计算 NetworkX 图的断开组件数

Question

从一棵随机生成的树开始，我想考虑树的每个节点并可能以某种概率将其删除 p。由于树没有循环，并且任何一对节点之间都有一条唯一路径，因此删除一个节点应该留下 d 个断开连接的树，其中 d 是该节点的度数。

我的问题是，对整个图表完成此操作后，如何检查这些未连接的线段中有多少？

import networkx as nx
import random as rand

n = 20
p = 0.1

G = nx.random_tree(n)
for i in range(0, n):
    if rand.random() < p:
        G.remove_node(i)

x = G.count_disconnected_components() # is there anything that accomplishes this?

例如，对于此图，G.count_disconnected_components() 应该 return 3。

Answer 1

在我看来你实际上是想计算连接部分的数量。试试 number_connected_components:

print(list(nx.connected_components(G)))
print(nx.number_connected_components(G))

计算 NetworkX 图的断开组件数

Calculating the number of disconnected components of a NetworkX graph

python

graph-theory

networkx