深入浅出：数据结构与算法解析与应用

时间：11-09 名人轶事提交错误

图像回忆了深度优先搜索的过程：从某个顶点开始，访问它的一个相邻点，然后访问这个相邻点的相邻点之一.一直深入，直到到达某个顶点并发现周围的邻近地区。所有点都已访问过。这时候再回到前一个顶点，访问该顶点未访问过的相邻点……直到所有顶点都被访问过。容易知道一次深度优先遍历中所有访问过的顶点都是相互可达的，即连通的。我们按照并查算法为每个连通分量标记一个id，即具有相同id的顶点属于同一个连通分量。上面已经分析过，连通分量的数量范围是[1, graph.vertexNum]，所以所需的ids graph.vertexNum数量就足够了。存储ids 的数组int[] 的范围是[0, graph.vertexNum - 1 ]。

以下是查找无向图的所有连通分量的代码。使用的无向图是上面具有3 个连通分量的图。

包第7章；

导入java.util.LinkedList;

公共课CC {

//用于标记已经访问过的顶点，保证每个顶点值都被访问过一次

private boolean[] 标记；

//为每个连接的组件标记一个id

私有int[] id；

//连通分量的个数

私有整数计数；

公共CC(UndiGraph?graph) {

标记=new boolean[graph.vertexNum()];

id=new int[graph.vertexNum()];

for (int s=0; s graph.vertexNum(); s++) {

if (!marked[s]) {

dfs(图， s);

//一次dfs调用是一个连接组件，第一个连接组件id为0。

//后面分配的id会递增，第二个连通分量的id为1，以此类推。

计数++；

}

私有void dfs(UndiGraph?graph, int v) {

//为刚刚访问过的顶点设置标志

标记[v]=true；

id[v]=计数；

//从v的所有相邻顶点中选择一个未访问过的顶点

for (int w : graph.adj(v)) {

如果（！标记[w]）{

dfs（图，w）；

}

公共布尔连接（int v，int w）{

返回id[v]==id[w]；

}

公共int id(int v) {

返回id[v]；

}

公共int 计数（）{

返回计数；

}

公共静态无效主（字符串[] args）{

//边

int[][] 边={{0, 6}, {0, 2}, {0, 1}, {0, 5},

{3, 4}, {3, 5}, {4, 5}, {4, 6}, {7, 8},

{9, 10}, {9, 11}, {9, 12}, {11, 12}}；

UndiGraph?graph=new UndiGraph(13, 边);

CC cc=新CC(图);

//M 是连通分量的数量

int M=cc.count();

System.out.println(M + "连通分量");

LinkedList[] 组件=(LinkedList[]) new LinkedList[M];

for (int i=0; i M; i++) {

组件[i]=new LinkedList();

}

//将相同ID的顶点归属到同一个链表

for (int v=0; v graph.vertexNum(); v++) {

组件[cc.id(v)].add(v);

}

//打印每个连通分量中的顶点

for (int i=0; i M; i++) {

for (int v : 组件[i]) {

System.out.print(v+ " ");

}

System.out.println();

}

}程序会打印以下信息

3 个连接组件

0 1 2 3 4 5 6

7 8

9 10 11 12 对比上图，一模一样！

深度优先搜索的应用——判断无向图是否有环

DFS 可用于轻松判断无向图是否为环（假设不存在自环和平行边）。

包第7章；

公共类UndirectCycle {

私有布尔值标记[]；

私有布尔值hasCycle；

公共UndirectCycle(UndiGraph?graph) {

标记=new boolean[graph.vertexNum()];

for (int s=0; s graph.vertexNum(); s++) {

if (!marked[s]) {

//开始时还没有访问过任何顶点，所以将当前访问过的和最后访问过的顶点设置为起始点s。当递归调用一次dfs时，当前访问的参数v是s的邻接点，最后访问的参数u是s，符合

dfs(图， s, s);

}

//修改后的DFS，v表示当前访问的顶点，u表示最后访问的顶点

私有void dfs(UndiGraph?graph, int v, int u) {

//为刚刚访问过的顶点设置标志

标记[v]=true；

//从v的所有相邻顶点中选择一个未访问过的顶点

for (int w : graph.adj(v)) {

如果（！标记[w]）{

dfs(图， w, v);

} 否则如果(w !=u) {

已循环=真；

}

公共布尔hasCycle() {

返回hasCycle；

}

}DFS算法稍作修改，增加了一个新参数u，表示最后访问的顶点。判断是否存在环路的关键是else if(w !=u)这句话。请注意，w 和u 是进行比较的。为什么这样就能判断有环呢？如果当前访问的顶点v的这个邻接点w是之前已经访问过的，且不是上一个访问的顶点，那么该无向图就有环。就是下图所示的情况。

当imagew 被访问并且w==u 时，就没有循环。就是下图的情况

image

寻找有向图的强连通分量

在图片有向图中，如果两个顶点v 和w 彼此可达，则称它们是强连通的。如果有向图中任意两个顶点是强连通的，那么这个图也是强连通。

有向环与强连通性之间存在着密切的关系。两个顶点是强连通的当且仅当它们都在一个普通的有向环中。这个很容易理解。存在v -w 路径和w -v 路径。那么v和w是强连接的，这也意味着这是一个环结构。包含V 个顶点的有向图在[1, V] 范围内具有多个强连通分量。 —— 强连通图只有一个强连通分量，而有向无环图包含V 个强连通分量。

下图包含5 个强连通分量。

就像计算无向图中的连通分量一样，计算有向图的强连通分量也是深度优先搜索的应用。只需在上面的代码中添加几行即可实现这个名为Kosaraju 的算法。

虽然这个算法实现起来很简单，但是并不容易理解。 nullzx博客园的这篇博文非常好。看完之后我终于明白了Kosaraju算法的神奇方法……

上图是一个包含两个强连通分量的有向图。强连通分量和强连通分量之间不会形成环，否则这两个连通分量就是一个整体，即看成同一个强连通分量。如果连通分量减少到一个顶点，那么上图就是一个包含两个顶点的无环图，左边的顶点指向右边的顶点。

如果从左侧强连通分量中的任意顶点开始DFS，则只需一次调用即可访问图中的所有顶点。这主要是因为A2指向两个连通分量之间的B3；相反，从右边的强连通分量开始，从中的任意顶点开始深度优先搜索，需要调用DFS两次，——，这正是强连通分量的个数，以及每次访问的顶点调用DFS的是强连通分量中的所有顶点（假设这句话是正确的，下面会给出这个命题的证明），例如第一次调用DFS时，访问了B3、B4、B5 。这三个顶点恰好构成了右边强连通分量的所有顶点。反过来想一下，为了找出全部的强连通分量，保证DFS访问顶点的顺序为B强连通分量中任意一个顶点在A强连通分量全部顶点之前即可。或者换个角度想一下，将连通分量缩减为顶点后，整个图就变成了无环图。 DFS访问顶点的顺序是：首先访问那些不指向任何连通分量（顶点）的顶点，比如上面A2指向B3，那么应该先访问B中的顶点。更简单地说，DFS会首先访问那些出度为0的连通分量（视为顶点）。这保证了一次调用DFS肯定是在同一个连通分量里面递归，不会跑到其他连通分量中取。会首先访问那些指向其他分量的分量（出度不是0）。 0）。DFS必须能够进入其他连接的组件。例如，连通分量A 通过A2 进入连通分量B。这种情况下，DFS一次性遍历多个强连通分量，根本达不到目的。

例如，B3、A2、A0、A1、B4、B5。如果按照这个顺序调用DFS，就可以保证DFS会被调用两次。当然，该顺序并不唯一。 DFS中有一个通用的序列可以保证这种关系，即逆后序。

所谓倒序就是DFS递归调用返回之前，将该顶点压入栈中得到的序列。。例如dfs(s) -dfs(v)的递归调用栈就代表了一条s -v 的路径。 v 将在s 之前返回，因此首先存储v，然后存储s。堆栈中的顺序是sv。

现在我们可以谈谈Kosaraju算法的思想：

反转原始图像。对反向图进行深度优先遍历，以获得顶点的逆序。回到原始图像，按照上面得到的相反序列的顺序对原始图像进行深度优先搜索。（而不是按照0、1、2……等顶点的顺序）我们来看看为什么反向图的逆序就是我们需要的序列。

上图是反转的有向图。设原图像为G，反转图像为Gr。深度优先搜索Gr 有两种可能：

从强连通分量A中的任意顶点开始，需要调用DFS两次。 A0、A1、A2第一次入栈；第二次将B3、B4 和B5 压入堆栈。此时，强连通分量B的所有顶点都在强连通分量A之前。从强连通分量B中的任意顶点开始，只需调用一次DFS即可遍历所有顶点。因为是倒序，因为B中最先访问的顶点会最后返回，所以它位于栈顶。在上述两种情况下，B中至少有一个顶点在A全部顶点之前都是有保证的。返回原始图像时，首先对B中的顶点进行DFS。扩展到具有多个强连通分量的有向图，上述推论仍然有效。

逆图的逆序列实际上是一个伪拓扑序列（“伪”是因为它可能具有循环结构）。将连通分量减少到一个顶点后，有向图就变成了无环图。逆图的逆后序变为拓扑序列——。度数为0的顶点总是排在第一位。原图中该拓补序列就变成了出度为0的顶点排在前面了，如上分析，如果先对那些出度为0的分量（已视为顶点）进行DFS，则可以保证每次DFS访问的顶点都处于同一个强状态连接的组件。向下。

为了明确证明Kosaraju算法的正确性，我们需要证明这个命题：按照反向图的逆后序顺序在原图中进行DFS，每一次DFS中所访问的所有顶点都在同一个连通分量之中。上面说了这么多，但只是定性地解释了为什么使用逆图的逆序这样的序列可以达到目的。命题的后半部分.在上面的分析中我们假设它是正确的，实际上这个命题需要严格的证明，我们来证明在命题前半部分的前提下，句子的后半部分是正确的。

为了证明这个命题，有两点需要证明（以逆图的逆序进行DFS的前提下）：

与s 强连接的每个顶点v 都必须在调用dfs(G, s); 中被访问。 dfs(G, s) 到达的任何顶点v 都必须与s 强连接。第一点是用反证法：假设有一个顶点v在调用dfs(G, s)时没有被访问过，因为存在一条路径s -v，也就是说在调用dfs(G之前v已经被访问过了， s) 通过（否则与假设不一致）；又因为还有一条v -s的路径，所以调用dfs(G, v)后，s肯定会被标记为已访问，从而无法调用dfs(G, s)，这与我们假设dfs的前提相矛盾(G, s) 将被调用。所以原命题成立。

第二点是dfs(G, s)可以到达顶点v，说明存在一条路径s -v。要证明s和v是强连通的，我们只需要证明原图G中存在一条路径v -s即可。相当于在逆图Gr中找到一条路径s-v。由于深度优先搜索是逆序进行的，所以在Gr中dfs(Gr, v)一定是在dfs(Gr, s)之前返回的，否则逆后序就变成了[v, s]，原图在dfs调用时就会先调用dfs(G, v)，此时如果原图存在v -s的路径，那么dfs(G, v)被调用后，s会被标记已访问，从而dfs(G, s)不会被调用到——这和我们假设的前提dfs(G, s)会被调用且达到v顶点矛盾。中，Gr中的dfs(Gr, v)肯定会先于dfs(Gr, s)返回。有两种情况。

dfs(Gr, v) 在dfs(Gr, s) 之前调用，并且也在dfs(Gr, s) 调用结束之前结束。即dfs(Gr, v) 调用-dfs(Gr, v) 结束-dfs(Gr, s) 调用-dfs(Gr, s) 结束dfs(Gr, v) 在dfs(Gr, s) 之后调用，并在dfs(Gr, s) 调用结束之前结束。即dfs(Gr, s) 调用-dfs(Gr, v) 调用-dfs(Gr, v) 结束-dfs(Gr, s) 结束。第一种情况是不可能的。因为v -s 存在于Gr 中（并且s -v 存在于G 中），所以第一种情况的调用不会发生。第二种情况只是表明Gr中存在一条s-v路径。获取证据！

如下图，中图和右图分别对应了上面两种情况。

图片证明也证明应该给出代码。

包第7章；

导入java.util.LinkedList;

/**

* 在有向图中查找强连通分量

公开课KosarajuSCC {

//用于标记已经访问过的顶点，保证每个顶点值都被访问过一次

private boolean[] 标记；

//为每个连接的组件标记一个id

私有int[] id；

//连通分量的个数

私有整数计数；

公共KosarajuSCC(DiGraph?graph) {

标记=new boolean[graph.vertexNum()];

id=new int[graph.vertexNum()];

//将原图像G反转得到Gr

DFSorder 顺序=new DFSorder(graph.reverse());

//按照Gr的相反顺序进行dfs

for (int s : order.reversePost()) {

if (!marked[s]) {

dfs(图， s);

//一次dfs调用是一个连接组件，第一个连接组件id为0。

//后面分配的id会递增，第二个连通分量的id为1，以此类推。

计数++；

}

private void dfs(DiGraph?graph, int v) {

//为刚刚访问过的顶点设置标志

标记[v]=true；

id[v]=计数；

//从v的所有相邻顶点中选择一个未访问过的顶点

for (int w : graph.adj(v)) {

如果（！标记[w]）{

dfs（图，w）；

}

公共布尔强连接（int v，int w）{

返回id[v]==id[w]；

}

公共int id(int v) {

返回id[v]；

}

公共int 计数（）{

返回计数；

}

公共静态无效主（字符串[] args）{

//边

int[][] 边={{0, 1}, {0, 5}, {2, 3},{2, 0}, {3, 2},

{3, 5}、{4, 2}、{4, 3}、{4, 5}、{5, 4}、{6, 0}、{6, 4}、

{6, 9}, {7, 6}, {7, 8}, {8, 9},{8, 7}, {9, 10},

{9, 11}、{10, 12}、{11, 4}、{11, 12}、{12, 9}}；

有向图？图=新有向图（13，边）；

KosarajuSCC cc=新KosarajuSCC(图);

//M 是连通分量的数量

int M=cc.count();

System.out.println(M + "连通分量");

LinkedList[] 组件=(LinkedList[]) new LinkedList[M];

for (int i=0; i M; i++) {

组件[i]=new LinkedList();

}

//将相同ID的顶点归属到同一个链表

for (int v=0; v graph.vertexNum(); v++) {

组件[cc.id(v)].add(v);

}

//打印每个连通分量中的顶点

for (int i=0; i M; i++) {

for (int v : 组件[i]) {

System.out.print(v + " ");

}

System.out.println();

}

}针对具体的有向图，我们看一下Kosaraju算法的轨迹。左图是逆图上的DFS，逆序排列是伪拓扑序列；右图中，按照这个顺序对原图进行DFS，总共对5个顶点进行DFS。每个DFS 代表一个强连接组件（由盒子包围的一组顶点）。

[图片上传失败.(image-f58914-1510374691562)]

上面代码中的测试例子其实就是上图。它将打印以下信息

5 个连接组件

0 2 3 4 5

9 10 11 12

7 8 对比上框圈出的内容，确实是5个强连通分量。

顺便说一句，如果将图中的强连通分量减少到一个顶点，则可以得到下面的图。由于强连通分量与强连通分量之间不形成环路，因此逆序列是真正的拓扑序列。回到原来的有向图，顺着拓扑序列DFS（顺序为1,0,11,6,7）可以发现，算法总是优先选择出度为0的顶点，并删除该顶点执行DFS后。然后从剩下的图中选择度数为0的顶点继续DFS。

image我对这个算法的分析感到痛苦……如果你觉得麻烦，记住结论就可以了。

通过@sunhaiyu

OK，关于深入浅出：数据结构与算法解析与应用和的内容到此结束了，希望对大家有所帮助。