证实也证清楚明了，代码该给出了。

package Chap7; 
 
import java.util.LinkedList; 
 
/** 
 * 寻找有向图中的强连通分量 
 */ 
public class KosarajuSCC { 
    // 用来标记已经拜访过的顶点，包管每个顶点值拜访一次 
    private boolean[] marked; 
    // 为每个连通分量标示一个id 
    private int[] id; 
    // 连通分量的个数 
    private int count; 
 
    public KosarajuSCC(DiGraph<?> graph) { 
        marked = new boolean[graph.vertexNum()]; 
        id = new int[graph.vertexNum()]; 
        // 对原图G取反获得Gr 
        DFSorder order = new DFSorder(graph.reverse()); 
        // 按Gr的逆后序进行dfs 
        for (int s : order.reversePost()) { 
            if (!marked[s]) { 
                dfs(graph, s); 
                // 一次dfs调用就是一个连通分量，第一个连通分量id为0。 
                // 之后分派的id要自增，第二个连通分量的id为1，以词攀类推 
                count++; 
            } 
        } 
    } 
 
    private void dfs(DiGraph<?> graph, int v) { 
        // 将刚拜访到的顶点设置标记 
        marked[v] = true; 
        id[v] = count; 
        // 大年夜v的所有邻居点中选择一个没有被拜访过的顶点 
        for (int w : graph.adj(v)) { 
            if (!marked[w]) { 
                dfs(graph, w); 
            } 
        } 
	
			
 6/8   首页 上一页 4 5 6 7 8 下一页 尾页
	
			

　　推荐阅读
　　40岁的IT巨人微软 究竟是什么在支撑着它继续前进？
            Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践
            上周，微软颁布了其2018财年第一季度的财报。毫无不测埠，微软在这一季度大年夜赚了一笔。微软颁布财报后>>>详细阅读


本文标题：数据结构与算法–图论之寻找连通分量、强连通分量
地址：http://www.17bianji.com/lsqh/38858.html
 1/2    1