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.<mark>来源gaodaimacom搞#^代%!码网</mark>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 graphclass 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 = 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 = 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));	}}

喜欢 (0)赏

[搞代码]

分享 (0)