本文主要介绍Python算法的图遍历，涉及遍历算法BFS和DFS，以及寻找图的(强)连通分量的算法等。有一定的参考价值，有需要的朋友可以了解一下。
本节主要介绍图的遍历算法BFS和DFS，以及寻找图的(强)连通分量的算法。
遍历就是遍历，主要是图的遍历，也就是遍历图中的每一个节点。遍历一个节点有两个阶段，第一个是发现，然后是访问。不用说，图中有几个算法与遍历无关。
【算法入门很清楚发现和访问的区别，很好的解释了图的算法。遍历节点时，它标记其发现节点时间d[v]和结束访问时间f[v]，然后从这些时间的一些规则中得出一些实用的定理。本节稍后将介绍一些内容。有兴趣的话，不妨看看《算法导论》的原著]
图的连通分支是图的最大子图，其中任意两个节点可以互相到达(忽略边的方向)。这一节的重点是思考如何找到一个图的连通分支。
一个显而易见的思路是，我们从一个顶点开始，沿着边一直走，慢慢展开子图，直到子图不能再展开了，就得到一个连通分支，对吧？怎么才能确定真的找到了一个完整的连通分支呢？可以看看作者给出的解释。类似于上一节的归纳，我们考虑从i-1到I的过程，只要保证添加这个节点后子图仍然连通。
让我们看看下面的相关问题。显示您可以连接V1，V2，…Vn，sosat for any I=1…n，thesubgraphoverV1，…，VI。如果我们可以显示thisandweconfigureouthowtodotherordering，我们可以通过所有的nodesinectedcomponentdknowhenthereallusedup。
这是怎么回事？归纳起来想，我们需要。我们知道thubgraphoverthei-1第一个节点是连通的。接下来呢？嗯，因为有12对节点，考虑到第一个节点和第二个节点。从utov的路径来看，考虑到组件中的last node，我们已经建立了，以及aswellasthefirstnodeoutsideit。让我们称之为andwe，它们之间必须有边缘，因此添加到我们的growing components保持连接的节点，并且我们显示我们设置为显示的内容。
经过上面的思考，我们知道了如何寻找连通分支：从一个顶点开始，沿着它的边寻找其他节点(或者站在这个节点上，看能找到哪些节点)，然后不断地向已有的连通分支添加节点，使连通分支仍然满足连通性质。如果我们继续遵循上面的想法，我们将得到一棵树，一棵遍历树，这也是我们遍历的组件的生成树。在实现这种算法时，我们要记录“边节点”，即那些与所得到的连通分量中的节点相连接的节点。它们就像待办事项列表，前面添加的节点就是已勾选的待办事项列表。
在这里，作者举了一个很有意思的例子，一个角色扮演游戏。如下图所示，我们可以把房间看成一个节点，房间的门看成节点之间的边，我们走过的路径就是遍历树。这样，房间分为三种：(1)我们经过的房间；(2)我们已经经过的房间附近的房间，也就是可以马上进入的房间；(3)“黑屋子”，我们甚至不知道它们是否存在，也不知道它们在哪里。
根据上面的分析，可以写出下面的遍历函数walk，其中的参数s暂时没有用，后面要找强连通分量，表示一个“禁区”，就是不要访问这些节点。
请注意以下差分函数的使用。参数可以是多个，也就是说，调用后返回的集合中的元素并不存在于每个参数中。另外，参数不一定要设置，也可以是dict或list，只要是可迭代的即可。你可以看看python文档
#遍历用邻接集表示的图的连通部分
def walk(G，S，S=set()): #从节点S开始遍历图
p，Q=dict()，set() #前置任务'待办事项'队列
P[s]=None # s没有前任
Q.add(s) #我们计划从s开始
而Q: #仍然是要访问的节点
u=Q.pop() #任意挑一个
对于G[u]中的v。差异(P，S): #新节点？
我们计划去拜访他们！
记住我们从哪里来
返回P
我们可以用下面的代码测试一下，结果没问题。
def some_graph()。
a，b，c，d，e，f，g，h=范围(8)
N=[
[b、c、d、e、f]，# a
[中、英]，# b
[d]，# c
[英]，# d
[f]，# e
[c，g，h]，# f
[f，h]，# g
[f，g] # h
]
返回
G=some_graph()
对于范围内的I(len(G)):G[I]=set(G[I])
打印列表(walk(G，0)) #[0，1，2，3，4，5，6，7]
上面的行走函数只适用于无向图，只能找到一个从参数S开始的连通分量。如果你想得到所有连接的组件，你需要修改它们。
定义组件(G): #连接的组件
comp=[]
seen=set() #我们已经看到的节点
对于u in G: #尝试每一个起点
如果你在看过：继续#看过？忽略它
C=walk(G，u) #横向分量
seen.update(C) #将C的键添加到seen
comp.append(C) #收集组件
退货补偿
用下面的代码测试，结果没问题。
G={
0: set([1，2])，
1: set([0，2])，
2: set([0，1])，
3: set([4，5])，
4: set([3，5])，
5:设置([3，4])
}
打印[组件(G)中C的列表(排序(C))]#[[0，1，2]，[3，4，5]]
至此，我们已经完成了一个寻找时间复杂度为 (EV)的无向图的连通分支的算法，因为每个边和顶点都要访问一次。【这种时间复杂度会经常看到，比如拓扑排序，在强连通分量中很常见】
【接下来，作者引入欧拉路径和哈密尔顿回路作为扩展：前者一次穿过图的所有边，然后返回起点；后者是通过图中所有顶点一次，然后返回起点。网上有很多信息，有兴趣自己去了解一下]
下面我们来看迷宫问题。如下图，原问题是一个人在公园里走，结果走不出来。即使他按照“左手法则”(即遇到路口总是左转)行走，但如果走回原来的起点，就会陷入死循环！有趣的是，左边的迷宫可以通过“左手定则”转化为右边的树形结构。
【注：具体换算方法我还没看懂。下面是作者给出的构造描述]
在这种情况下，“把一只手放在墙上”的策略会很有效。了解其工作原理的一种方法是观察迷宫实际上只有一个内壁(或者，换句话说，如果你在里面放墙纸，你可以使用一个连续的条带)。看外面的方块。只要你不被允许创建循环，你画的任何障碍都必须在一个确切的地方连接到它，这不会给左手定则带来任何问题。按照这种遍历策略，您将发现所有节点，并对每个通道遍历两次(每个方向一次)。
上面的迷宫其实是要通向DFS的。每当我们到达一个十字路口，也许我们可以向左或向右走。选择有很多，但要想一直走下去，只能选择其中一个。如果发现这个方向走不出去，就回头选择一个刚才没选的方向继续尝试。
基于上述思想，可以写出下面的DFS递归版本。
def rec_dfs(G，S，S=None):
如果S为None: S=set() #初始化历史记录
我们已经参观过了
for u in G[s]: #探索邻居
如果您在美国：继续#已访问：跳过
rec_dfs(G，u，S) # New:递归浏览
返回S #进行测试
G=some_graph()
对于范围内的I(len(G)):G[I]=set(G[I])
打印列表(rec_dfs(G，0)) #[0，1，2，3，4，5，6，7]
很自然地，我们会想到将递归版本改为迭代版本。以下代码使用Python中的yield关键字。具体用法请看IBM Developer Works这里。
def iter_dfs(G，s):
s，Q=set()，[] # Visited-set和queue
Q.append(s) #我们计划访问s
而Q: #计划节点剩余？
u=Q.pop() #获取一个
如果你在美国：继续#已经访问？逃走
我们已经参观过了
Q.extend(G[u]) #调度所有邻居
产出u #报告u被访问
G=some_graph()
对于范围内的I(len(G)):G[I]=set(G[I])
打印列表(iter_dfs(G，0)) #[0，5，7，6，2，3，4，1]
上面的迭代版本可以稍微修改一下，得到一个更一般的遍历函数。
定义遍历(G，s，qtype=set):
s，Q=set()，qtype()
q .添加
一边问：
u=Q.pop()
如果你在美国：继续
添加(u)
对于G[u]中的v:
问题补充(五)
产量u
traverse函数中的参数qtype表示队列类型，比如stack stack。下面的代码显示了如何自定义堆栈和测试遍历函数。
类堆栈(列表):
添加=列表.追加
G=some_graph()
打印列表(遍历(G，0，stack)) #[0，5，7，6，2，3，4，1]
如果还不清楚，可以看看算法介绍里的这张DFS示例图。后面会介绍节点的颜色。
上图显示了DFS中节点的时间戳。这有什么作用？
如前所述，在遍历一个节点时，如果该节点标有其发现节点时间d[v]和结束访问时间f[v]，我们就可以从这些时间中找到一些信息，比如下图，(a)是一个带时间戳的图的DFS遍历的结果；(b)如果在每个节点的d[v]到f[v]的区间上加一个括号，可以看出DFS遍历中节点U的后继节点V(即后面的深度优先树/森林)的所有区间都在节点U的区间内，如果节点V不是节点U的后继，那么两个节点的区间不相交，这就是“括号定理”。
带时间戳的DFS遍历很好写吧？
#带时间戳的深度优先搜索
def dfs(G，S，d，f，S=无，t=0):
如果S为None: S=set() #初始化历史记录
d[s]=t；t=1 #设置发现时间
我们已经参观过了
for u in G[s]: #探索邻居
如果你在美国：继续#已经访问。跳跃
t=dfs(G，u，d，f，S，t)# Recurse；更新时间戳
f[s]=t；t=1 #设定完成时间
返回t #返回时间戳
除了给节点添加时间戳，《算法简介》在引入DFS时还会给节点上色。节点在被发现前是白色的，被发现后是灰色的，访问结束后是黑色的。详细过程请参考前面算法介绍中的DFS示例图。颜色有什么用？起作用了！根据节点的颜色，我们可以对边进行分类！大致可以分为以下四种类型：
当使用DFS遍历图时，对于每个边(u，V)，当第一次发现边时，根据节点V的颜色对边进行分类(前向边和交叉边不进行细分):
(1)白色表示边缘是树边缘；
(2)灰色表示该边是对边；
(3)黑色表示边缘是前向边缘或交叉边缘。
下图显示了上面引入括号定理时，图的深度优先树中所有边的类型。用灰色标记的边是深度优先树的树边。
边分类的作用是什么？功能很多！最常见的功能是判断有向图中是否存在回路。如果通过有向图的DFS遍历找到了对边，那么一定有环，否则没有环。另外，对于无向图，如果被DFS遍历，肯定不会有前向边或交叉边。
时间戳节点有什么用？其实除了上面提到的重要性质，对于接下来要介绍的拓扑排序和强连通分量的另一种解法，时间戳是非常重要的！
我们来看看这个取自《算法导论》的拓扑排序的例图。这就是一个教授早上起来会做的事，呵呵。
不难发现，最终的拓扑排序只是节点完成时间f[v]的降序！结合前面的括号定理和依赖关系就不难理解了。如果把节点按f[v]降序排列，就会得到我们想要的拓扑排序！这是拓扑排序的另一种解法！【在《算法导论》中，这个解是主解，而我们之前提到的那个出现在《算法导论》的习题中】
基于以上思路，可以得到以下实现代码。recurse函数是一个内部函数，因此它可以访问G和RES等变量。
#基于深度优先搜索的拓扑排序
def dfs_topsort(G):
s，res=set()，[] #历史和结果
def recurse(u): #遍历子程序
if u in S: return #忽略访问过的节点
否则：添加到历史记录中
对于G[u]中的v:
递归(v) #通过邻居递归
res.append(u) #以u: Append结束
对于u in G:
覆盖整个图形
res.reverse() #目前为止都是落后的
返回资源
G={'a': set('bf ')，' b': set('cdf ')，' c': set('d ')，' d': set('ef ')，' e': set('f ')，' f': set()}
打印dfs_topsort(G)
【接下来作者介绍了一种迭代加深的深度优先搜索，我没看懂。好像和BFS差不多]
如果我们一层一层地遍历图，首先找到的节点首先被访问，那么我们得到广度优先搜索(BFS)。下面是作者给出的一个有趣的例子，说明BFS和DFS之间的区别。遍历的过程就像我们上网一样。DFS会一个一个地跟随网页上的链接，当您访问完这个网页后，单击Back返回上一个网页继续访问。BFS首先在后台打开当前网页上的所有链接，然后按照打开的顺序逐一访问。访问网页后，它会关闭窗口。
可视化BFS和DFS的一种方式是浏览网页。如果你一直跟随链接，然后在进入一个页面后使用后退按钮，你就会得到DFS。回溯有点像“撤销”BFS更像是在一个新窗口(或标签页)中打开你已经打开的链接，然后在你完成每一页后关闭窗口。
BFS的代码很容易实现，主要使用队列。
#广度优先搜索
从集合导入队列
定义bfs(G，s):
p，Q={s: None}，dequee([s])#父队列和FIFO队列
一边问：
u=q . pop left()# dequee的常数时间
对于G[u]中的v:
如果P: continue #中的v已经有父级
P[v]=u #来自u: u是父级
q .追加(v)
返回P
G=some_graph()
打印bfs(G，0)
Python的list可以作为栈使用，但是作为队列使用时性能很差。函数bfs在collections模块中使用dequee，即dequee(双端队列)，一般使用链表实现。这个类的方法，比如extend、append和pop，都作用于队列的右端。而extendleft、appendleft、popleft等方法都作用于队列的左端，其内部实现非常高效。
在内部，deque被实现为一个双向链表块，每个块都是一个单个元素的数组。虽然在渐近上等同于使用单个元素的链表，但这减少了开销，并使其在实践中更有效。例如，如果d[k]是一个普通列表，那么表达式d[k]将需要遍历deque d的前k个元素。如果每个块包含b个元素，那么只需遍历k//b个块。
最后，让我们看看强连接的组件。正面组件不考虑边的方向。如果我们考虑边的方向，并且最大子图中的任意两个节点都可以沿着边到达，那么这就是强连通分量。
下图是算法简介中的一个示例图。(a)它是图的DFS遍历的带时间戳的结果；(b)是上图的换位，即颠倒上图中所有边的方向得到的图形；(c)是最终得到的强连通分支图，分支中的节点显示在每个节点内部。
自然不容易理解怎么得到上面的样图。大家慢慢来分析三图【原书中分析太多，我很迷茫_。下面是我结合算法介绍的分析过程]
先看图(a)。每个灰色区域都是强连通分支。我们来想，如果强连通分支X内部有一条边指向另一个强连通分支Y，那么强连通分支Y内部肯定没有一条边指向另一个强连通分支Y，否则它们可以整合起来形成一个新的更大气的强连通分支！也就是说强连通分支图一定是有向无环图！从图(c)中我们还可以看到
看图(c)，强连接分支之间的方向。如果我们定义每个分支中任意顶点的最晚完成时间为对应分支的完成时间，那么分支abe的完成时间为16，分支cd为10，分支fg为7，分支H为6。不难发现，分支之间的边的方向是从完成时到完成时，换句话说，总是从完成时到完成时。
最后看图(B)，是原图的换位，但是强连通分支是一样的(强连通分支图会变化，只是原分支图的换位)，那么为什么要反边呢？结合前面两个图的分析，由于强连通分支图是有向无环图，并且总是从完成时间晚的强连通分支指向完成时间早的强连通分支，如果我们反边，虽然得到的强连通分支不变，但是分支之间的方向发生了变化，完成时间晚的不再指向完成时间早的那个！这样，如果按拓扑排序，也就是按完成时间降序再做一次DFS，就可以一个个得到强连通分支了，对吧？因为每次得到一个强连通分支，都没有办法指向其他分支，也就是确定一个强连通分支后就停止了。【试着画个图得到图(B)的强连通分支图的拓扑排序结果，你就明白了】
经过上面稍微复杂的分析，我们知道强连通分支算法的流程有以下四个步骤：
1.在原图g上运行DFS，得到每个节点的完成时间f[v]；
2.得到原图像的转置图像gt；
3.在GT上运行DFS，主循环按照节点f[v]降序访问；
4.输出深度优先森林中的每棵树，即强连通分支。
根据以上思路，可以实现以下强连通分支算法，其中函数parse_graph是作者为了方便构造图而使用的函数。
定义tr(G): #转置(修订边缘)
GT={}
for u in G: GT[u]=set() #获取所有的节点
对于u in G:
对于G[u]中的v:
GT；GT；v .添加(u) #添加所有反向边
返回大型旅行车
def scc(G):
GT=tr(G) #得到转置图
sccs，seen=[]，set()
对于dfs_topsort(G)中的u:# DFS起点
如果u in seen: continue #忽略覆盖的节点
C=walk(GT，u，seen) #不要'后退(见过)
seen.update(C) #我们现在已经看到了C
sccs.append(C) #找到另一个单路调节器(single-channel controller)
返回单路调节器(single-channel controller)
从字符串导入ascii _小写
定义解析图：
# print zip(ascii_lowercase，s.split('/'))
# [('a '，' bc ')，(' b '，' die '，(' c '，' d '，(' d '，' ah ')，(' e '，' f '，(' f '，' g '，(' g '，' eh ')，(' h '，' I '，(' I '，' h')]
G={}
对于u，zip中的行(ascii_lowercase，s.split('/'):
G[u]=集合（行)
返回G
g=parse _ graph(' BC/die/d/ah/f/g/eh/I/h ')
打印列表(映射(列表，scc(G)))
#[['a '，' c '，' b '，' d']，['e '，' g '，' f']，['i '，' h']]
[最后作者提到了一点如何进行更加高效的搜索，也就是通过分支限界来实现对搜索树的剪枝，具体使用可以看下这个问题顶点覆盖问题顶点覆盖问题]
问题5.17 强连通分支
在科萨拉朱的算法中，我们通过从初始深度优先搜索开始递减完成时间来找到最终遍历的开始节点，并且我们在转置图中执行遍历（即，所有边都反转)。为什么我们不能在原始图表中使用递增的完成时间？
问题就是说，我们干嘛要对转置图按照完成时间降序遍历一次呢？干嘛不直接在原图上按照完成时间升序遍历一次呢？
试着找一个简单的例子，这个例子会给出错误的答案。(你可以用一个非常小的图来做。)
总结
以上就是本文关于计算机编程语言算法之图的遍历的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：
python先序遍历二叉树问题
python实现报表自动化详解
python绘制铅球的运行轨迹代码分享
如有不足之处，欢迎留言指出。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。