本来这个问题应该是放在并查集里面一起说明，不过并查集篇幅比较大，就单独把这个问题拿出来了。
并查集的问题也可以转化为图的连通子图问题。给一个图G，返回它的所有不连通的子图。
1. 使用networkx包求图的所有不连通的子图
主要使用connected_components()方法。下面是一个例子。
import networkx as nx
import matplotlib.pyplot as plt
pointList = ['A','B','C','D','E','F','G']
linkList = [('A','B'),('B','C'),('C','D'),('E','F'),('F','G'),]
def subgraph():
G = nx.Graph()
# 转化为图结构
for node in pointList:
G.add_node(node)
for link in linkList:
G.add_edge(link[0], link[1])
# 画图
plt.subplot(211)
nx.draw_networkx(G, with_labels=True)
color =['y','g']
subplot = [223,224]
# 打印连通子图
for c in nx.connected_components(G):
# 得到不连通的子集
nodeSet = G.subgraph(c).nodes()
# 绘制子图
subgraph = G.subgraph(c)
plt.subplot(subplot[0]) # 第二整行
nx.draw_networkx(subgraph, with_labels=True,node_color=color[0])
color.pop(0)
subplot.pop(0)
plt.show()
subgraph()
原图与分开后的子图
那么networkx的connected_components()方法是如何实现的呢，也很简单，通过BFS遍历来找连通的子图。进行一次完整的BFS遍历可以一组连通节点，放入一个集合，然后从没有遍历到的节点再开始一次BFS遍历，放入集合就是另一组连通子图，以此类推可以几次BFS就找到几个连通子图，看源码：
seen = set()
for v in G:
if v not in seen:
c = set(_plain_bfs(G, v))
yield c
seen.update(c)
2. 一个很经典的广度优先算法
networkx实现的BFS算法，这里使用G_adj[v]是邻接矩阵的存储方式，所以时间复杂度是O(|V|^2）
def _plain_bfs(G, source):
"""A fast BFS node generator"""
G_adj = G.adj
seen = set()
nextlevel = {source}
while nextlevel:
thislevel = nextlevel
nextlevel = set()
for v in thislevel:
if v not in seen:
yield v
seen.add(v)
nextlevel.update(G_adj[v])
邻接表形式存储时，每个顶点均需搜索一次，时间复杂度T1=O（v），从一个顶点开始搜索时，开始搜索，访问未被访问过的节点。最坏的情况下，每个顶点至少访问一次，每条边至少访问1次，这是因为在搜索的过程中，若某结点向下搜索时，其子结点都访问过了，这时候就会回退，故时间复 杂度为O(E)，算法总的时间复 度为O(|V|+|E|)
时间复杂度参考链接(https://blog.csdn.net/Charles_ke/article/details/82497543 )
3. 在这里顺便回顾一下深度优先遍历(DFS)
邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(|V|)，要查找整个矩阵，故总的时间复杂度为O(|V|^2)
邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O（V）,此时，总的时间复杂度为O(V+E) (这里没自己实现邻接表代码，直接抄书上的过来了)
G的定义与上面相同
递归形式（参考王道数据结构）：
G_adj = G.adj
seen = set()
def DFSTraverse(G):
for v in G:
if v not in seen:
c = set(DFS(G,v))
seen.update(c)
def DFS(G,v):
seen.add(v)
yield v
# 访问操作
print(v)
for w in G_adj[v]:
if w not in seen:
DFS(G,w)
DFSTraverse(G)
使用队列实现DFS(参考链接https://blog.csdn.net/changyuanchn/article/details/79008760
):
def DFS2(G,node0):
G_adj = G.adj
#queue本质上是堆栈，用来存放需要进行遍历的数据
#order里面存放的是具体的访问路径
queue,order=[],[]
#首先将初始遍历的节点放到queue中，表示将要从这个点开始遍历
queue.append(node0)
while queue:
#从queue中pop出点v，然后从v点开始遍历了，所以可以将这个点pop出，然后将其放入order中
#这里才是最有用的地方，pop（）表示弹出栈顶，由于下面的for循环不断的访问子节点，并将子节点压入堆栈，
#也就保证了每次的栈顶弹出的顺序是下面的节点
v = queue.pop()
order.append(v)
#这里开始遍历v的子节点
for w in G_adj[v]:
#w既不属于queue也不属于order，意味着这个点没被访问过，所以讲起放到queue中，然后后续进行访问
if w not in order and w not in queue:
queue.append(w)
return order
def DFSTraverse2(G):
seenArray = []
for v in G:
if v not in seenArray:
order = DFS2(G,v)
seenArray.extend(order)
return seenArray
seenArray = DFSTraverse2(G)
print(seenArray)
