本文共 1125 字，大约阅读时间需要 3 分钟。

如果对于任意两个不同的顶点u和v，存在一个从u到v的有向路径以及从v到u的有向路径，这样的有向图被称为是强连通的。一般来说，一个有向图的顶点可以分割成一些互不相交的最大子集，每个子集的顶点之间可以通过有向图中的有向路径相互访问，这些子集被称为强连通分量。

下面三步说的顶点变成死端是递归的dfs出栈的顺序。

第一步：对给定的有向图执行一次DFS遍历，然后按照顶点变成死端的顺序对它们进行编号。

邻接表

package d;public class AGraph {   int n,e;VNode adjlist[];public AGraph(int n) {   	super();	this.n = n;	adjlist=new VNode[n];}}package d;class ArcNode{   int adjvex;  ArcNode nextarc;ArcNode reverse_nextarc;public ArcNode() {   } public ArcNode (int adjvex){   this.adjvex=adjvex;};}package d;class VNode{   //邻接矩阵的顶点也可以用这个ArcNode firstarc;ArcNode reverse_firstarc;int Serial_number;//DFS访问后按照死端编号char info; public VNode(char info) {   this.info = info;}public VNode() {   	super();}}

主程序

package d;import java.util.Comparator;class Mycomparator implements Comparator
   
    {   	public int compare(VNode v1,VNode v2)	{   		int a=v1.Serial_number;		int b=v2.Serial_number;		if (a>b)		{   			return -1;//按照这种方式排序		}		else if (a
    
      cmp=new Mycomparator();		Arrays.sort(a.adjlist,cmp);		for (int i=0;i