标签: kosaraju-algorithm

有一个著名的算法来寻找强连通分量Kosaraju's algorithm，它使用两个 DFS 来解决这个问题，并且?(|V| + |E|)及时运行。

首先，我们在图 ( G^R ) 的补上使用 DFS来计算顶点的逆后序，然后我们G通过以逆后序取顶点来计算强连通分量，在主图上应用第二个 DFS 。

虽然我了解算法的机制，但我没有得到反向后序需求背后的直觉。

它如何帮助第二个 DFS 找到强连接组件？

谁能解释一下 Kosaraju\xe2\x80\x99s 查找连通分量算法背后的逻辑？

我已阅读说明，但我无法理解反转图上的 DFS 如何检测强连通分量的数量。

def dfs(visited, stack, adj, x):\n    visited[x] = 1\n\n    for neighbor in adj[x]:\n        if (visited[neighbor]==0):\n            dfs(visited, stack, adj, neighbor)\n\n    stack.insert(0, x)\n    return stack, visited\n\ndef reverse_dfs(visited, adj, x, cc):\n    visited[x] = 1\n\n    for neighbor in adj[x]:\n        if (visited[neighbor]==0):\n            cc += 1\n            reverse_dfs(visited, adj, neighbor,cc)\n    print(x)\n    return cc\n\n\ndef reverse_graph(adj):\n    vertex_num = len(adj)\n    new_adj = [ [] for _ in range(vertex_num)]\n    for i in range(vertex_num):\n        for j in adj[i]:\n            new_adj[j].append(i)\n    return new_adj\n\n\ndef find_post_order(adj):\n    vertex_num …

我正试图在大图上实施Kosaraju的算法作为任务的一部分[MOOC Algo I Stanford on Coursera]

https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

当前代码适用于小图,但我在运行时执行期间遇到了Stack Overflow.

尽管已经阅读了F#中的Expert相关章节,或者网站上的其他可用示例和SO,我仍然没有得到如何使用continuation来解决这个问题

下面是通用的完整代码,但在执行DFSLoop1和递归函数DFSsub时它已经失败了.我认为我没有使函数tail递归[因为指令

t<-t+1
G.[n].finishingtime <- t

？]

但我不明白我如何正确实施延续.

当仅考虑失败的部分时,DFSLoop1将我们将应用深度优先搜索的图形作为参数.我们需要记录完成时间作为算法的一部分,以便在第二个DFS循环(DFSLoop2)中进入算法的第二部分[当然我们在此之前就失败了].

open System
open System.Collections.Generic
open System.IO

let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford I\PA 4 - SCC.txt";;
// let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford I\PA 4 - test1.txt";;
// val x : string [] =

let splitAtTab (text:string)=
    text.Split [|'\t';' '|]

let splitIntoKeyValue (A: int[]) = 
    (A.[0], A.[1])

let parseLine (line:string)=
    line
    |> splitAtTab
    |> Array.filter (fun s -> not(s=""))
    |> …