[LintCode] Topological Sorting [BFS & DFS]

draveness 發布于2019-08-14 15:24 / 2881人閱讀

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

Problem

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.

Notice

You can assume that there is at least one topological order in the graph.

Example

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

Challenge

Can you do it in both BFS and DFS?

Note

先看BFS的做法：
建立哈希表map，存儲graph中所有neighbors結點的入度。
然后建立空的隊列q，將所有非依賴結點（如例子中的0結點，沒有其它元素指向它，也可以理解為根節點）放入隊列q和結果數組res。
當隊列q非空時，拿出q最后放入的元素cur。然后遍歷cur的所有neighbors結點neighbor，并將遍歷后的neighbor入度減1。若減1后入度為0，則這個結點遍歷完成，放入結果數組res和隊列q。

再看DFS的做法：
建立HashSet visited，標記遍歷過的點node。遞歸dfs函數去遍歷node的neighbors，繼續在visited中標記，使得所有點只遍歷一次。
最深的點最先，根結點最后，加入結果數組res的頭部（index = 0處）。

Solution

BFS

public class Solution {
    public ArrayList topSort(ArrayList graph) {
        ArrayList res = new ArrayList<>();
        Queue queue = new LinkedList<>();
        Map map = new HashMap<>();
        //把除了頭結點外的結點放入map
        for (DirectedGraphNode n: graph) {
            for (DirectedGraphNode node: n.neighbors) {
                if (!map.containsKey(node)) map.put(node, 1);
                else map.put(node, map.get(node)+1);
            }
        }
        //找到頭結點，放入queue和結果數組res
        for (DirectedGraphNode n: graph) {
            if (!map.containsKey(n)) {
                queue.offer(n);
                res.add(n);
            }
        }
        //對queue中的結點的neighbors進行BFS（入度減1），當neighbor的入度減小為0，放入queue和結果數組res
        while (!queue.isEmpty()) {
            DirectedGraphNode n = queue.poll();
            for (DirectedGraphNode node: n.neighbors) {
                map.put(node, map.get(node)-1);
                if (map.get(node) == 0) {
                    res.add(node);
                    queue.offer(node);
                }
            }
        }
        return res;
    }
}

DFS Recursion

public class Solution {
    public ArrayList topSort(ArrayList graph) {
        ArrayList res = new ArrayList();
        Set visited = new HashSet();
        for (DirectedGraphNode node: graph) {
            if (!visited.contains(node)) {
                dfs(node, visited, res);
            }
        }
        return res;
    }
    public void dfs(DirectedGraphNode node, Set visited, List res) {
        visited.add(node);
        for (DirectedGraphNode n: node.neighbors) {
            if (!visited.contains(n)) dfs(n, visited, res);
        }
        res.add(0, node);
    }
}

GPU云服務器云服務器 Sorting Topological BFS LintCode

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65740.html

[LintCode/LeetCode] Clone Graph [BFS/DFS]

摘要：開始看這道題目的時候，沒有看懂和的作用。然后對這個放入的結點開始操作遍歷的所有，當前遍歷到的的叫做。當完成，則中沒有新的結點了，退出循環。返回在中更新過的，結束。 Problem Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. We use #...

fredshare 2019-08-14 15:23 評論0 收藏0
DOM樹遍歷之JS實現DFS&amp;BFS

摘要：對于上面例子遍歷結果應為則總是先遍歷當前層級的所有節點，只有當當前層級所有節點都遍歷結束后才會進入下一層級。我們一般可以采用DFS（深度優先遍歷）和BFS（廣度優先遍歷）來遍歷DOM樹介紹 DFS & BFS 我們來結合具體例子進行分析，給出HTML代碼片段如下： DFS總是先進入下一...

imccl 2019-08-20 15:52 評論0 收藏0
DOM樹遍歷之JS實現DFS&amp;BFS

摘要：對于上面例子遍歷結果應為則總是先遍歷當前層級的所有節點，只有當當前層級所有節點都遍歷結束后才會進入下一層級。我們一般可以采用DFS（深度優先遍歷）和BFS（廣度優先遍歷）來遍歷DOM樹介紹 DFS & BFS 我們來結合具體例子進行分析，給出HTML代碼片段如下： DFS總是先進入下一...

fengxiuping 2019-08-01 16:40 評論0 收藏0
js版本的BFS&amp;DFS

摘要：隊列棧隊列是先進先出，后進后出，常用的操作是取第一個元素尾部加入一個元素。棧是后進先出，就像一個垃圾桶，后入的垃圾先被倒出來。遍歷中間過程，每一個節點入棧的時候是灰色的，出棧的時候是黑色的。 0. 前言廣度優先搜索(BFS)和深度優先搜索(DFS)，大家可能在oj上見過，各種求路徑、最短路徑、最優方法、組合等等。于是，我們不妨動手試一下js版本怎么玩。 1.隊列、棧隊列是先進先出，...

劉福 2019-08-22 16:49 評論0 收藏0
[LintCode] Route Between Two Nodes in Graph [DFS/B

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

187J3X1 2019-08-14 15:21 評論0 收藏0