《程序员面试金典》中的一道题

题目描述

对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。

给定图中的两个结点的指针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 ;

}