《程序员面试金典》中的一道题
题目描述
对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。
给定图中的两个结点的指针DirectedGraphNode* a, DirectedGraphNode* b(请不要在意数据类型，图是有向图),请返回一个bool，代表两点之间是否存在一条路径(a到b或b到a)。
java代码
有向图的节点
public class UndirectedGraphNode {
int label =0;
UndirectedGraphNodeleft =null;
UndirectedGraphNoderight =null;
ArrayListneighbors =new ArrayList();
public UndirectedGraphNode(int label) {
this.label = label;
}
}
思路：
有向图检索有两种方式——深度优先、广度优先。这个检查用到的是深度优先查询，首先解决的问题是如何记录节点被访问了，这里采用了Set集合。
public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {
if (a ==null || b ==null){
return false ;
}
Set set =new HashSet<>();
boolean res = checkPath(a, b, set);
set.clear();
return res || checkPath(b, a,set);
}
private boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b, Set set) {
if (a == b){
return true ;
}
set.add(a);
for (int i=0 ; i<a.neighboors.size() ; i++)
if (!set.contains(a.neighbors.get(i)) && checkPath(a.neighbors.get(i),b,set)){
//如果不包含这个节点且能连接到b点
return true ;
}
}
return false ;
}
