algorithm - 有向图查找其输入边并非都可以从给定节点到达的节点

Question

在最近的一次采访中，我被问到以下问题。

给定一组节点和边，起始节点指向最终结束节点。在下图中，它从 1 开始，到 15 结束。他们的问题是以节点 2（或任何节点）为起点，我们如何才能在其路径中找到下一个节点，其输入边并非都可以从节点 2 到达（即我们怎样才能达到14）。

我该怎么做，伪代码应该没问题。

Answer 1

1. 标记从起始节点可到达的所有边。
2. 查找从具有未标记输入边的起始节点可到达的第一个节点。

Answer 2

我会说：

1. 查找从节点 2 无法到达的节点。运行 BFS 或任何完整的算法以查找 set all reachable R。查找无法访问的使用U = V - R

2. 从那些不可到达的节点中查找所有可以到达的节点，每当找到一个节点时，就判断它是否在节点2的可达列表中。如果是，则保存刚刚使用的边。

在第二步中，您依次选择节点U并执行 BFS。您对待节点的方式不同：

• X每当你发现一个属于U已经被挑选的节点时，你就会停下来
• 每当你发现一个Y属于U但未被选中的节点时，你就从U
• 当您在 中找到一个节点时 R，您会记住该边并将该节点标记为“永远不要访问”。

Answer 3

我看不出有任何方法可以避免至少遍历整个图一次（假设节点没有指向父节点的链接）。如果可以，那么基于从节点到直接父集的映射（下面的“父映射”）的简单解决方案是：

• 编写一个例程，为起始节点下的所有节点扩展父映射（使用 dfs）。该例程不需要探索已经是地图中的键的节点。

• 为图中的每个节点调用上面的例程。这给出了从节点到父节点的完整映射（图的转置，有效）。

• 从问题中的给定节点（例如 2）调用上面的例程，并使用新地图。这给出了从节点到父节点的映射，可从 2 到达。

• 使用给定节点的 bfs，找到两个映射中父节点不同的第一个节点。

您不需要在地图中存储实际的父节点（这种方式最容易解释）；您可以通过标记访问过的节点并存储父母数量的计数来做类似的事情。

还有另一种说法：找到图的转置和从给定节点可到达的节点集。然后从给定节点 bfs 找到第一个节点，其中转置导致可达集之外的父节点。（这真的只是一个问题......）

Answer 4

• 如果该算法必须进行一次查找，那么只需考虑 StartNode：
  • 查找从起始节点可到达的所有节点。（通过运行 BFS 图遍历算法）
  • 将这个从 StartNode 可到达的节点列表保存在哈希表中，以便高效查找。
  • 对于从当前节点可到达的每个节点（按顺序）：
    • 检查传入节点（传入边的起始顶点）
    • 如果哈希表中所有传入节点都可用，则移动到下一个可达节点 - 否则返回此节点。