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 s = new Stack();
		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 queue = new LinkedList();
		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:"+Graph1.isRouteBFS(2, 3));
		System.out.println("R:"+Graph1.isRouteDFS(2, 3));
	}
}