图表 - 如何计算从 v1 到 v2 所需的最小 "broken roads" 数量？
Graphs - How to count the minimum number of "broken roads" necessary to go from v1 to v2?
给定一个图（无向、无加权且所有顶点都相互连接），我需要找到从 A 到 B 必须访问的最少 "bad edges" 个数。例如，如果有一个图有 5 个顶点，坏边是：(0,1)、(0,2)、(0,3) 和 (0,4)，从 0 到 4 我至少需要访问1 个坏边。它可以直接从 0 到 4，或者从 0 到 1，然后从 1 到 4。路径的长度根本不重要。我正在尝试修改 BFS 来完成这项工作，但我不太确定这是否是正确的方法。我的修改是不使用队列，而是使用列表，当我发现一条坏边时，我把它放在列表的后面，所以我只会在真正需要的时候访问这条边，但发现它不会最小化坏边的数量。有什么建议吗？
虽然确实可以通过加权最短路径来解决，但实际上还有一个更有效的方法（就运行时间解决方案而言）。
首先，定义一个辅助图 G'=(V,E')，其中 e 在 E' 中当且仅当 e 是 "good"。此步骤与图表的大小成线性关系。
现在，您可以在 G' 中使用 DFS 或 BFS 在 O(|V|+|E|) 中找到连通分量。
接下来，你所要做的就是"collapse"所有节点到代表它们的单个节点（这也是线性时间），然后添加"bad edges"（注意永远不会有"good edge" 连接两个组件，否则它们将在同一组件中）。
现在，您可以在新图上运行 BFS，路径的长度是所需的最少节点数。
虽然这比简单的加权最短路径实施起来复杂得多，但与 O(|E|log|V|) 的加权最短路径。
给定一个图（无向、无加权且所有顶点都相互连接），我需要找到从 A 到 B 必须访问的最少 "bad edges" 个数。例如，如果有一个图有 5 个顶点，坏边是：(0,1)、(0,2)、(0,3) 和 (0,4)，从 0 到 4 我至少需要访问1 个坏边。它可以直接从 0 到 4，或者从 0 到 1，然后从 1 到 4。路径的长度根本不重要。我正在尝试修改 BFS 来完成这项工作，但我不太确定这是否是正确的方法。我的修改是不使用队列，而是使用列表，当我发现一条坏边时，我把它放在列表的后面，所以我只会在真正需要的时候访问这条边，但发现它不会最小化坏边的数量。有什么建议吗？
虽然确实可以通过加权最短路径来解决，但实际上还有一个更有效的方法（就运行时间解决方案而言）。
首先，定义一个辅助图 G'=(V,E')，其中 e 在 E' 中当且仅当 e 是 "good"。此步骤与图表的大小成线性关系。
现在，您可以在 G' 中使用 DFS 或 BFS 在 O(|V|+|E|) 中找到连通分量。
接下来，你所要做的就是"collapse"所有节点到代表它们的单个节点（这也是线性时间），然后添加"bad edges"（注意永远不会有"good edge" 连接两个组件，否则它们将在同一组件中）。
现在，您可以在新图上运行 BFS，路径的长度是所需的最少节点数。
虽然这比简单的加权最短路径实施起来复杂得多，但与 O(|E|log|V|) 的加权最短路径。