求图的连通⼦图python使⽤networkx（BFS,DFS）本来这个问题应该是放在并查集⾥⾯⼀起说明，不过并查集篇幅⽐较⼤，就单独把这个问题拿出来了。
并查集的问题也可以转化为图的连通⼦图问题。给⼀个图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 ted_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()
原图与分开后的⼦图
那么networkx的connected_components()⽅法是如何实现的呢，也很简单，通过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:
matplotlib中subplotthislevel = nextlevel
nextlevel =set()
for v in thislevel:
if v not in seen:
yield v
seen.add(v)
nextlevel.update(G_adj[v])
###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)
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)
return seenArray
seenArray = DFSTraverse2(G)
print(seenArray)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。