[LintCode] Route Between Two Nodes in Graph [DFS/B

187J3X1 发布于2019-08-14 15:21 / 1316人阅读

摘要：若为有向图的终点，经过下一次，会指向，返回否则，只要所有的深度搜索中包含满足条件的结果，就返回。

Problem

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Example

Given graph:

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

for s = B and t = E, return true
for s = D and t = C, return false

Note

若s为有向图的终点，经过下一次dfs，会指向null，返回false；否则，只要s所有neighbors的深度搜索中包含满足条件的结果，就返回true。

Solution

public class Solution {
    public boolean hasRoute(ArrayList graph, 
                            DirectedGraphNode s, DirectedGraphNode t) {
        Set visited = new HashSet();
        return dfs(s, t, visited);
    }
    public boolean dfs(DirectedGraphNode s, DirectedGraphNode t, Set visited) {
        if (s == null) return false;
        if (s == t) return true;
        visited.add(s);
        for (DirectedGraphNode next: s.neighbors) {
            if (visited.contains(next)) continue;
            if (dfs(next, t, visited)) return true;
        }
        return false;
    }
}

BFS

public class Solution {
   public boolean hasRoute(ArrayList graph, DirectedGraphNode s, DirectedGraphNode t) {
        if (s == t) return true;
        Deque q = new ArrayDeque<>();
        q.offer(s);
        Set visited = new HashSet<>();
        while (!q.isEmpty()) {
            DirectedGraphNode node = q.poll();
            visited.add(node);
            if (node == t) return true;
            for (DirectedGraphNode child : node.neighbors) {
                if (!visited.contains(child)) q.offer(child);
            }
        }
        return false;
    }
}

云服务器 GPU云服务器 Nodes graph LintCode between

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65668.html

[LintCode] Minimum Absolute Difference in BST

Problem Minimum Absolute Difference in BSTGiven a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example Input: 1 3 ...

curlyCheng 2019-08-16 12:36 评论0 收藏0
[LeetCode] 785. Is Graph Bipartite?

Problem Given an undirected graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B such that every ed...

godlong_X 2019-08-16 13:46 评论0 收藏0
[LeetCode] 684. Redundant Connection

Problem In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one...

lncwwn 2019-08-16 13:55 评论0 收藏0
[LintCode] Swap Two Nodes in Linked List

摘要：建立结点，指向可能要对进行操作。找到值为和的结点设为，的前结点若和其中之一为，则和其中之一也一定为，返回头结点即可。正式建立，，以及对应的结点，，然后先分析和是相邻结点的两种情况是的前结点，或是的前结点再分析非相邻结点的一般情况。 Problem Given a linked list and two values v1 and v2. Swap the two nodes in th...

wua_wua2012 2019-08-14 14:41 评论0 收藏0
[LintCode] Topological Sorting [BFS & DFS]

摘要：当队列非空时，拿出最后放入的元素。若减后入度为，则这个结点遍历完成，放入结果数组和队列。递归函数去遍历的，继续在中标记，使得所有点只遍历一次。最深的点最先，根结点最后，加入结果数组的头部处。 Problem Given an directed graph, a topological order of the graph nodes is defined as follow: For ...

draveness 2019-08-14 15:24 评论0 收藏0