题目描述
对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。
给定图中的两个结点的指针DirectedGraphNode* a, DirectedGraphNode* b(请不要在意数据类型，图是有向图),请返回一个bool，代表两点之间是否存在一条路径(a到b或b到a)。
代码如下：
package com.yzh.hehe; import java.util.ArrayList;
import java.util.Stack; public class DirGraCheckPath { public static void main(String[] args) {
// TODO Auto-generated method stub } public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {
return checkSingle(a, b)||checkSingle(b, a);
} private boolean checkSingle(UndirectedGraphNode a, UndirectedGraphNode b) {
if (a.label==b.label) {
return true;
}
//深度优先遍历用堆栈实现（广度优先遍历用队列实现）
Stack<UndirectedGraphNode> stack= new Stack<UndirectedGraphNode>();
//已遍历的点
ArrayList<UndirectedGraphNode> list=new ArrayList<UndirectedGraphNode>();
list.add(a);
stack.addAll(a.neighbors);
UndirectedGraphNode temp = null;
//深度遍历一个点，看是否目标点，是结束，否则再将此点的连接点放入栈中等待遍历重复（入栈将连接点中已经在栈中和已遍历过的点去掉）。
while (!stack.isEmpty()) {
temp = stack.pop();
if (temp.label==b.label) {
return true;
}
for (UndirectedGraphNode undirectedGraphNode : temp.neighbors) {
if (!stack.contains(undirectedGraphNode)&&!list.contains(undirectedGraphNode)) {
stack.push(undirectedGraphNode);
}
}
list.add(temp);
}
return false;
} }
class UndirectedGraphNode {
int label = 0;
UndirectedGraphNode left = null;
UndirectedGraphNode right = null;
ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>(); public UndirectedGraphNode(int label) {
this.label = label;
}
}