Graph: Topological Sort

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

Graph: Topological Sort

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

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;
}

云服務(wù)器 GPU云服務(wù)器 topological-sort Topological graph graph編程語言

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

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

相關(guān)文章

[LintCode] Topological Sorting [BFS & DFS]

摘要：當(dāng)隊(duì)列非空時(shí)，拿出最后放入的元素。若減后入度為，則這個(gè)結(jié)點(diǎn)遍歷完成，放入結(jié)果數(shù)組和隊(duì)列。遞歸函數(shù)去遍歷的，繼續(xù)在中標(biāo)記，使得所有點(diǎn)只遍歷一次。最深的點(diǎn)最先，根結(jié)點(diǎn)最后，加入結(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

摘要：復(fù)雜度思路重建，應(yīng)為要按進(jìn)行排序，所以用來決定下一個(gè)要出去的值。 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 外文字典

摘要：拓?fù)渑判驈?fù)雜度時(shí)間空間思路首先簡單介紹一下拓?fù)渑判颍@是一個(gè)能夠找出有向無環(huán)圖順序的一個(gè)方法假設(shè)我們有條邊，先將每個(gè)節(jié)點(diǎn)的計(jì)數(shù)器初始化為。最后，我們開始拓?fù)渑判?，從?jì)數(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 有向圖

摘要：只好特地拎出來記錄證明一下算法步驟第一步在逆圖上運(yùn)行，將頂點(diǎn)按照逆后序方式壓入棧中顯然，這個(gè)過程作用在有向無環(huán)圖上得到的就是一個(gè)拓?fù)渑判蜃饔迷诜巧系玫降氖且粋€(gè)偽拓?fù)渑判虻诙皆谠瓐D上按第一步的編號順序進(jìn)行。等價(jià)于已知在逆圖中存在有向路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...

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

摘要：相關(guān)操作就是判斷的不等號符號改反，初始值設(shè)為負(fù)無窮副本的最短路徑即為原圖的最長路徑。方法是同上面一樣構(gòu)造圖，同時(shí)會添加負(fù)權(quán)重邊，再將所有邊取反，然后求最短路徑最短路徑存在則可行沒有負(fù)權(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