在一张图中找到孤立节点的算法

Question

我正在寻找一种方法，能够在给定有向图中，找到所有从给定起点无法到达的节点。我有一个想法，基于与迪杰斯特拉算法类似的概念，大致如下（伪代码），但是否有更好的方法？

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

- Mason Wheeler

Answer 1

只需从起始节点开始运行广度优先搜索！在BFS后未被访问的所有节点都无法从您的起点到达。

- Haile

---

那里描述的算法基本上看起来像我给出的算法，只是它有一个“目标”节点和图的隐式根。 - Mason Wheeler

是的，我没有注意到，这有点棘手。StealFrom 做什么？此外，这是一个众所周知的算法，对于你的任务来说相当标准。我可以问一下为什么你需要另一种方法吗？ - Haile

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