查找无向图的程度

Rachel 发表于 Dev

瑞秋

我试图找到无向图的度分布。我尝试了以下代码：

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的情况下帮助我吗？

金库

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)