Python Graph类最大度数计算错误，请求排查原因

问题概述 #

实现了Graph类用于计算图的最大度数和最小度数，预期最大度数为5，但实际运行返回4，代码及输出如下：

原代码 #

class Graph():
    def __init__(self, graph = None):
        if graph == None:
            graph = {}
        self.graph = graph
    
    def degree(self, node):
        deg =  len(self.graph[node])
        if node in self.graph[node]:
            deg += 1
        return deg

    def maxd(self):
        max = 0
        for node in self.graph:
            degree = self.degree(node)
            if degree > max:
                max = degree
        return max

    def mind(self):
        min = 10000000000
        for node in self.graph:
            nodedeg = self.degree(node)
            if nodedeg < min:
                min = nodedeg
        return min

graph = { "a" : {"c"},
          "b" : {"c", "e"},
          "c" : {"a", "b", "d", "e"},
          "d" : {"c"},
          "e" : {"c", "b"},
          "f" : {'c'}
        }

g = Graph(graph)

print("max:", g.maxd())
print("min:", g.mind())

运行输出 #

max: 4
min: 1

错误原因 #

你的degree方法仅计算了节点的出度（即当前节点指向其他节点的边数），再加上自环的情况，但实际你想计算的是无向图的度数——无向图中每条边是双向的，比如节点f指向c，这条边也应当计入c的度数，但你的代码中c的邻接集合并没有包含f，因此漏掉了这条入边，导致c的度数少算1，最终最大度数返回4而非预期的5。

修复方案 #

修改degree方法，统计所有与当前节点相连的边，包括其他节点指向它的入边：

class Graph():
    def __init__(self, graph = None):
        if graph == None:
            graph = {}
        self.graph = graph
    
    def degree(self, node):
        # 先统计出边数
        deg = len(self.graph[node])
        # 统计入边数：遍历所有其他节点，若该节点的邻接集合包含当前node，则计数+1
        for n in self.graph:
            if n != node and node in self.graph[n]:
                deg += 1
        # 自环的情况已经包含在len(self.graph[node])中，无需额外加1
        return deg

    def maxd(self):
        max_deg = 0
        for node in self.graph:
            degree = self.degree(node)
            if degree > max_deg:
                max_deg = degree
        return max_deg

    def mind(self):
        min_deg = float('inf')  # 用无穷大更符合Python编程习惯
        for node in self.graph:
            nodedeg = self.degree(node)
            if nodedeg < min_deg:
                min_deg = nodedeg
        return min_deg

graph = { "a" : {"c"},
          "b" : {"c", "e"},
          "c" : {"a", "b", "d", "e"},
          "d" : {"c"},
          "e" : {"c", "b"},
          "f" : {'c'}
        }

g = Graph(graph)

print("max:", g.maxd())  # 输出max: 5
print("min:", g.mind())  # 输出min: 1

说明 #

• 修复后的degree方法同时统计了出边和入边，符合无向图的度数定义；
• 将mind方法中的初始最小值替换为float('inf')，比硬编码大数更合理；
• 测试后最大度数返回5，与预期一致。

内容的提问来源于stack exchange，提问作者asldhaslfhlahsf