本章结束时，您将能够:
- 描述 Dijkstra 算法的固有问题，并演示如何对其进行修改和/或与其他算法相结合来规避这些问题
- 使用贝尔曼-福特和约翰逊算法寻找图中的最短路径
- 描述 garaph 中强连接组件的重要性
- 使用 Kosaraju 算法寻找图中的强连通分支
- 描述有向图和无向图连通性的区别
- 对复杂问题实施深度优先搜索
- 评估图中的负权重循环
本章在前一章的基础上，介绍了一些更高级的图算法。您还将学习如何处理负权重和处理负权重周期的异常。
到目前为止，我们已经探索了各种常见的编程结构和范例。现在，我们将深入研究几项技术，这些技术扩展了我们之前讨论过的主题，从一系列高级图问题开始，然后将重点转移到动态编程的扩展主题上。
在这一章中，我们将讨论三种著名的算法，即贝尔曼-福特算法、约翰逊算法和科萨拉朱算法。所有这些算法都与我们在本书中已经介绍过的算法有着明显的相似之处，但是以各种方式扩展和组合它们，以比次优实现所允许的更高的效率来解决潜在的复杂问题。除了学习这些特定的技术，本章还应该增加你对基本图相关技术的使用的总体熟悉程度，并提供更多关于如何将这些基础应用于各种不同问题的见解。
我们之前讨论了寻找图中两个节点之间最短路径的几种方法。我们从探索最标准的图遍历形式开始，即深度优先搜索和广度优先搜索，并最终讨论了如何处理包含加权边的图的更有问题的情况。我们演示了如何使用 Dijkstra 算法，根据立即可用的最佳选项贪婪地对遍历中的每一步进行优先级排序，从而有效地找到加权图中的最短距离。然而，尽管 Dijkstra 算法在性能上有所提高，但它并不适用于所有情况。
考虑正在通过网络广播的无线信号；当它超过最初传播的点时，它的强度可能会受到许多因素的影响，例如它行进的距离以及它必须穿过的墙和其他障碍物的数量。如果您想确定信号到达每个目的地的路径，从而最大限度地减少信号恶化，您可以创建一个加权图，其中网络中的每个点由一个节点表示，任意两点之间的信号损失程度由加权边表示。然后，您可以使用迪克斯特拉算法计算图中的最短距离，以确定网络中成本最低的路径。
现在，假设在网络中安装了一个中继器/增强器，以增加特定点的信号强度，这种增加如何在您的图表中表示？最明显的方法是将升压器节点的输出边缘权重设置为负值(相当于它增加信号强度的程度)，这将减少通过它的任何路径的总距离/恶化。如果我们在网络图中使用迪克斯特拉算法，这将如何影响我们的结果？
正如我们在上一章中所讨论的，Dijkstra 的算法在遍历中如何选择每个顶点方面采取了贪婪的方法。在每一步中，它都会找到最近的未访问顶点，并将其添加到访问集中，从而将其排除在进一步的考虑之外。迪杰斯特拉算法的假设是，到目前为止考虑的每个顶点的最短路径已经找到，所以寻找更好的替代方案是没有意义的。然而，在包含负边权重的图中，如果它们在遍历的早期阶段产生较高的和，这种方法将不会探索导致最优解的可能性。
考虑一个具有负边权重的图，如下图所示:
在上图中，迪克斯特拉算法穿过的路径用红色表示。假设我们从顶点 A 开始，第一次从节点 A 移动到节点 B 后会有两个潜在的选项: B — > C ，其边权重为 5 ， B — > D ，其边权重为 10 。由于 Dijkstra 的贪婪方法， C 将被选为最短路径中的下一个节点，但我们可以清楚地看到，另一个选项(B—>D—>C = 10+–7 = 3)实际上是最优选择。
当面对负边缘权重时，Dijkstra 算法中固有的优化使其具有高水平的效率，最终导致其垮台。谢天谢地，对于这样的图，我们可以采用一种替代方法，这种方法与 Dijkstra 的算法非常相似，并且可以说实现起来更简单。
我们可以使用贝尔曼-福特算法来处理负权重的图。它用另一种方法取代了迪克斯特拉的贪婪选择方法，即迭代图中的每条边V–1次(其中 V 等于顶点的总数)，并在每次迭代中逐渐找到从源节点开始的最佳距离值。自然地，这使得它比迪克斯特拉算法具有更高的渐近复杂度，但是它也允许它为迪克斯特拉算法会误解的图产生正确的结果。下面的练习展示了如何实现贝尔曼-福特算法。
在本练习中，我们将使用基本的贝尔曼-福特算法来寻找负权重图中的最短距离。让我们开始吧:
-
首先，通过包含必要的库(以及方便起见的
namespace std)来设置您的代码:#include <iostream> #include <vector> #include <climits> using namespace std;
-
让我们从定义图中边的表示开始，这将需要三个变量:源节点的索引、目标节点的索引以及在它们之间遍历的成本:
struct Edge { int start; // The starting vertex int end; // The destination vertex int weight; // The edge weight // Constructor Edge(int s, int e, int w) : start(s), end(e), weight(w) {} };
-
为了实现贝尔曼-福特算法，我们需要对我们的图进行一些表示。为了简单起见，让我们假设我们的图可以用整数
V、图中顶点的总数和向量edges(定义图的邻接的“边”对象的指针集合)来表示。让我们也定义一个整数常数UNKNOWN，我们可以将其设置为某个任意的高值，该值总是大于图中任何边权重子集的总和(在climits中定义的INT_MAX常数适用于此目的):const int UNKNOWN = INT_MAX; vector<Edge*> edges; // Collection of edge pointers int V; // Total number of vertices in the graph int E; // Total number of edges in the graph
-
让我们也编写一些代码来收集图数据作为用户输入:
int main() { cin >> V >> E; for(int i = 0; i < E; i++) { int node_a, node_b, weight; cin >> node_a >> node_b >> weight; // Add a new edge using the defined constructor edges.push_back(new Edge(node_a, node_b, weight)); } // Choose a starting node int start; cin >> start; // Run the Bellman-Ford algorithm on the graph for // the chosen starting vertex BellmanFord(start); return 0; }
-
现在，我们可以开始实现贝尔曼-福特算法本身。出于我们的目的，让我们创建一个名为
BellmanFord()的函数，该函数接受一个参数—start(我们希望从中找到图中最短路径的起始节点)—并返回void。然后，我们将定义一个大小为V的距离数组，每个元素都初始化为UNKNOWN，除了起始节点，其索引初始化为0:void BellmanFord(int start) { vector<int> distance(V, UNKNOWN); distance[start] = 0;
-
大部分工作在下一步完成，我们定义一个循环，持续
V – 1次迭代，并在每次重复时遍历整个边集。对于每条边，我们检查其源节点的当前距离值是否不等于UNKNOWN(在第一次迭代中，仅适用于起始节点)。假设这是真的，那么我们将它的目的节点的当前距离值与源节点的距离和边的权重相比较。如果将边缘权重添加到当前节点的距离的结果小于目标节点的存储距离，我们用新的总和替换它在距离数组中的值:// Perform V - 1 iterations for(int i = 0; i < V; i++) { // Iterate over entire set of edges for(auto edge : edges) { int u = edge->start; int v = edge->end; int w = edge->weight; // Skip nodes which have not yet been considered if(distance[u] == UNKNOWN) { continue; } // If the current distance value for the destination // node is greater than the sum of the source node's // distance and the edge's weight, change its distance // to the lesser value. if(distance[u] + w < distance[v]) { distance[v] = distance[u] + w; } } }
-
在函数的最后，我们现在可以遍历
distance数组，并输出从源到图中每隔一个节点的最短距离:cout << "DISTANCE FROM VERTEX " << start << ":\n" for(int i = 0; i < V; i++) { cout << "\t" << i << ": "; if(distance[i] == UNKNOWN) { cout << "Unvisited" << endl; continue; } cout << distance[i] << endl; }
-
现在，我们可以返回到我们的
main()方法，并调用我们新实现的BellmanFord()函数。让我们在来自图 7.1 的示例图上测试我们的实现。为此，我们应该运行代码并输入以下输入:5 5 0 1 3 1 2 5 1 3 10 3 2 -7 2 4 2 0
-
我们的程序应该输出以下内容:
DISTANCE FROM VERTEX 0: 0: 0 1: 3 2: 6 3: 13 4: 8
如我们所见，贝尔曼-福特避免了会导致迪克斯特拉算法错误评估最短路径的陷阱。然而，还有另一个重要的问题需要解决，我们将在下一节中讨论。
考虑下图所示的图表:
用红色突出显示的边表示负权重循环或图中的循环，其中合并的边权重产生负总和。在这种情况下，这种循环会被反复考虑，最终结果会有偏差。
为了比较，考虑一个只有正边权重的图。这样一个图中的循环永远不会被考虑在解决方案中，因为到循环中第一个节点的最短距离已经被找到。为了演示这一点，假设上图中节点 B 和 D 之间的边缘权重为正。从节点 A 开始，通过边的第一次迭代将确定到节点 B 的最短距离等于 3 。再经过两次迭代，我们也会知道 A 到C(A—>B—>D—>C)的最短距离，等于 14 ( 3 + 8 + 3 )。
显然，14 加不出小于 3 的正数。由于在每个节点只被访问一次的任何图遍历中最多只能有*| V–1 |个步骤，我们可以确定通过图的边的| V–1 |次迭代足以确定每个可能的最短距离。推而广之，我们可以得出结论，在| V–1 |*迭代之后，更短的路径能够存在的唯一方式是重新访问一个节点，并且导致它的边权重是负的。因此，贝尔曼-福特算法的最后一步包括通过边缘执行一次迭代，以检查这种循环的存在。
我们可以使用与寻找最短路径相同的逻辑来实现这一点:通过检查每个边的权重与其源节点的距离值之和是否小于当前存储的到其目的节点的距离。如果在此步骤中发现较短的路径，我们将终止算法并报告负循环的存在。
我们将在下面的练习中探索算法的这种实现。
在本练习中，我们将修改练习 32 、*中实现贝尔曼-福特算法(第一部分)*的实现，以处理具有负权重循环的图。让我们开始吧:
-
我们基本上可以逐字复制上一步的代码。但是，这一次，我们将在确定是否找到了更短路径的条件下，用某种指示图包含负循环的输出来替换代码，从而使其无效:
// Iterate through edges one last time for(auto edge : edges) { int u = edge->start; int v = edge->end; int w = edge->weight; if(distance[u] == UNKNOWN) { continue; }
-
如果我们仍然能找到比我们已经找到的路径更短的路径，那么这个图一定包含一个负循环。让我们用以下
if语句来检查负重量循环:if(distance[u] + w < distance[v]) { cout << "NEGATIVE CYCLE FOUND" << endl; return; } }
-
现在，让我们在第一个
for循环结束和第一个输出行void BellmanFord(int start) { vector<int> distance(V, UNKNOWN); distance[start] = 0; for(int i = 1; i < V; i++) { for(auto edge : edges) { int u = edge->start; int v = edge->end; int w = edge->weight; if(distance[u] == UNKNOWN) { continue; } if(distance[u] + w < distance[v]) { distance[v] = distance[u] + w; } } } for(auto edge : edges) { int u = edge->start; int v = edge->end; int w = edge->weight; if(distance[u] == UNKNOWN) { continue; } if(distance[u] + w < distance[v]) { cout << "NEGATIVE CYCLE FOUND" << endl; return; } } cout << "DISTANCE FROM VERTEX " << start << ":\n"; for(int i = 0; i < V; i++) { cout << "\t" << i << ": "; if(distance[i] == UNKNOWN) { cout << "Unvisited" << endl; continue; } cout << distance[i] << endl; } }
之间插入这段代码
-
为了测试我们添加的逻辑，让我们在以下输入上运行算法:
6 8 0 1 3 1 3 -8 2 1 3 2 5 5 3 2 3 2 4 2 4 5 -1 5 1 8 0
-
我们的程序应该输出以下内容:
NEGATIVE CYCLE FOUND
你正在开发一种寻路机器人，它必须找到通过障碍跑道的最有效路径。出于测试目的，您设计了几门课程，每门都是正方形网格。你的机器人能够穿越它遇到的任何障碍，但这也需要更大的动力消耗。假设您的机器人从网格的左上角开始，可以在四个基本方向(北、南、东和西)中的任何一个方向上移动，您必须实现一个算法来确定您的机器人可以完成课程的最大能量。
由于执行这种遍历所需的能量可能很高，所以您在整个电网中散布了发电站，您的机器人可以使用这些发电站为自己充电。不幸的是，看起来你的机器人在能源消耗方面相当贪婪——如果它可以多次到达一个能源站而不必回溯，它将不断返回同一个位置，直到它不可避免地过度充电并爆炸！正因为如此，你需要预测你的机器人是否会在灾难发生前重新访问发电站并中止穿越尝试。
输入
- 第一行包含单个整数
N，是球场的高度和宽度。 - 下一个
N2- 1行各包含directions字符串和一个名为power的整数。每组N行对应一行，从网格顶部开始，其中每个单元格的数据从左到右定义(例如，在 3 x 3 网格中，*0—>【0，0】，1—>【0，1】，2—>【0，2】，3—>【1，0】，4—>【1，1】*等等)。 directions包含集合{“N”、“S”、“E”、“W”中的 0-3 个字符，代表您的机器人可以从每个点访问的细胞。因此，如果directions弦是SW，那么机器人可以从该点向南或向西移动。power代表穿过细胞所需的能量消耗。power的正值表示充电站位于电池内。
输出
- 如果穿越路线导致机器人爆炸，打印一行–
TRAVERSAL ABORTED。 - 否则，打印你的机器人到达课程右下角单元格时所能拥有的最大能量，相对于它开始时的能量。例如，如果机器人能以比开始多 10 个单位的能量完成迷宫，打印
10；如果它以比开始时少 10 个单位的能量完成迷宫，打印-10。
例
假设我们有以下输入:
3
SE -10
SE -8
S -6
S 7
E -10
S 20
E -1
NE 5网格的布局如下所示:
到达右下角能量最大的单元的路径如下:
0 —> 3 (-10)
3 —> 6 (+7)
6 —> 7 (-1)
7 —> 4 (+5)
4 —> 5 (-10)
5 —> 8 (+20)
(-10) + 7 + (-1) + 5 + (-10) + 20
= 11 more units of energy因此，你的程序应该输出11。
测试用例
以下测试用例应该有助于您更好地理解这个问题:
活动指南
-
不需要超出练习 33 、*实施贝尔曼-福特算法(第二部分)*中所述的算法。
-
您可能需要重新解释一些输入，以便它对应于您试图解决的实际问题。
-
There is no need to represent the grid as two-dimensional.
这个活动的解决方案可以在第 537 页找到。
我们现在已经确定，Bellman-Ford 比 Dijkstra 算法更通用，因为它具有在 Dijkstra 算法会产生不正确结果的情况下产生正确解的能力。然而，如果我们正在考虑的图不包含任何负边权重，Dijkstra 算法是两者之间的明显选择，因为其贪婪方法提供了潜在的显著效率优势。现在，我们将探索贝尔曼-福特如何与迪克斯特拉算法结合使用，以便它可以用于负权重的图。
比较了 Bellman-Ford 算法和 Dijkstra 算法的相对优缺点后，我们现在将讨论一种算法，该算法将两者结合起来检索图中每对顶点之间的最短路径。约翰逊算法为我们提供了这样的优势:能够利用 Dijkstra 算法的效率，同时仍然为负边权重的图产生正确的结果。
约翰逊算法背后的概念相当新颖——为了应对 Dijkstra 在处理负权重时的局限性，约翰逊算法只是对图中的边进行重新加权，使它们一致非负。这是通过贝尔曼-福特的创造性运用，结合一些特别优雅的数学逻辑来实现的。
约翰逊算法的第一步是向图中添加一个新的“虚拟”顶点，该顶点随后通过零加权边与每隔一个顶点相连。然后，贝尔曼-福特被用来寻找新顶点和其余顶点之间的最短路径，这些距离被存储起来以备后用。
考虑添加这个新顶点的含义:因为它有一条 0 加权边连接到图中的每个其他节点，所以它的最短路径距离都不会是正的。此外，它与图中每个节点的连通性确保了它的距离值在所有潜在的遍历路径上保持恒定的关系，这使得这些值和它们对应的边权重形成的和“伸缩”，换句话说，序列中的后续项相互抵消，使得总和等于第一项和最后一项的差。请看下图:
在上图中，标记为S的菱形节点表示虚拟顶点，黑色括号数字表示边权重，红色文本表示从S到每个节点的最短路径，橙色箭头表示从S经过的最佳路径，蓝色箭头表示从S分支的 0 权重边，这些边不包含在任何S的最短路径中。
让我们获取新的距离值，并根据它们在图的遍历中的外观按顺序排列–A --> B --> C --> A --> D --> E:
如果我们将原始边权重插入到它们所连接的节点的距离值之间，序列将如下:
现在，让我们将以下公式应用于边值:
W(uv) = w(uv) + d[s, u] - d[s, v]这里，w(uv)表示节点u和v之间的原始边缘权重，d[s, u]和d[s, v]表示S和u/v之间的最短路径距离，W(uv)表示变换后的边缘权重值。应用此公式会产生以下结果:
AB —> (-7) + 0 – (-7) = 0
BC —> (-2) + (-7) – (-9) = 0
CA —> 10 + (-9) – 0 = 1
AD —> (-5) + 0 – (-5) = 0
DE —> 4 + (-5) – (-1) = 0请注意，在后续迭代中，表达式中的第三项总是被中间项抵消；这证明了公式的“伸缩”特性。由于这个性质，下面两个表示节点 A 和 E 之间距离的表达式是等价的:
(w(AB) + d[s, A] - d[s, B]) + (w(BC) + d[s, B] - d[s, C]) + … + (w(DE) + d[s, D] - d[s, E])
(w(AB) + w(BC) + w(CA) + w(AD) + w(DE)) + d[s, A] - d[s, E]这意味着添加到图中任何路径的权重等于添加到其子路径的权重。我们知道，将这些值相加的结果总是非负的，因为贝尔曼-福特返回的距离数组确保我们对任何一对都有d[s, u] + weight(u, v) >= d[s, v]``u,v。因此，w(u, v) + d[s, u] - d[s, v]的值永远不能小于 0。
作为所应用的变换的结果，图中任何最短路径将穿过的每条边将被重新加权为零，这给我们留下了非负权重值，非常值得注意的是，这些值仍然保留了它们原来的最短路径排序！我们现在可以使用这些新的权重值在图上执行 Dijkstra 算法，以有效地检索每对节点的最短路径。
我们将在下面的练习中探索约翰逊算法的实现。
在本练习中，我们将实现约翰逊算法，以找到负权重图中每个节点到每个其他节点的最短距离。让我们开始吧:
-
我们可以重用前面练习中的大部分代码，包括我们的
Edge结构、UNKNOWN常量和图数据:#include <iostream> #include <vector> #include <climits> using namespace std; struct Edge { int start; int end; int weight; Edge(int s, int e, int w) : start(s), end(e), weight(w) {} }; const int UNKNOWN = INT_MAX; vector<Edge*> edges; int V; int E;
-
我们应该修改 Bellman-Ford 的函数声明，使其接受两个参数(一个整数，
V，和一个向量或Edge指针，edges，并返回一个整数向量。我们也可以删除start参数:vector<int> BellmanFord(int V, vector<Edge*> edges)
-
我们将从向图中添加虚拟顶点
S开始。因为S本质上对图的其余部分没有影响，所以这就像将距离数组的大小增加到 | V + 1 | 并在S和每隔一个节点vector<int> distance(V + 1, UNKNOWN); int s = V; for(int i = 0; i < V; i++) { edges.push_back(new Edge(s, i, 0)); } distance[s] = 0;
之间添加一条边一样简单
-
我们继续将 Bellman-Ford 的标准实现应用于修改后的图，使用
S作为源节点:for(int i = 1; i < V; i++) { for(auto edge : edges) { int u = edge->start; int v = edge->end; int w = edge->weight; if(distance[u] == UNKNOWN) { continue; } if(distance[u] + w < distance[v]) { distance[v] = distance[u] + w; } } }
-
这一次，让我们将负周期的最终检查移动到它自己的功能中:
bool HasNegativeCycle(vector<int> distance, vector<Edge*> edges) { for(auto edge : edges) { int u = edge->start; int v = edge->end; int w = edge->weight; if(distance[u] == UNKNOWN) continue; if(distance[u] + w < distance[v]) { return true; } } return false; }
-
现在，我们可以在原始函数的末尾调用它，如果发现负循环，就返回一个空数组:
if(HasNegativeCycle(distance, edges)) { cout << "NEGATIVE CYCLE FOUND" << endl; return {}; }
-
在确保图没有负循环之后，我们可以将距离值的结果集返回给调用函数，并将重新加权公式应用于图中的每条边。但是首先，让我们实现迪克斯特拉的算法:
vector<int> Dijkstra(int V, int start, vector<Edge*> edges)
-
现在，让我们声明一个整数向量
distance和一个布尔向量visited。和往常一样，distance的每个索引都会被初始化为UNKNOWN(除了起始顶点)，而visited的每个索引都会被初始化为假:vector<int> distance(V, UNKNOWN); vector<bool> visited(V, false); distance[start] = 0;
-
我们的迪克斯特拉算法的实现将利用一个简单的迭代方法，使用
for循环。您可能会从前面的章节中回忆起，Dijkstra 的算法需要在遍历的每一步找到具有最小距离值的节点。虽然这通常是通过优先级队列来完成的，但是我们将通过编码另一个短函数GetMinDistance()来完成，该函数将距离和访问的数组作为参数，并返回具有最短路径值的节点的索引:// Find vertex with shortest distance from current position and // return its index int GetMinDistance(vector<int> &distance, vector<bool> &visited) { int minDistance = UNKNOWN; int result; for(int v = 0; v < distance.size(); v++) { if(!visited[v] && distance[v] <= minDistance) { minDistance = distance[v]; result = v; } } return result; }
-
我们现在可以完成实现迪克斯特拉的算法:
```cpp
for(int i = 0; i < V - 1; i++)
{
// Find index of unvisited node with shortest distance
int curr = GetMinDistance(distance, visited);
visited[curr] = true;
// Iterate through edges
for(auto edge : edges)
{
// Only consider neighboring nodes
if(edge->start != curr) continue;
// Disregard if already visited
if(visited[edge->end]) continue;
if(distance[curr] != UNKNOWN && distance[curr] + edge->weight < distance[edge->end])
{
distance[edge->end] = distance[curr] + edge->weight;
}
}
}
return distance;
```
- 我们现在有了执行约翰逊算法所需的一切。让我们声明一个新的函数
Johnson()，它也以V和edges为参数:
```cpp
void Johnson(int V, vector<Edge*> edges)
```
- 我们首先创建一个整数向量
h，并将其设置为BellmanFord():
```cpp
// Get distance array from modified graph
vector<int> h = BellmanFord(V, edges);
```
的输出
- 我们检查
h是否为空。如果是，我们终止函数:
```cpp
if(h.empty()) return;
```
- 否则，我们应用重新加权公式:
```cpp
for(int i = 0; i < edges.size(); i++)
{
edges[i]->weight += (h[edges[i]->start] - h[edges[i]->end]);
}
```
- 为了存储每对节点的最短路径距离，我们用
V行初始化一个矩阵(这样每对二维索引[i, j]代表顶点i和顶点j之间的最短路径)。然后我们执行对迪克斯特拉算法的V调用，该算法返回每个起始节点的distance数组:
```cpp
// Create a matrix for storing distance values
vector<vector<int>> shortest(V);
// Retrieve shortest distances for each vertex
for(int i = 0; i < V; i++)
{
shortest[i] = Dijkstra(V, i, edges);
}
```
- 不出所料，我们在这一步积累的结果相当不准确。由于我们的重新加权操作，每个距离值现在都是正值。然而，这可以通过对每个结果反向应用相同的公式来非常简单地纠正:
```cpp
// Reweight again in reverse to get original values
for(int i = 0; i < V; i++)
{
cout << i << ":\n";
for(int j = 0; j < V; j++)
{
if(shortest[i][j] != UNKNOWN)
{
shortest[i][j] += h[j] - h[i];
cout << "\t" << j << ": " << shortest[i][j] << endl;
}
}
}
```
- 现在，让我们回到我们的
main()函数，实现处理输入的代码。在我们收集了输入图的边之后，我们只需要对Johnson()执行一次调用，我们的工作就完成了:
```cpp
int main()
{
int V, E;
cin >> V >> E;
vector<Edge*> edges;
for(int i = 0; i < E; i++)
{
int node_a, node_b, weight;
cin >> node_a >> node_b >> weight;
edges.push_back(new Edge(node_a, node_b, weight));
}
Johnson(V, edges);
return 0;
}
```
- 让我们使用以下输入来测试我们的算法:
```cpp
7 9
0 1 3
1 2 5
1 3 10
1 5 -4
2 4 2
3 2 -7
4 1 -3
5 6 -8
6 0 12
```
- The output should be as follows:
```cpp
0:
0: 0
1: 3
2: 6
3: 13
4: 8
5: -1
6: -9
1:
0: 0
1: 0
2: 3
3: 10
4: 5
5: -4
6: -12
2:
0: -1
1: -1
2: 0
3: 9
4: 2
5: -5
6: -13
4:
0: -3
1: -3
2: 0
3: 7
4: 0
5: -7
6: -15
5:
0: 4
1: 7
2: 10
3: 17
4: 12
5: 0
6: -8
6:
0: 12
1: 15
2: 18
3: 25
4: 20
5: 11
6: 0
```
从前面的输出中可以看到，我们已经成功地打印了从每个节点到每个其他节点的最短距离。
你是一家知名软件公司的开发人员，该公司每年都会收到大量新的求职申请。因此，要求每个员工都参与技术面试过程。每次面试前，都会给你一套三个编程问题，每个问题包含一个简短的描述，以及两到三个难度不断增加的测试用例。
最近有消息引起你的注意，一些受访者设法提前获得了某些面试问题的测试用例。因此，每隔几周，被调用的能力就会要求你创建新的测试用例集。为大多数问题生成像样的测试用例并不是特别有挑战性，除了关于图论的问题。您已经注意到，设计一个既有效又与问题相关的图表的过程可能有点耗时，因此您已经下定决心要自动化这个过程。
贵公司使用的最常见的与图相关的面试问题是全对最短路径问题，该问题要求受访者在一个有加权边的有向图中找到每对顶点之间的最短距离。由于这个问题的性质，您希望生成器实用程序生成的图表有助于评估受访者对问题的理解。您已经决定，如果图表符合以下标准，它将对技术面试有用:
- 它是一个有向图，可以包含正边权重和负边权重。
- 任何一对节点之间都应该只有一条边，任何节点都不应该有自己的边。
- 每个节点应该至少有一个传入或传出边缘。
- 任何边权重的绝对值都应该小于 100。
该实用程序应接受以下输入:
seed:随机数生成的种子值iterations:要生成的图数量V:顶点数E:边数
实用程序应该使用对std::rand()的调用来处理每个边的生成。如果它试图在同一对节点之间创建第二条边，它应该停止生成新边，直到找到有效的边对。
图生成应如下进行:
1.接收输入(seed、iterations、V和E)
2.设置随机数生成器的种子值
3 对于每次迭代，请执行以下操作:
-
Set
i = 0-尝试通过对
rand()执行三次调用来创建边，以便生成源节点、目标节点和边权重的值(按此顺序)。-检查
rand()生成的下一个值是否能被3;整除，如果能，则使边缘权重为负。 -
If an edge between the source and destination nodes already exists, try again:
-将
edge(source, destination, weight)添加到边集中，并增加i。-如果在
E边创建之后，有一个节点不是边的一部分，则该图被认为是无效的。
如果生成的图是有效的，您应该找到图中每对节点之间的最短路径，就像我们在面试中所期望的那样。对于图中的每个节点，您希望找到其所有路径的平均最短距离(即距离值之和除以可到达的节点数)。图表的平均距离将被定义为这些值的平均值。
您还对哪组值倾向于产生最多数量的“有趣”图感兴趣。当图的平均距离小于最高值边权重的一半时，你认为图是有趣的。因此，您的算法应该输出感兴趣的图与有效图总数的百分比(四舍五入到两位小数)。请注意，出于这一特殊目的，您认为具有负权重循环的连通图是有效的，但并不有趣。
输入格式
一行包含四个整数；即分别为seed、iterations、V和E。
输出格式
两行，第一行包含INVALID: 字符串，后面是无效图的数量，第二行包含PERCENT INTERESTING: 字符串，后面是感兴趣图与有效图的比率，显示为四舍五入到两位小数的百分比。
活动指南
对std::rand()的调用不一定会在每个环境中产生相同的值。为了确保一致性，您可以将以下代码复制/粘贴到您的程序中(取自 C 标准):
static unsigned long int randNext = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
randNext = randNext * 1103515245 + 12345;
return (unsigned int)(randNext/65536) % 32768
}
void srand(unsigned int seed)
{
randNext = seed;
}实现图生成实用程序时，请确保按照问题描述中描述的确切顺序执行这些步骤。
测试用例
以下是一些示例输入和输出，应该可以帮助您更好地理解问题:
这个活动的解决方案可以在第 541 页找到。
在前几章中，我们讨论了图的几种分类。描述一个图的特征的最常见的方法是说明它是有向的还是无向的。后者定义了默认情况下边是双向的图(如果节点 A 有一条边连接到节点 B，则节点 B 有一条边连接到节点 A)，而前者描述了边朝向特定“方向”的图。
假设你是一家视频托管网站的员工，负责统计各种渠道的用户之间的共性。贵公司特别感兴趣的是发现订阅某些频道的个人和频道各自所有者的订阅之间的模式，希望更深入地了解他们的定向广告服务应该如何定向。你的公司提供的服务最近变得相当广泛，所以你需要一种方法来组织相关的数据，以一种足够清晰的方式来产生有用的统计信息。
让我们将网站每个用户的频道可视化为有向图中的节点，它们之间的邻接关系代表他们订阅的另一个频道的各自所有者。我们可能会注意到，即使是在共享同一频道订阅的大量用户群体中，他们的所有单个订阅集的多样性也将使我们发现它们之间任何明显相似之处的能力变得非常复杂。理想情况下，我们希望解开图中大量杂乱的连接，并将数据放入不同的组中，在这些组中，每个用户的订阅都与其他用户的订阅有某种关联。
我们可以通过观察有向图共有的某些特征来解开这个特殊问题的复杂性。因为有向图的边不能保证是双向的，所以我们可以从逻辑上得出结论，对图的某些部分的访问可能会受到限制，这取决于您从哪个节点开始遍历。如果将一个图分成不同的集合，使得同一集合中的任意一对顶点之间都有一条连接路径，则得到的组将代表该图的强连通分量。
无向图的连通分支可以被描述为包含主图的最大尺寸子图的集合，其中同一组中的每个节点都“连接”到其他节点(也就是说，单个分支中任意两个节点之间的访问不受限制)。在连通图中，无论遍历从哪里开始，每个节点都可以到达，因此我们可以推导出这样的图由单个连通分量(整个图)组成。相反，任何限制从一点到另一点的访问的图都被描述为断开的。
另一方面，所谓的“强”连通性是有向图独有的特征。要比较理解“强连通性”的定义差异，请观察无向图的以下示例:
三个彩色子图各自代表一个独立的连接组件。如前所述，它们的连通性是由这样一个事实定义的，即每个顶点都有一条路径将其连接到同一组中的其他顶点。此外，一个组件的顶点没有连接到另一个组件的路径。从上图中，我们可以看到无向图的连通分支被分成明显独立的组，其中任何分支的节点集和边集都与其他分支完全分离。
相比之下，强连接的组件不需要与图中的其他组件完全隔离，也就是说，组件之间可能存在重叠的路径:
在上图中，我们可以看到有四个强连接的组件: A 、 B 、 CEFG 、 DHI 。注意节点 A 和 B 是各自集合中唯一的成员。通过对节点 A 的进一步研究，我们可以看到虽然 A 有一条通往 DHI 集合中每个节点的路径，但是 DHI 集合中没有一个节点有任何通往节点 A 的路径。
回到我们的视频托管网站示例，我们可以将网络图的强连接组件定义为组，在这些组中，通过导航与同一组中其他用户的频道相关联的订阅的“路径”，可以找到每个频道。以这种方式分解潜在的大量数据可能有助于将相关的图关系集与那些没有明显相似之处的图关系集隔离开来:
寻找图的强连通分支的最常见且概念上容易掌握的方法之一是 Kosaraju 算法。Kosaraju 的算法通过执行两组独立的 DFS 遍历来工作，首先探索原始形式的图，然后对其转置进行同样的操作。
虽然 DFS 是 Kosaraju 算法中典型使用的遍历类型，但 BFS 也是一个可行的选择。然而，对于本章包含的解释和练习，我们将坚持传统的基于 DFS 的方法。
图的转置基本上与原始图相同，除了其每个边中的源/目标顶点被交换(即，如果原始图中存在从节点 A 到节点 B 的边，转置图将具有从节点 B 到节点 A 的边):
算法的第一步(初始化后)是遍历图的顶点并执行 DFS 遍历，从上一次遍历中尚未访问的每个节点开始。在 DFS 中每个点的开始，当前节点被标记为已访问，然后探索其所有未访问的邻居。在研究了每个当前节点的邻接之后，在当前递归子树终止之前，它被添加到栈的顶部。
在探索原始图中的每个顶点后，从栈顶部弹出的每个未访问节点开始，对其转置进行同样的操作。此时，在具有唯一起始点的每个后续 DFS 遍历期间遇到的节点集代表图的强连通部分。
就如何直观地简化一个潜在的复杂问题而言，Kosaraju 的算法相当有效，将它简化为一个相当简单的实现。另外，假设输入图具有邻接表表示，它也是相当有效的，因为它具有线性渐近复杂度 O(V + E) 。
不建议在该算法中使用邻接矩阵，因为在遍历中寻找每个顶点的邻居需要大量的额外迭代。
我们将在下面的练习中研究 Kosarju 算法的实现。
在本练习中，我们将使用 Kosaraju 的算法找到图中的强连通分量。让我们开始吧:
-
为了实现 Kosaraju 的算法，我们需要包含以下标题:
#include <iostream> #include <vector> #include <stack>
-
让我们定义一个名为
Kosaraju()的函数，该函数接受两个参数——一个整数，V(顶点数)和一个整数向量的向量，adj(图的邻接表表示)——并返回一个整数向量的向量，该向量表示输入图的每个强连通分量中的节点索引集合:vector<vector<int>> Kosaraju(int V, vector<vector<int>> adj)
-
我们的第一步是声明我们的栈容器和访问数组(每个索引初始化为
false)。然后，我们遍历图的每个节点，从每个尚未标记为visited:vector<bool> visited(V, false); stack<int> stack; for(int i = 0; i < V; i++) { if(!visited[i]) { FillStack(i, visited, adj, stack); } }
的索引开始我们的 DFS 遍历
-
我们的第一个 DFS 函数
FillStack()采用四个参数:一个整数节点(遍历中当前点的顶点索引)，一个名为visited的布尔向量(先前遍历的节点集)，以及两个整数向量adj(图的邻接表)和stack(访问节点索引列表，根据它们被探索的时间排序)。最后三个参数将通过调用函数的引用传递。DFS 以标准方式实现，除了在每个函数调用结束时将当前节点的索引推送到栈的附加步骤:void FillStack(int node, vector<bool> &visited, vector<vector<int>> &adj, stack<int> &stack) { visited[node] = true; for(auto next : adj[node]) { if(!visited[next]) { FillStack(next, visited, adj, stack); } } stack.push(node); }
-
现在，让我们定义另一个函数
Transpose()，它以原始图的参数为参数，返回其转置的邻接表:vector<vector<int>> Transpose(int V, vector<vector<int>> adj) { vector<vector<int>> transpose(V); for(int i = 0; i < V; i++) { for(auto next : adj[i]) { transpose[next].push_back(i); } } return transpose; }
-
为了准备下一组遍历，我们声明邻接表转置(初始化为我们的
Transpose()函数的输出)，并将我们访问的数组重新初始化为false:vector<vector<int>> transpose = Transpose(V, adj); fill(visited.begin(), visited.end(), false);
-
对于算法的后半部分，我们将需要定义我们的第二个 DFS 函数
CollectConnectedComponents()，它采用与FillStack()相同的参数，只是第四个参数现在被替换为对整数向量分量的引用。这个向量分量是我们存储图中每个强连通分量的节点索引的地方。遍历的实现也几乎与FillStack()函数相同，除了我们删除了将节点推送到栈的行。取而代之的是，我们在函数的开头包含一行，用于收集组件向量中遍历的节点:void CollectConnectedComponents(int node, vector<bool> &visited, vector<vector<int>> &adj, vector<int> &component) { visited[node] = true; component.push_back(node); for(auto next : adj[node]) { if(!visited[next]) { CollectConnectedComponents(next, visited, adj, component); } } }
-
回到我们的
Kosaraju()函数，我们定义一个称为connectedComponents的整数向量向量，在这里我们将存储我们对转置执行的每个遍历的结果。然后，我们在一个while循环中迭代地从栈中弹出元素，再次从未访问的节点开始每次 DFS 遍历。在每次调用 DFS 函数之前，我们声明CollectConnectedComponents()引用的分量向量，然后在遍历完成后将其推送到connectedComponents。栈空时算法完成，之后返回connectedComponents:vector<vector<int>> connectedComponents; while(!stack.empty()) { int node = stack.top(); stack.pop(); if(!visited[node]) { vector<int> component; CollectConnectedComponents(node, visited, transpose, component); connectedComponents.push_back(component); } } return connectedComponents;
-
从我们的
main()函数中，我们现在可以通过在单独的行上打印每个向量的值来输出每个强连通分量的结果:int main() { int V; vector<vector<int>> adj; auto connectedComponents = Kosaraju(V, adj); cout << "Graph contains " << connectedComponents.size() << " strongly connected components." << endl; for(auto component : connectedComponents) { cout << "\t"; for(auto node : component) { cout << node << " "; } cout << endl; } }
-
To test the functionality of our newly implemented algorithm, let's create an adjacency list representation based on the following graph:
###### 图 7.17:样本输入数据的图表示
- 在
main()中，V和adj的定义如下:
```cpp
int V = 9;
vector<vector<int>> adj =
{
{ 1, 3 },
{ 2, 4 },
{ 3, 5 },
{ 7 },
{ 2 },
{ 4, 6 },
{ 7, 2 },
{ 8 },
{ 3 }
};
```
- 执行我们的程序时，应显示以下输出:
```cpp
Graph contains 4 strongly connected components.
0
1
2 4 5 6
3 8 7
```
你正在设计一个游戏，其中多个玩家被随机放置在迷宫般的房间里。每个房间都包含一个或多个传送设备，玩家可以使用它们在迷宫的不同部分之间旅行。每个传送点都有一个相关的值，这个值会被添加到任何使用它的玩家的分数中。玩家轮流轮流穿越迷宫，直到每个房间都至少被参观一次，此时回合结束，得分最低的玩家获胜。
你已经实现了一个系统，在每个游戏开始的时候，这个系统都会按程序生成一个新的迷宫。不幸的是，你最近发现一些生成的迷宫包含循环，玩家可以使用这些循环来无休止地降低他们的分数。你还注意到，玩家经常有不公平的优势，这取决于他们开始的房间。最糟糕的是，传送点经常以这样一种方式分散，玩家最终可能会在整个回合中与迷宫的其他部分隔绝。
您希望实现一个测试过程，以确保生成的迷宫是公平和适当平衡的。你的测试应该首先确定迷宫是否包含一条可以用来不断降低玩家分数的路径。如果是，应该输出INVALID MAZE。如果迷宫有效，你应该从每个起点找到可以达到的最低分数并上报(或者DEAD END，在房间没有传送点的情况下)。
此外，你想防止被困在迷宫某个特定区域的可能性，所以你的测试也应该输出玩家无法进入迷宫其他部分的任何房间组。
预期输入
每个测试都应该接收以下输入:
- 迷宫中的房间数量
- 迷宫中传送点的数量
- 源房间、目的房间以及与每个传送点相关的点数
预期输出
对于每一个测试，程序首先要确定迷宫中是否有可以用来无限降低玩家分数的路径。如果是，应该打印一行:INVALID MAZE。
如果迷宫有效，你的程序应该输出能达到的最低分，从每个房间开始(或者DEAD END，如果房间没有传送点的话)，假设至少移动一次，整个迷宫只能穿越一次。最后，你的程序应该列出玩家可以“卡住”的任何房间组(也就是说，他们完全被限制进入迷宫的其他部分)；对于每一个这样的组，你的程序应该在单独的行上打印每个组中所有房间的索引。
样本输入和输出
以下是一些示例输入，可以帮助您更好地理解这个问题:
活动指南
-
不要被无关的信息分散注意力。问问自己具体需要完成什么。
-
问题的第一个条件(确定迷宫是否包含可以无限降低我们分数的路径)也可以表示为:如果迷宫表示为一个加权图，那么在任何产生负和的路径上是否存在循环？显然，这是一个我们完全有能力解决的问题！您可能还认识到第二个条件(找到玩家从给定点开始可以获得的最低分数)与第一个条件密切相关。
-
最后一个条件有点挑战性。根据我们在本章中讨论的图术语，考虑如何重新定义“被困”在迷宫的某个部分。有这个属性的迷宫会是什么样子？
-
Consider drawing one or several of the input graphs on paper. What characterizes the groups of rooms in which a player can get stuck?
这个活动的解决方案可以在第 550 页找到。
到目前为止，很可能很明显，很少有一种“完美”的方法来实现图结构。我们所代表的数据的特征，加上我们试图解决的问题的细节，可能会使某些方法不合理地低效，尽管事实上它们在不同的条件下可能是完全可以接受的。
每当你试图确定是否使用邻接表对矩阵，类/结构对简单数组，贝尔曼-福特对约翰逊算法，BFS 对 DFS 等等，最终的决定应该主要取决于数据的细节和你打算如何使用它。例如，如果你想找到图中每对节点之间的最短距离，约翰逊算法将是一个很好的选择。然而，如果您只需要偶尔找到单个起始节点的最短距离，约翰逊算法将执行相当多的不必要的工作，而对贝尔曼-福特的一次调用就足够了。
尝试使用不同形式的图表示来编写我们在本章中讨论的每个算法是一个有益的练习。例如，贝尔曼-福特可以通过用邻接表和二维边权重矩阵替换我们在第一个练习中使用的Edge指针的向量来轻松实现。在某些情况下，一个实现提供的效率潜力可能只比另一个略好；在其他时候，差异可能相当大。然后，有时候，某种方法的价值更多的是与简单性和可读性有关，而不是任何可衡量的性能基准。比较各种算法的性能如何在不同的数据集和场景中扩展可以提供非常丰富的信息，并且通常是现实世界开发中的基本实践。
在您努力加深对图论及其实现的理解的过程中，我们提供以下建议:
- 抵制使用“复制粘贴”方法实现新算法的冲动。如果你不理解算法工作背后的基本原理，你就很有可能错误地使用它。此外，即使它按照您希望的方式运行，也要记住图实现是高度特定于上下文的，这一点很重要。盲目使用任何算法意味着您将缺乏在不同参数集之间扩展解决方案功能所必需的理解。
- 当将新的概念付诸实践时，避免完全依赖抽象的、非上下文的实现。在纯理论数据上使用某种算法后，尝试修改它以适合某种实际数据模型(即使该数据本身是假设的)。想象真实的场景，在其中你可以使用你新获得的算法知识，这将增加你知道何时以及如何在工作中使用它的概率。
在您真正考虑以下事项之前，避免实现您的图表:
- 它的基本目的和实现该目的所需的基本功能(即，它描述的数据、它需要执行的查询类型、它需要有多动态等等)
- 它需要表示与问题相关的信息的最基本的组件
未能评估这些关键想法可能会导致混乱和过于冗长的代码，充斥着不必要的数据和函数，对实际的解决方案毫无价值。在编写任何代码之前，规划好图表的必要组成部分，可能会为您节省大量的混乱和繁琐的重构工作。
最终，发展对图编程的全面理解是一项技能，它远远超出了简单学习所有正确算法的范围。一个简单的网络搜索与任何非琐碎的绘图问题相关，将导致大量深入分析的研究文章，对不同方法的比较评估，以及尚未发现合理实现的推测解决方案。一如既往，一致的实践是掌握任何编程技能的最佳方法；而图论作为一门庞大而充满活力的学科，当然也不例外！
到目前为止，我们已经相当详细地介绍了图表。现在，您应该对图论在软件开发中的一些基本用途有了一个坚实的理解，并且对基于图的解决方案如何被用来封装复杂的数据，使我们能够相对容易地查询和操作它有了一个了解。在第 6 章、图算法 I 中学习了图结构和遍历的基础，然后在本章中扩展它们来解决更高级的问题，现在您应该已经准备好在未来探索更深入的图实现，因为这些基本概念是它们的核心。
虽然这一章没有完全结束我们对本书中图算法的讨论，但我们现在将从图中休息一下，来探索现代开发人员技能中最强大、最具挑战性的编程技术之一。像图算法一样，我们接下来要讨论的主题是如此广泛和概念抽象，以至于它将跨越两个独立的章节。然而，由于它的有用性(以及它的难度)，它是许多软件公司在技术面试时的最爱。