1

我目前正在为大学做一个挑战，在那里我必须获得有向图（没有循环，没有多重边）的拓扑排序（如果它是 DAG）或获得强分量（如果它不是 DAG）。Tarjans 算法似乎是最好的，因为它以相反的拓扑顺序找到图的所有强分量。如果图是一个 DAG，它会找到所有顶点的逆拓扑排序，因为 DAG 中的每个顶点都是它自己的 SCC。问题是tarjans alg的拓扑类型。在 DAG 上并不总是适合标准顶部的那个。排序（问题末尾的那个）找到，这让我的大学提供的所有测试都失败了。

这方面的一个示例是具有 8 个顶点和以下边的 DAG 在此示例中为支架。最佳。排序算法。不会创建相同的顶部。排序为 tarjan alg。

0 -> 4

1 -> 6

2 -> 1

3 -> 1

5 -> 6

6 -> 4

7 -> 3

问题是是否有可能始终获得拓扑排序标准的顶部。sort 从修改后的 tarjan 返回以及该修改的外观。Tarjans O(v+e) 不应该通过修改来改变。

我知道我可以同时实现两者，但挑战在于性能，所以我更希望有一种算法可以同时实现。

我目前正在维基百科上使用 tarjans 实现 https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

这是立场。用于我的大学提供的测试的顶级排序算法

List L
foreach v ∈ V
    count[v] ← 0
foreach v ∈ V
    foreach Kante (v, w) ∈ E
        count[w] ← count[w]+1
foreach v ∈ V
    if count[v] = 0
       Add v at beginning of L
while L is not empty
    v ← first element in L
    delete v from L
    print v(or assign v and incrementing index)
    foreach Kante (v, w) ∈ E
        count[w] ← count[w]−1
        if count[w] = 0
            add w at the beginning of L

这个算法总是从顶点 0 开始。顶点它总是采用最低的 adj。首先是顶点（作为一个数字）。它会去 0 -> 1 然后 0-> 6

我希望你能帮助我，并提前谢谢你。

4

0 回答 0