连通性与连通分量

连通性定义：若一个途中人两点间有路径相通，则称此图为连通图。
例如：networkx学习与使用——（3）路与圈中创建的APANET就是一个连通图，但并不是所有的图都是连通图。
连通分量定义：若图G的节点子集满足如下两个条件：

1. 子集中任意两个节点间均有路径相通；
2. 该子集不是其他任何满足条件1的子集的一部分；

则称该子集为图G的一个连通分量。具体实例如下：

import networkx as nx               #载入networkx包
import matplotlib.pyplot as plt     #用于画图
G = nx.Graph()                     #无向图
example_edges = [('A','B'),('C','E'),('D','E'), 
                 ('F','G'),('F','H'),('G','I'), 
                 ('G','J'),('H','J'),('H','L'), 
                 ('H','M'),('I','K'),('J','K'), 
                 ('L','K'),('L','H'),('L','M')]
G.add_edges_from(example_edges)

上图的例子共有三个连通分量，这是很直观的。

networkx中的连通性分析

事实上对于一个图，我们对连通性的需求通常有两点：

1. 该图是否连通？
2. 若图不连通，那么此图有多少连通分量？

networkx将这样的分析归类在Algorithms->Components中：

判断图是否连通：

print(nx.is_connected(G))

out:
False

求图的连通分量的数量：

print(nx.number_connected_components(G))

out:
3

求图各连通分量的节点集合：

for i in nx.connected_components(G):
    print(i)

out:
{'B', 'A'}
{'D', 'E', 'C'}
{'K', 'J', 'I', 'M', 'H', 'L', 'G', 'F'}

生成各个连通分量的子图：

graphs=list(nx.connected_component_subgraphs(G))

分别画出graphs[0]、graphs[1]和graphs[2]如下图:



求包含某个节点的连通分量的节点集合：

print(nx.node_connected_component(G, 'H'))

out:
{'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M'}

大体上简单的连通性分析就是这些，networkx还提供了更丰富的连通性分析，包括有向图的连通性分析，强连通分析和弱连通分析，割点割边的分析，这些后面再阐述。

完整代码资源

networkx学习（4）

参考

networkx官网地址：https://networkx.org/