找到一组不可达节点

Question

设有向图 G.

U 是 G 中的一组“黑色”顶点 这样：

1. G\U（白色）的每个元素都有一条通往黑色顶点的路径。
2. U(black)的任何元素之间都没有路径。

给我一个算法在这个图中搜索组 U。

我是图论算法的新手，这种类型的组有特定的名称吗？

我听说过的一个解决方案是 outdegree 0 的所有 nodea ......不确定这是不是真的。

Answer 1

“度数为 0 的顶点”是黑色顶点的必要条件，但不是充分条件。他们还必须至少有一个来自白色顶点的链接。

所以找到黑色顶点的算法：

• 遍历顶点

  • IF出度== 0 添加到候选黑人名单
  • 其他 添加到白人列表

• 设完假

• WHILE 完成 == false

  • 设置完成
  • 在候选黑人上循环 b
    • 设置黑色OK false
    • LOOP 白人
      • b,w 之间的 IF 链接
        • 设置黑色OK true
        • BREAK 从循环 w
    • IF blackOK false
      • 将 b 从黑名单移至白名单
      • 设完假
      • 继续循环 b

Answer 2

如果不允许黑色顶点返回到自身的路径，则某些图将无解。例如，任何循环图。出于这个原因，我假设你允许黑色节点有自己的路径，但没有其他黑色节点。

1. 首先将所有出度为零的顶点添加到 U.
2. 从 U 的顶点向后运行 BFS，令 X 为 BFS 永远不会到达的顶点集。
3. 如果 X 为空那么你就完成了，否则重复执行以下操作：
4. 选取 X 中的任意一个顶点。从它开始向前运行 BFS，直到您第二次到达任意一个顶点。从 X 中删除该顶点。现在，从该顶点向后运行 BFS，并删除您从 X 到达的所有顶点。如果 X 不为空，则重复所有 (4)。