Graph: Topological Sort

ShevaKuilin 發(fā)布于2019-08-14 15:01 / 2968人閱讀

Graph: Topological Sort

利用和detect cycle類似的思路，用dfs + recursion解決。并且一定時一個有向圖。

Stack stack = new Stack<>();
// 0:unvisit, 1:visited, 2:visiting
public boolean topologicalSort(Node node) {
    if(node.state = 2) return true;
    node.state = 2;
    if(map.get(node) != null) {
        for(Node adj : map.get(node)) {
            if(adj.state != 1 && topologicalSort(adj)) {
                return true;
            }
        }
    }
    node.state = 1;
    stack.push(node.val);
    return false;
}

云服務器 GPU云服務器 topological-sort Topological graph graph編程語言

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/65232.html

[LintCode] Topological Sorting [BFS & DFS]

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

摘要：復雜度思路重建，應為要按進行排序，所以用來決定下一個要出去的值。 Leetcode[332] Reconstruct Itinerary Given a list of airline tickets represented by pairs of departure andarrival airports [from, to], reconstruct the itinerary ...

Flands 2019-08-14 15:57 評論0 收藏0
[Leetcode] Alien Dictionary 外文字典

摘要：拓撲排序復雜度時間空間思路首先簡單介紹一下拓撲排序，這是一個能夠找出有向無環(huán)圖順序的一個方法假設我們有條邊，先將每個節(jié)點的計數(shù)器初始化為。最后，我們開始拓撲排序，從計數(shù)器為的字母開始廣度優(yōu)先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...

pkhope 2019-08-14 12:38 評論0 收藏0
算法（第4版） Chapter 4.2 有向圖

摘要：只好特地拎出來記錄證明一下算法步驟第一步在逆圖上運行，將頂點按照逆后序方式壓入棧中顯然，這個過程作用在有向無環(huán)圖上得到的就是一個拓撲排序作用在非上得到的是一個偽拓撲排序第二步在原圖上按第一步的編號順序進行。等價于已知在逆圖中存在有向路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...

曹金海 2019-08-14 17:13 評論0 收藏0
算法（第4版） Chapter 4.4 最短路徑

摘要：相關操作就是判斷的不等號符號改反，初始值設為負無窮副本的最短路徑即為原圖的最長路徑。方法是同上面一樣構(gòu)造圖，同時會添加負權(quán)重邊，再將所有邊取反，然后求最短路徑最短路徑存在則可行沒有負權(quán)重環(huán)就是可行的調(diào)度。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter ...

leap_frog 2019-08-14 17:16 評論0 收藏0