本來這個問題應(yīng)該是放在并查集里面一起說明凹蜈，不過并查集篇幅比較大，就單獨把這個問題拿出來了忍啸。
并查集的問題也可以轉(zhuǎn)化為圖的連通子圖問題仰坦。給一個圖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()
# 轉(zhuǎn)化為圖結(jié)構(gòu)
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()方法是如何實現(xiàn)的呢白粉，也很簡單传泊，通過BFS遍歷來找連通的子圖。進(jìn)行一次完整的BFS遍歷可以一組連通節(jié)點鸭巴，放入一個集合眷细，然后從沒有遍歷到的節(jié)點再開始一次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. 一個很經(jīng)典的廣度優(yōu)先算法
networkx實現(xiàn)的BFS算法，這里使用G_adj[v]是鄰接矩陣的存儲方式恬口，所以時間復(fù)雜度是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])
鄰接表形式存儲時校读，每個頂點均需搜索一次，時間復(fù)雜度T1=O（v）祖能，從一個頂點開始搜索時歉秫，開始搜索，訪問未被訪問過的節(jié)點养铸。最壞的情況下雁芙，每個頂點至少訪問一次，每條邊至少訪問1次钞螟，這是因為在搜索的過程中兔甘，若某結(jié)點向下搜索時，其子結(jié)點都訪問過了鳞滨，這時候就會回退洞焙，故時間復(fù) 雜度為O(E)，算法總的時間復(fù) 度為O(|V|+|E|)
時間復(fù)雜度參考鏈接(https://blog.csdn.net/Charles_ke/article/details/82497543 )
3. 在這里順便回顧一下深度優(yōu)先遍歷(DFS)
鄰接矩陣表示時，查找每個頂點的鄰接點所需時間為O(|V|)澡匪，要查找整個矩陣熔任，故總的時間復(fù)雜度為O(|V|^2)
鄰接表表示時，查找所有頂點的鄰接點所需時間為O(E)仙蛉，訪問頂點的鄰接點所花時間為O（V）,此時笋敞，總的時間復(fù)雜度為O(V+E) (這里沒自己實現(xiàn)鄰接表代碼碱蒙，直接抄書上的過來了)
G的定義與上面相同
遞歸形式（參考王道數(shù)據(jù)結(jié)構(gòu)）：
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)
使用隊列實現(xiàn)DFS(參考鏈接https://blog.csdn.net/changyuanchn/article/details/79008760
):
def DFS2(G,node0):
G_adj = G.adj
#queue本質(zhì)上是堆棧荠瘪，用來存放需要進(jìn)行遍歷的數(shù)據(jù)
#order里面存放的是具體的訪問路徑
queue,order=[],[]
#首先將初始遍歷的節(jié)點放到queue中，表示將要從這個點開始遍歷
queue.append(node0)
while queue:
#從queue中pop出點v赛惩，然后從v點開始遍歷了哀墓，所以可以將這個點pop出，然后將其放入order中
#這里才是最有用的地方喷兼，pop（）表示彈出棧頂篮绰，由于下面的for循環(huán)不斷的訪問子節(jié)點，并將子節(jié)點壓入堆棧季惯，
#也就保證了每次的棧頂彈出的順序是下面的節(jié)點
v = queue.pop()
order.append(v)
#這里開始遍歷v的子節(jié)點
for w in G_adj[v]:
#w既不屬于queue也不屬于order吠各，意味著這個點沒被訪問過，所以講起放到queue中勉抓，然后后續(xù)進(jìn)行訪問
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)
