查找圖中斷開連接的節點的算法

我正在尋找一種方式，給定有向圖，以查找從給定起點無法到達的所有節點。基於與Dijkstra算法類似的概念，我已經有了一個想法，就像這樣（僞代碼），但有沒有更好的方法？查找圖中斷開連接的節點的算法

function DisconnectedNodes(Graph, Start) 
    var Unknown = new list 
    var Open = new list 
    var Closed = new list 
    for each Node in Graph 
    Unknown.add(Node) 
    Open.StealFrom(Unknown, Start) 
    while Open.Count > 0 
    var Current = Open[0] 
    for each Node in Current.Destinations 
     if Node in Unknown 
     Open.StealFrom(Unknown, Node) 
    Closed.StealFrom(Open, Current) 
    return Unknown

來源

2012-11-25 Mason Wheeler

剛剛從起始節點運行一個breadth-first search！從起點無法到達BFS之後未訪問的所有節點。

來源

2012-11-25 00:07:42 Haile

這裏描述的算法看起來基本上與我給出的算法類似，除了它有一個「目標」節點和圖的隱式根。 –

是的。我沒有注意到，它有點毛茸茸的。 * StealFrom *做什麼？此外，這是一個非常知名的算法，而且是您任務的標準。請問爲什麼你需要另一種方法？ – Haile

它將一個項目從一個列表移動到另一個列表。我不需要「另一種方法」，我只是想弄清楚它應該如何工作。圖論從來不是我的強項。 –

查找圖中斷開連接的節點的算法

回答

相關問題