(a) 可以用图中的每一个顶点表示街道中的每个十字路口，由于街道都是单行的，所以图是有向图，若从一个十字路口都有一条合法的路线到另一个十字路口,则图是一个强连通图。即要验证的是图是否是一个强连通图。
(b) 若从市政厅沿着合法路线到达任何一个地方都有合法路线返回则说明市政厅位于一个有向图中的一个汇点强连通部件中。
1 package org.xiu68.ch03.ex11; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Stack; 6 7 public class Ex3_15 { 8 9 public static void main(String[] args) { 10 // TODO Auto-generated method stub 11 int[][] edges=new int[][]{ 12 {0,1,0,0}, 13 {0,0,1,0}, 14 {0,0,0,1}, 15 {1,0,0,0} 16 }; 17 MGraph1 m1=new MGraph1(edges); 18 m1.checkSC(0); //强连通图 19 20 System.out.println("***************************"); 21 int[][] edges1=new int[][]{ 22 {0,1,0,1}, 23 {0,0,1,0}, 24 {0,0,0,1}, 25 {0,0,0,0} 26 }; 27 MGraph1 m2=new MGraph1(edges1); 28 m2.checkSC(0); 29 for(int i=0;i<4;i++){ 30 System.out.print(i+":"); 31 m2.isInSinkSCC(i); 32 } 33 //输出 34 /* 35 非强连通图 36 0:不存在汇点强连通分量中 37 1:不存在汇点强连通分量中 38 2:不存在汇点强连通分量中 39 3:存在汇点强连通分量中 40 */ 41 42 System.out.println("***************************"); 43 int[][] edges3=new int[][]{ 44 {0,0,0,0,0,0,0}, 45 {1,0,0,1,0,0,0}, 46 {1,0,0,1,0,0,0}, 47 {0,0,0,0,1,1,0}, 48 {0,0,0,1,0,0,1}, 49 {0,0,0,1,0,0,1}, 50 {0,0,0,0,1,1,0} 51 }; 52 MGraph1 m3=new MGraph1(edges3); 53 for(int i=0;i<edges3.length;i++){ 54 System.out.print(i+":"); 55 m3.isInSinkSCC(i); 56 } 57 //输出 58 /* 59 0:存在汇点强连通分量中 60 1:不存在汇点强连通分量中 61 2:不存在汇点强连通分量中 62 3:存在汇点强连通分量中 63 4:存在汇点强连通分量中 64 5:存在汇点强连通分量中 65 6:存在汇点强连通分量中 66 */ 67 } 68 69 } 70 71 72 class MGraph1{ 73 private int[][] edges; //有向图 74 private int[][] rEdges; //有向图的反向图 75 private int vexNum; //顶点数量 76 private Stack<Integer> stack; //存储反向图深度优先遍历的post值 77 78 public MGraph1(int[][] edges){ 79 this.edges=edges; 80 this.vexNum=edges.length; 81 stack=new Stack<>(); 82 rEdges=new int[vexNum][vexNum]; //反向图 83 84 //求原图的反向图 85 for(int i=0;i<vexNum;i++){ 86 for(int j=i+1;j<vexNum;j++){ 87 rEdges[i][j]=edges[j][i]; 88 rEdges[j][i]=edges[i][j]; 89 } 90 } 91 92 } 93 //****************************************************** 94 //验证图是否是强连通的 95 /* 96 * 先从某个顶点开始对原图进行深度优先遍历 97 * 再从这个顶点开始对反向图做深度优先遍历 98 * 若两次遍历都能访问所有顶点说明是强连通图 99 */ 100 public void checkSC(int v){ 101 boolean[] visited=new boolean[vexNum]; //原图中已访问的顶点 102 dfs(edges,visited,v); 103 104 boolean[] rVisited=new boolean[vexNum]; //反向图中已访问的顶点 105 dfs(rEdges,rVisited,v); 106 107 for(int i=0;i<vexNum;i++){ 108 if(!visited[i] || !rVisited[i]){ 109 System.out.println("非强连通图"); 110 return; 111 } 112 } 113 System.out.println("强连通图"); 114 } 115 116 //深度优先遍历 117 public void dfs(int[][] edges,boolean[] visited,int v){ 118 visited[v]=true; 119 for(int i=0;i<vexNum;i++){ 120 if(edges[v][i]==1 && !visited[i]){ 121 dfs(edges,visited,i); 122 } 123 } 124 } 125 //************************************************************** 126 //判断一个顶点是否位于一个汇点强连通部件中 127 public void isInSinkSCC(int target){ 128 rDFSTraverse(); //先对反向图进行深度优先遍历 129 130 //List<List<Integer>> sccs=new ArrayList<>(); //存放每一个强连通部件对应的顶点 131 132 boolean[] visited=new boolean[vexNum]; //记录深度优先遍历原图过程中非当前强连通分量已经访问的顶点 133 int[] visitedN=new int[vexNum]; //记录顶点属于第几个强连通分量 134 boolean[] isSinkSCC=new boolean[vexNum]; //记录第i个强连通分量是否是汇点强连通部件，最多有vexNum个强连通部件 135 int n=0; //第几个强连通部件 136 137 for(int i=0;i<vexNum;i++){ 138 visitedN[i]=-1; 139 isSinkSCC[i]=true; 140 } 141 142 while(!stack.isEmpty()){ 143 int v=stack.pop(); 144 if(!visited[v]){ 145 //sccs.add(new ArrayList<Integer>()); 146 List<Integer> vexs=new ArrayList<>(); //记录第n个强连通分量的顶点 147 148 DFS(visited,visitedN,v,vexs,isSinkSCC,n); 149 for(int i=0;i<vexs.size();i++){ 150 //sccs.get(i).add(vexs.get(i)); 151 visited[vexs.get(i)]=true; 152 } 153 n++; 154 } 155 } 156 if(isSinkSCC[visitedN[target]]){ 157 System.out.println("存在汇点强连通分量中"); 158 }else{ 159 System.out.println("不存在汇点强连通分量中"); 160 } 161 } 162 /* 163 * 对原图进行深度优先遍历 164 * 在汇点强连通部件中对某个顶点进行深度优先遍历则刚好访问该强连通部件的所有顶点 165 */ 166 private void DFS(boolean[] visited,int[] visitedN,int v,/*List<List<Integer>> sccs,*/ 167 List<Integer> vexs,boolean[] isSinkSCC,int n){ 168 //sccs.get(n).add(v); 169 vexs.add(v); 170 visitedN[v]=n; 171 for(int i=0;i<vexNum;i++){ 172 if(edges[v][i]==1){ 173 //若在一个汇点强连通部件中进行深度优先遍历,刚好得到该汇点强连通部件 174 //若遍历到其他强连通分量的顶点说明该强连通分量不是汇点强连通分量 175 if(visited[i]){ 176 isSinkSCC[n]=false; 177 }else if(visitedN[i]!=n){ 178 DFS(visited,visitedN,i,/*sccs,*/vexs,isSinkSCC,n); 179 } 180 } 181 }//for 182 } 183 184 //************************************************************** 185 /* 186 * 对反向图进行深度优先遍历,post值最大的顶点将位于反向图中的一个源点强连通部件， 187 * 也就是原图中的某个汇点连通部件的某个顶点 188 * 按post值从小到大,压入栈中 189 */ 190 public void rDFSTraverse(){ 191 boolean[] visited=new boolean[vexNum]; 192 for(int i=0;i<vexNum;i++){ 193 if(!visited[i]){ 194 rDFS(visited,stack,i); 195 } 196 } 197 } 198 //对反向图做深度优先遍历 199 private void rDFS(boolean[] visited,Stack<Integer> stack,int v){ 200 visited[v]=true; 201 for(int i=0;i<vexNum;i++){ 202 if(rEdges[v][i]==1 && !visited[i]){ 203 rDFS(visited,stack,i); 204 } 205 } 206 stack.push(v); 207 } 208 }