Crackingcodinginterview(4.2)有向图判断任意2点之间是否有一

4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes. 1.图的存储使用邻接矩阵 2.使用邻接矩阵的过程中，必须给每个节点编号(0,1...) 3.可以写一个map函数给按一定规则所有节点编号(本例未实现) 4.alg

4.2 Given a directed graph, design an algorithm to find out whether

there is a route between two nodes.

1.图的存储使用邻接矩阵

2.使用邻接矩阵的过程中，必须给每个节点编号(0,1...)

3.可以写一个map函数给按一定规则所有节点编号(本例未实现)

4.algorithm:通过bfs或dfs遍历从其中一个节点开始遍历图，看是否对可达另一个节点。

import java.util.Queue;
import java.util.LinkedList;
import java.util.Stack;
//vertex in the graph must have serial number
//from 0 to n, if graph isn't suitable for this
//write map() to map.
//directed no-weight graph
class Graph1{
private static boolean[][] Matrix;
private static int vertexNum;
public static void generator(int[][] G, int vNum){
vertexNum = vNum;
Matrix = new boolean[vertexNum][vertexNum];
for(int i=0;i < G.length;i++){
Matrix[G[i][0]][G[i][1]] = true;
}
}
public static boolean isRouteDFS(int v1, int v2){
if(v1 < 0 || v2 < 0 || 
v1 >= Matrix.length || v2 >= Matrix.length)
return false;
boolean[] isVisited = new boolean[vertexNum];
Stack<integer> s = new Stack<integer>();
int v = -1;
if(v1 != v2){
s.push(v1);
isVisited[v1] = true;
} else
return true;
while(!s.empty()){
v = s.peek();//when v's all next node have been invisted, then pop
//
System.out.println("["+v+"]");//
boolean Marked = false;
for(int j=0;j < Matrix[v].length;j++)
if(Matrix[v][j] && !isVisited[j])
if(j == v2){
return true;
} else{
s.push(j);
isVisited[j] = true;
Marked = true;
break;
}
if(!Marked)
s.pop();
}
return false;
}
public static boolean isRouteBFS(int v1, int v2){
if(v1 < 0 || v2 < 0 || 
v1 >= Matrix.length || v2 >= Matrix.length)
return false;
boolean[] isVisited = new boolean[vertexNum];
Queue<integer> queue = new LinkedList<integer>();
int v = -1;
queue.offer(v1);
isVisited[v1] = true;
while(!queue.isEmpty()){
v = queue.poll();
if(v == v2)
return true;
for(int j = 0;j < Matrix[v].length;j++)
if(Matrix[v][j] == true && isVisited[j] == false)
queue.offer(j);
}
return false;
}
public static void printMatrix(){
for(int i=0;i < Matrix.length;i++){
System.out.print(i+": ");
for(int j=0;j < Matrix[i].length;j++)
System.out.print((Matrix[i][j] == true ? 1 : 0) + " ");
System.out.println();
}
}
}
public class Solution{
public static void main(String[] args){
int[][] G = {
{0, 1}, {0, 2},
{1, 3}, {1, 4},
{2, 4},
{4, 0}
};
Graph1.generator(G, 5);
Graph1.printMatrix();
System.out.println("R<bfs>:"+Graph1.isRouteBFS(2, 3));
System.out.println("R<dfs>:"+Graph1.isRouteDFS(2, 3));
}
}</dfs></bfs></integer></integer></integer></integer>