电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 图论算法有图有代码万字总结向前辈致敬（7） [打印本页]

作者: yuyang911220 时间: 2016-8-20 19:51 标题: 图论算法有图有代码万字总结向前辈致敬（7）

深度优先搜索深度优先搜索（depth-first search）是对前序遍历的推广，对每一个顶点，字段visited被初始化成false，通过哪些尚未被访问的结点递归调用该过程，我们保证不会陷入无限循环。如果图是无向且连通的，或是有向但非强连通的，这种方法可能会访问不到某些结点。此时我们搜索一个未被标记的结点，然后应用深度优先遍历，并继续这个过程直到不存在未标记的结点为止。因为该方法保证每一条边只被访问一次，所以只要使用邻接表，执行遍历的总时间就是O(|E|+|V|)。
深度优先搜索的算法实现：
#define FALSE 0 #define TRUE 1 short int visited[MAX_VERTICES] void dfs(int v) { node_pointer w; visited[v]=TRUE; printf("%5d",v); for(w=graph[v];w;w=w->link); if(!visited[w->vertex]) dfs(w->vertex); }

和上文中的广搜一样，我们也来对dfs进行分析。
如果采用邻接表来存储，就可以沿着顶点的链表来确定其所有邻接顶点。因此在邻接表中的每一个顶点都至多扫描一次，所以完成搜索时间复杂性为O(e)。
如果采用邻接矩阵来存储，访问顶点的所有邻接顶点的时间为O(n)，而整个过程至多访问n个顶点，因此完成搜索时间复杂性为O(n2)。
无向图如下左图中是一个无向图，我们以此为例，假设从A开始，标记A为known并递归地调用dfs(B)。dfs(B)标记B为known并递归调用dfs(C)。dfs(C)标记C为known并递归调用dsf(D)。而后D的邻接结点只有C，但C已经是knwon的，这里便无法再继续递归下去，因此返回到dfs(C)。dfs(C)看到已经标记为known的B邻接点和D邻接点，因此调用dfs(E)。dfs(E)标记E为known，同样的它只能返回到dfs(C)，再返回到dfs(B)，最后返回到dfs(A)。实际上这里接触每条边2次，一次是作为边（v，w），另一次是作为边（w，v）。
如下右图展示了深度优先搜索树（depth-first spanning tree）的步骤。虚线表示向后边（back edge），表示这条“边”并不是树的一部分。

树将模拟我们执行的遍历，使用树的边对该树的前序编号（preorder numbering）表示顶点被标记的顺序；如果图不是连通的，那么处理所有的结点（以及边）自然需要多次反复调用dfs，每次都生成一棵树，整个集合就是深度优先生成森林（depth-first spanning forest）。
双连通性前面我们已经介绍过了双连通图，如果删除一个无向图的仁一顶点后，剩下的图仍然连通，那么这样的无向连通图就称为是双连通的（biconnected）。
如果图不是双联通的，那么将其删除后不再连通的那些顶点叫做割点（articulation point）。
深度优先搜索提供了一种找出连通图中所有割点的线性时间算法。从图中任一顶点开始，执行深度优先搜索并在顶点被访问时给它们编号。对于每一个顶点v，我们称其前序编号为Num(V)。然后，对于深度优先搜索生成树中的每一个顶点v，计算编号最低的顶点，我们称之为Low(V)，该点可从v开始通过树的零条或多条边，且可能还有一条后向边而以该序达到。

有向图如前所述，如果图不是强连通的，那么从某个结点开始的深度优先搜索可能访问不了所有的结点，这种情况下我们从某个未做标记的结点处开始，反复执行深度优先搜索，直到所有的结点都被访问到为止。

对此我们从顶点B开始深度优先搜索，依次访问B、C、A、D、E、F。而后从某个未被标记的顶点重新开始，比如H，然后访问J和I。最后从G开始，也从此结束。

深度优先生成森林中的虚线是一些（v，w）边，其中的w在考察时已经做了标记。在无向图中，它们总是一些向后边，但是可以看到，存在三种类型的边并不通向新的顶点。这里有一些向后边（back edge），如（A，B）；还有一些向前边（forward edge），如（C，D）；最后还有一些交叉边（cross edge），如（F，C），它们把不直接相关的两个树结点连接起来。深度优先搜索森林一般通过把一些子结点和一些新的树丛左到右添加到森林中形成。
深度优先搜索还可以用来检测一个有向图是否是无环图，因为一个有向图是无环图当且仅当它没有向后边。上面的例子明显不是无环图，因为它有向后边。而拓扑排序也可以用来检测一个图是否是无环图，进行拓扑排序的另一种方法是通过深度优先搜索生成森林的后序遍历给顶点指定拓扑编号N，N−1，……，1。只要图是无环的，这种排序就是一致的。

作者: yuchengze 时间: 2016-8-21 12:14

很好的算法分析，感谢楼主的分享，完美解决了我的问题

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)