Graph: Topological Sort

ShevaKuilin 发布于2019-08-14 15:01 / 2953人阅读

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编程语言

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

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

[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
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 外文字典

摘要：拓扑排序复杂度时间空间思路首先简单介绍一下拓扑排序，这是一个能够找出有向无环图顺序的一个方法假设我们有条边，先将每个节点的计数器初始化为。最后，我们开始拓扑排序，从计数器为的字母开始广度优先搜索。 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 有向图

摘要：只好特地拎出来记录证明一下算法步骤第一步在逆图上运行，将顶点按照逆后序方式压入栈中显然，这个过程作用在有向无环图上得到的就是一个拓扑排序作用在非上得到的是一个伪拓扑排序第二步在原图上按第一步的编号顺序进行。等价于已知在逆图中存在有向路径。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...

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

摘要：相关操作就是判断的不等号符号改反，初始值设为负无穷副本的最短路径即为原图的最长路径。方法是同上面一样构造图，同时会添加负权重边，再将所有边取反，然后求最短路径最短路径存在则可行没有负权重环就是可行的调度。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter ...

leap_frog 2019-08-14 17:16 评论0 收藏0