Skip to main content
 首页 » 编程设计

python之查找无向图的度数

2024年11月01日12xing901022

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

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) 

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