查找图中断开连接的节点的算法

我正在寻找一种方式，给定有向图，以查找从给定起点无法到达的所有节点。基于与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

它将一个项目从一个列表移动到另一个列表。我不需要“另一种方法”，我只是想弄清楚它应该如何工作。图论从来不是我的强项。 –

查找图中断开连接的节点的算法

回答

相关问题