笃志以砺，决起而飞

有向图的强连通分量

深度优先遍历是求有向图的强连通分量的一个有效方法，具体求解步骤如下： ⑴ 在有向图中，从某个顶点出发进行深度优先遍历，并按其所有邻接点的访问都完成（即出栈）的顺序将顶点排列起来。 ⑵ 在该有向图中，从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成访问的那个顶点出发，继续作逆向的深度优先遍历，依次类推，直至有向图中所有顶点都被访问到为止。 ⑶ 每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集，若仅作一次逆向深度优先遍历就能访问到图的所有顶点，则该有向图是强连通图。 例如对图6-3(a)所示有向图，从顶点v1出发作深度优先遍历，在访问顶点v2后，顶点v2不存在未访问的邻接点从而成为一个“死结点”，如图(b) 所示。将v2从栈顶弹出后，再从顶点v1出发，在访问顶点v3 v4后，顶点v4不存在未访问的邻接点从而也成为“死结点”，如图(c)所示。将v4从栈顶弹出后，顶点v3不存在未访问的邻接点从而也成为“死结点”， 将v3从栈顶弹出后，顶点v1不存在未访问的邻接点从而也成为“死结点”，将v1从栈顶弹出，所以，得到出栈的顶点序列为v2, v4, v3, v1；再从最后一个出栈的顶点v1出发作逆向的深度优先遍历（逆着有向边的箭头方向），得到一个顶点集{ v1, v3, v4}，如图(d)所示；再从顶点v2出发作逆向的深度优先遍历，得到一个顶点集{v2}，如图(e)所示。这就是该有向图的两个强连通分量的顶点集。

欧拉回路 【定义】 图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。 具有欧拉回路的图称为欧拉图（简称E图）。 【相关结论】 定理： 一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数或只有两个定点的度数为奇。 一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。 求欧拉回路的一种解法 下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。 int num = 0;//标记输出队列 int match[MAX];//标志节点的度，无向图，不区分入度和出度 void solve(int x) { if(match[x] == 0)

Record[num++] = x;

else { for(int k =0;k<=500;k++) { if(Array[x][k] !=0 ) { Array[x][k]–; Array[k][x]–; match[x]–; match[k]–; solve(k); }

} Record[num++] = x; } } 注意record中的点的排列是输出的到序，因此，如果要输出欧拉路径，需要将record倒过来输出。 求欧拉回路的思路： 循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。 具体步骤： 1。如果此时与该点无相连的点，那么就加入路径中 2。如果该点有相连的点，那马就列一张表，遍历这些点，知道没有相连的点。 3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。 [...]