第37章：图进阶

挑战1：计算路径的数量

写一个方法来计算有向图中两个顶点之间的路径数。下面的示例图有五条从A到E的路径。

挑战2：用图形表示你的朋友

文森特有三个朋友：切斯利、鲁伊斯和帕特里克。鲁伊兹也有朋友。雷，孙，以及文森特的一个共同朋友。帕特里克是科尔和凯里的朋友。Cole是Ruiz和Vincent的朋友。建立一个代表这个友谊图的邻接列表。鲁伊兹和文森特有哪些共同的朋友？

解决方案

挑战1的解决方案

我们的目标是写一个函数，找出图中两个顶点之间的路径数。一种解决方案是进行深度优先遍历，并跟踪所访问的顶点。

在这里，你要做以下工作。

1. numberOfPaths记录了在源和目的地之间找到的路径数量。

2. visited是一个Set，记录了所有被访问的顶点。

3. paths是一个递归辅助函数，接收四个参数。前两个参数是源点和目的地顶点。最后两个参数，visited，跟踪所访问的顶点，numberOfPath跟踪发现的路径数量。最后两个参数是在路径内修改的。

在numberOfPaths函数后面添加以下内容。

要获得从源头到目的地的路径。

1. 通过将源顶点标记为已访问，启动算法。

2. 检查源点是否是目的地。如果是，你就找到了一条路径，将计数递增1。

3. 如果不是，则获取与源顶点相邻的所有边。

4. 对于每一条边，如果它以前没有被访问过，就递归地遍历相邻的顶点，找到一条通往目的地顶点的路径。

5. 将源顶点从访问集中删除，这样你就可以继续找到通往该节点的其他路径。

你是在做深度优先的图形遍历。你递归地沿着一条路径下潜，直到你到达目的地，然后通过弹出堆栈来回溯。时间复杂度为O(V+E)。

挑战2的解决方案

这个解决方案使用你在上一章建立的AdjacencyList API。你可以使用任何非零的权重，但一个好的默认值是1。

你可以简单地看一下这个图，找到共同的朋友。

print("Ruiz and Vincent both share a friend name Cole")

如果你想用程序来解决，你可以利用元素是Hashable的事实，找到Ruiz和Vincent的朋友的Set的交点。

---

上一章	目录	下一章