时间戳

首页 > 解决方案 > 求图的最小度

python - 求图的最小度

问题描述

我正在尝试找到图形的度数分布。我尝试了以下代码：

class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self, nbr, weight=0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        degree = len([x.id for x in self.connectedTo])
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo]) + ' with degree ' + str(
            len([x.id for x in self.connectedTo])), degree

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self, nbr):
        return self.connectedTo[nbr]


class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self, key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self, n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self, n):
        return n in self.vertList

    def addEdge(self, f, t, weight=0):
        if f not in self.vertList:
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], weight)

    def removeEdge(self, f, t):
        # return self.vertList[f].pop(t)
        del self.vertList[f][t]

    def getVertices(self):
        return self.vertList.keys()

    def removeVertices(self, f):
        del self.vertList[f]

    def __iter__(self):
        return iter(self.vertList.values())


n = int(input())
g = Graph()
for i in range(n):
    command = input().split(' ')
    if command[0] == 'IV':
        g.addVertex(command[1])
    if command[0] == 'IA':
        g.addEdge(command[2], command[1])
    if command[0] == 'RV':
        g.removeVertices(command[1])
    if command[0] == 'RA':
        g.removeEdge(command[2], command[1])

for v in g:
    for w in v.getConnections():
        print(f'( {v.getId()} , {w.getId()} )')

print(g.getVertices())
degrees = [v.__str__()[1] for v in g]
print(degrees)
if len(degrees) > 1:
    print(min(degrees))

我的输入是这样的：

9
IV A
IV B
IV C
IA B C
IV D
IV E
IV F
IA E D
IA E F

我的输出是这样的：

( C , B )
( D , E )
( F , E )

图的度数是其顶点度数的最大值，但我试图实现相反的想法，即它是顶点度数的最小值。任何人都可以在不使用 NetworkX 的情况下帮助我吗？

我试图继续使用这个逻辑，但我无法使用已经预定义的类来实现：

graph = {"A": [],
         "B": [],
         "C": ["B"],
         "D": ["E"],
         "E": [],
         "F": ["E"]}


def max_length(x):
    return len(graph[x])


# Determine what index has the longest value
index = max(graph, key=max_length)
m = len(graph[index])

# Fill the list with `m` zeroes
out = [0 for x in range(m + 1)]

for k in graph:
    print(k)
    l = len(graph[k])
    out[l] += 1

print(out)

标签： python

解决方案

感谢大家的评论。我想在更改程序逻辑并重做例程后，我设法实现了我的预期：

from collections import defaultdict


class Graph:
    def __init__(self):
        self._graph = defaultdict(set)
        self._weight = dict()

    def has_node(self, n):
        return n in self._graph

    def nodes(self):
        return iter(self._graph)

    def node_count(self):
        return len(self._graph)

    def neighbours(self, n):
        return iter(self._graph[n])

    def neighbour_count(self, n):
        return len(self._graph[n])

    def add_node(self, n):
        """Add the node n."""
        self._graph[n]

    def remove_node(self, n):
        for n1 in self.neighbours(n):
            if n1 != n:
                self._graph[n1].remove(n)
            del self._weight[self._edge(n, n1)]
        del self._graph[n]

    def _edge(self, n1, n2):
        return (n1, n2) if n1 <= n2 else (n2, n1)

    def has_edge(self, n1, n2):
        return self._edge(n1, n2) in self._weight

    def edges(self):
        for n, w in self._weight.items():
            yield n + (w,)

    def edge_count(self):
        return len(self._weight)

    def edge_weight(self, n1, n2):
        return self._weight[self._edge(n1, n2)]

    def add_edge(self, n1, n2, w=0):
        self._graph[n1].add(n2)
        self._graph[n2].add(n1)
        self._weight[self._edge(n1, n2)] = w

    def remove_edge(self, n1, n2):
        self._graph[n1].remove(n2)
        if n1 != n2:
            self._graph[n2].remove(n1)
        del self._weight[self._edge(n1, n2)]


n = int(input())
if n != 0:
    g = Graph()
    for i in range(n):
        command = input().split(' ')
        if command[0] == 'IV':
            g.add_node(command[1])
        if command[0] == 'IA':
            g.add_edge(command[2], command[1])
        if command[0] == 'RV':
            g.remove_node(command[1])
        if command[0] == 'RA':
            g.remove_edge(command[2], command[1])

    keys = [i for i in g.nodes()]
    degrees = [g.neighbour_count(i) for i in keys]
    print(min(degrees))
else:
    print(0)

推荐阅读