lintcode 图中两个点之间的路线广度优先搜索

野性酷女 2022-07-15 00:12 23阅读 0赞

####  图中两个点之间的路线 ####

*  [ 描述][Link 1]
 *  [ 笔记][Link 2]
 *  [ 数据][Link 3]
 *  [ 评测][Link 4]

给出一张有向图，设计一个算法判断两个点 `s` 与 `t` 之间是否存在路线。

您在真实的面试中是否遇到过这个题？

Yes

样例

如下图:

A----->B----->C
     \     |
      \    |
       \   |
        \  v
         ->D----->E

for `s = B` and `t = E`, return `true`

for `s = D` and `t = C`, return `false`

/**
     * Definition for Directed graph.
     * class DirectedGraphNode {
     *     int label;
     *     ArrayList<DirectedGraphNode> neighbors;
     *     DirectedGraphNode(int x) {
     *         label = x;
     *         neighbors = new ArrayList<DirectedGraphNode>();
     *     }
     * };
     */
    public class Solution {
       /**
         * @param graph: A list of Directed graph node
         * @param s: the starting Directed graph node
         * @param t: the terminal Directed graph node
         * @return: a boolean value
         */
        public boolean hasRoute(ArrayList<DirectedGraphNode> graph, 
                                DirectedGraphNode s, DirectedGraphNode t) {
            // write your code here
            if(s == t){
                return true;
            }
            Queue<DirectedGraphNode> queue = new LinkedList<>();
            Set<DirectedGraphNode> set = new HashSet<>();
            
            queue.offer(s);
            set.add(s);
            while(!queue.isEmpty()){
                DirectedGraphNode node = queue.poll();
                for(int i= 0 ; i< node.neighbors.size(); i++){
                    if(set.contains(node.neighbors.get(i))){
                        continue;
                    }
                    queue.offer(node.neighbors.get(i));
                    set.add(node.neighbors.get(i));
                    if(node.neighbors.get(i) == t)return true;
                }
            }
            return false;
        }
    }

[Link 1]: http://www.lintcode.com/zh-cn/problem/route-between-two-nodes-in-graph/#description
[Link 2]: http://www.lintcode.com/zh-cn/problem/route-between-two-nodes-in-graph/#note
[Link 3]: http://www.lintcode.com/zh-cn/problem/route-between-two-nodes-in-graph/#testcase
[Link 4]: http://www.lintcode.com/zh-cn/problem/route-between-two-nodes-in-graph/#judge