Cracking coding interview(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 = 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.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 :"+Graph1.isRouteBFS(2, 3));
		System.out.println("R<dfs>:"+Graph1.isRouteDFS(2, 3));
	}
}</dfs></integer></integer></integer></integer>