第44章：Prim算法

在以前的章节中，你已经看过深度优先和广度优先的搜索算法。这些算法形成了生成树。

生成树是无定向图的一个子图，包含图的所有顶点，用最少的边连接。生成树不能包含一个周期，也不能断开连接。

这里有一个图G和它所有可能的生成树。

从这个形成三角形的无向图中，你可以生成三种不同的生成树，其中你只需要两条边来连接所有顶点。

本章将介绍Prim算法，这是一种用于构建最小生成树的贪婪算法。贪婪算法是一步一步地构建解决方案，并在每一步中孤立地选择最优化的路径。

最小生成树可以使被选择来跨越该树的边的总重量最小化。它在各种情况下都有帮助。例如，你可能想找到最便宜的方式来布局水管网络。

下面是一个加权无向图的最小生成树的例子。

注意，只有第三个子图形成了最小生成树，因为它的总成本是3。

Prim的算法通过一次选择一条边来创建最小生成树。它是贪婪的，因为每次选择一条边，都是选择连接一对顶点的最小的加权边。

用Prim的算法寻找最小生成树有六个步骤。

例子

想象一下，下面的图代表一个机场网络。顶点是机场，边表示飞机从一个机场飞到另一个机场的燃料成本。

让我们开始通过这个例子进行工作。

  1. 在图中选择任何一个顶点。让我们假设你选择了顶点2。

  2. 这个顶点的边的权重为[6, 5, 3]。一个贪婪的算法会选择权重最小的边。

  3. 选择权重为3的边，并与顶点5相连。

  4. 所探索的顶点是{2，5}。

  5. 从已探索的顶点中选择下一条最短的边。这些边是[6，5，6，6]。你选择权重为5的边，它与顶点3相连。

  6. 注意，顶点5和顶点3之间的边可以从考虑中删除，因为它已经是生成树的一部分。

  1. 探索的顶点是{2，3，5}。

  2. 接下来的潜在边是[6, 1, 5, 4, 6]。你选择权重为1的边，它与顶点1相连。

  3. 顶点2和顶点1之间的边可以被移除。

  4. 探索的顶点是{2, 3, 5, 1}。

  5. 从已探索的顶点中选择下一条最短的边。这些边是[5, 5, 4, 6]。你选择权重为4的边，它与顶点6相连。

  6. 顶点5和顶点6之间的边可以被删除。

  1. 所探索的顶点是{2, 5, 3, 1, 6}。

  2. 从已探索的顶点中选择下一条最短的边。这些边是[5，5，2]。你选择权重为2的边，它与顶点4相连。

  3. 从顶点1和顶点3连接到顶点4的边[5，5]可以被删除。

注意：如果所有的边都有相同的权重，你可以选择其中的任何一条。

这张最后的图是我们的例子中由Prim算法产生的最小生成树。

接下来，让我们看看如何在代码中建立这个。

实现

打开本章的起始游戏场。这个操场带有一个邻接列表图和一个优先级队列，你将用它来实现Prim的算法。

优先级队列用于存储探索过的顶点的边。它是一个最小优先级队列，所以每次当你取消排队时，它会给你权重最小的那条边。

首先定义一个Prim类。打开Prim.swift，添加以下内容。

public class Prim<T: Hashable> {

  public typealias Graph = AdjacencyList<T>
  public init() {}
}

Graph被定义为AdjacencyList的一个类型别名。在未来，如果需要的话，你可以用一个邻接矩阵来代替它。

帮助方法

在构建算法之前，你将创建一些辅助方法，以保持你的组织性并合并重复的代码。

复制一个图

要创建一个最小生成树，你必须包括原图的所有顶点。打开AdjacencyList.swift，在AdjacencyList类中添加以下内容。

这就把一个图的所有顶点复制到一个新的图中。

寻找边

除了复制图形的顶点，你还需要找到并存储你探索的每个顶点的边。打开Prim.swift，在Prim类中添加以下内容。

这个方法接收了四个参数。

  1. 当前的顶点。

  2. 图，其中存储了当前的顶点。

  3. 已经访问过的顶点。

  4. 增加所有潜在边的优先队列。

在这个函数中，你要做以下工作。

  1. 查看与当前顶点相邻的每一条边。

  2. 检查目标顶点是否已经被访问过。

  3. 如果它没有被访问过，你就把这条边添加到优先级队列中。

现在你已经建立了辅助方法，你可以实现Prim的算法。

生成最小生成树

在类Prim中添加以下方法。


下面是你目前拥有的东西。

  1. produceMinimumSpanningTree接收一个无向图，并返回一个最小生成树和它的成本。

  2. cost跟踪最小生成树中各条边的总权重。

  3. 这是一个图，将成为你的最小生成树。

  4. visited存储所有已经被访问过的顶点。

  5. 这是一个最小优先级的队列，用来存储边。

接下来，继续用下面的方法实现 produceMinimumSpanningTree。

这段代码启动了该算法。

  1. 将原图中的所有顶点复制到最小生成树中。

  2. 从图中获取起始顶点。

  3. 将起始顶点标记为已访问。

  4. 将所有从起始顶点开始的潜在边添加到优先级队列中。

最后，用以下方法完成produceMinimumSpanningTree。


翻阅代码。

  1. 继续Prim的算法，直到边的队列为空。

  2. 获取目标顶点。

  3. 如果这个顶点已经被访问过了，重新开始循环，得到下一个最小的边。

  4. 将目标顶点标记为已访问。

  5. 把边的权重加到总成本中。

  6. 将最小的边加入你正在构建的最小生成树中。

  7. 添加当前顶点的可用边。

  8. 一旦优先级队列为空，返回最小成本和最小生成树。

测试你的代码

导航到主操场，你会看到上面的图已经用邻接列表构造好了。

现在是时候看看Prim的算法的作用了。添加以下代码。

let (cost,mst) = Prim().produceMinimumSpanningTree(for: graph) 
print("cost: \(cost)") 
print("mst:") 
print(mst)

这段代码从例子部分构造了一个图。你会看到以下输出。

cost: 15.0 
mst:
5 ---> [ 2 ] 
6 ---> [ 3, 4 ] 
3 ---> [ 2, 1, 6 ] 
1 ---> [ 3 ] 
2 ---> [ 5, 3 ] 
4 ---> [ 6 ]

性能

在上面的算法中，你维护了三个数据结构。

  1. 建立最小生成树的邻接列表图。将顶点和边添加到邻接列表中是O(1)。

  2. 一个集合，用于存储所有你访问过的顶点。向集合添加顶点和检查集合是否包含一个顶点的时间复杂度也是O(1)。

  3. 一个最小优先级队列，当你探索更多的顶点时存储边。优先级队列建立在一个堆上，插入需要O(log E)。

Prim算法的最坏情况下的时间复杂性是O(E log E)。每次你从优先级队列中提取最小的边时，你必须遍历目的地顶点的所有边( O(E))，并将该边插入优先级队列( O(logE))。

关键点

上一章 目录 下一章