algorithm - 图 - 如何计算从 v1 到 v2 所需的最小 "broken roads"数量？

Question

给定一个图(无向、无加权且所有顶点都相互连接)，我需要找到从 A 到 B 必须访问的“坏边”的最小数量。例如，如果有一个图有 5 个顶点和坏边是:(0,1)、(0,2)、(0,3) 和 (0,4)，从 0 到 4 我需要访问至少 1 个坏边.它可以直接从 0 到 4，或者从 0 到 1，然后从 1 到 4。路径的长度根本不重要。我正在尝试修改 BFS 来完成这项工作，但我不太确定这是否是正确的方法。我的修改是不使用队列，而是使用列表，当我发现一条坏边时，我把它放在列表的后面，所以我只会在真正需要的时候访问这条边，但发现它不会最小化坏边的数量。有什么建议吗？

Answer 1

虽然它确实可以通过加权最短路径来解决，但实际上还有一个更有效的(在运行时解决方案方面)。

首先，定义一个辅助图 G'=(V,E') 其中 e 在 E' iff e 是“好”。此步骤与图的大小成线性关系。

现在，您可以在 O(|V|+|E|) 中使用 DFS 或 BFS 在 G' 中找到连通分量。

接下来，您所要做的就是将所有节点“折叠”为代表它们的单个节点(这也是线性时间)，并添加“坏边”(注意永远不会有“好边”连接两个组件，否则它们将位于同一组件中)。

现在，您可以在新图上运行 BFS，路径的长度是所需的最小节点数。

虽然这比简单的加权最短路径实现起来要复杂得多，但此解决方案提供了 O(|V|+|E|)(在您的图表中是 O(| E|)) 运行时间，与加权最短路径的 O(|E|log|V|) 相比。