<strike id="ski2q"></strike>

<abbr id="ski2q"></abbr>

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

187J3X1 發(fā)布于2019-08-14 15:21 / 1333人閱讀

摘要：若為有向圖的終點，經過下一次，會指向，返回否則，只要所有的深度搜索中包含滿足條件的結果，就返回。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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]

摘要：當隊列非空時，拿出最后放入的元素。若減后入度為，則這個結點遍歷完成，放入結果數(shù)組和隊列。遞歸函數(shù)去遍歷的，繼續(xù)在中標記，使得所有點只遍歷一次。最深的點最先，根結點最后，加入結果數(shù)組的頭部處。 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