python - 查找无向图的度数

Question

我正在尝试找出无向图的度分布。我尝试了以下代码:

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

def generate_edges(graph):
    edges = []
    for node in graph:
        for neighbour in graph[node]:
            edges.append((node, neighbour))

    return edges

print(generate_edges(graph))

我的输出是这样的:

[('c', 'a'), ('c', 'b'), ('c', 'd'), ('c', 'e'), ('b', 'c'), ('b', 'e'), ('a', 'c'), ('e', 'c'), ('e', 'b'), ('d', 'c')]

我正在努力寻找学位，但我没有得到它。我需要我的输出是 [1,2,2,0,1] 这是一个列表，其中索引值范围从 0 到图中的最大度数(即在上图中，4 是“c”的最大度数) 并且索引值是度数等于该索引的节点数。 (在上图中，有 1 个节点为 0 度，2 个节点为 1 度，2 个节点为 2 度，无节点为 3 度，最后 1 个节点为 4 度)。因此 [1,2,2,0,4]。谁能在不使用 NetworkX 的情况下帮助我解决这个问题？

Answer 1

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

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:
    l = len(graph[k])
    out[l]+=1

print(out)

输出 [1, 2, 2, 0, 1]