DSA 普里姆算法
普里姆算法由捷克数学家 Vojtěch Jarník 于 1930 年发明。
该算法随后由 Robert C. Prim 于 1957 年重新发现，并由 Edsger W. Dijkstra 于 1959 年重新发现。因此，该算法有时也被称为“Jarník 算法”或“Prim-Jarník 算法”。
普里姆算法
普里姆算法在一个连通的无向图中寻找最小生成树 (MST)。
普里姆算法找到的 MST 是图中所有顶点连接在一起的边的集合，且边的权重总和最小。
普里姆算法通过首先将一个随机顶点添加到 MST 来找到 MST。然后，算法查找当前 MST 中权重最低的顶点，并将其添加到 MST。普里姆算法不断重复此过程，直到所有节点都包含在 MST 中。
普里姆算法是贪心算法，它有一种简单的方法来创建一个最小生成树。
要使普里姆算法正常工作，所有节点都必须是连通的。要查找非连通图的 MST，可以使用 Kruskal 算法。下一页将介绍 Kruskal 算法。
工作原理
- 选择一个随机顶点作为起点，并将其包含为 MST 中的第一个顶点。
- 比较从 MST 发出的边。选择连接 MST 顶点和 MST 外部顶点的权重最低的边。
- 将该边和顶点添加到 MST。
- 重复步骤 2 和 3，直到所有顶点都属于 MST。
注意：由于起始顶点是随机选择的，因此同一图可能包含不同的 MST 边，但 MST 的总边权重仍然具有相同的最小值。
手动演练
让我们手动运行普里姆算法，以便在尝试编程之前理解详细的步骤。
普里姆算法从随机顶点开始生长最小生成树 (MST)，但在此演示中，顶点 A 被选为起始顶点。
从顶点 A 开始，MST 沿着权重最低的边生长。因此，顶点 A 和 D 现在属于属于最小生成树的顶点组。
一个 parents 数组是普里姆算法生长 MST 边方式的核心。
此时，parents 数组看起来像这样
parents = [-1, 0, -1, 0, 3, 3, -1, -1]
#vertices [ A, B, C, D, E, F, G, H]
起始顶点 A 没有父节点，因此其值为 -1。D 的父节点是 A，这就是为什么 D 的父节点值为 0（顶点 A 位于索引 0）。B 的父节点也是 A，D 是 E 和 F 的父节点。
parents 数组帮助我们维护 MST 的树结构（一个顶点只能有一个父节点）。
此外，为了避免循环并跟踪当前在 MST 中的顶点，使用了 in_mst 数组。
此时，in_mst 数组看起来像这样
in_mst = [ true, false, false, true, false, false, false, false]
#vertices [ A, B, C, D, E, F, G, H]
普里姆算法的下一步是包含一个新顶点作为 MST 的一部分，并选择最接近当前 MST 节点 A 和 D 的顶点。
由于 A-B 和 D-F 的权重都相同，最低边权重为 4，因此可以选择 B 或 F 作为下一个 MST 顶点。在此演示中，我们选择 B 作为下一个 MST 顶点。
如您所见，到 E 的 MST 边之前来自顶点 D，现在来自顶点 B，因为 B-E 的权重 6 低于 D-E 的权重 7。顶点 E 在 MST 树结构中（以及在 parents 数组中）只能有一个父节点，因此 B-E 和 D-E 不能同时成为到 E 的 MST 边。
MST 的下一个顶点是 C，因为 B-C 边的权重 3 是当前 MST 顶点之间的最短边权重。
随着顶点 C 被包含在 MST 中，会检查 C 的出边，以确定是否有权重更低的边从该 MST 顶点连接到 MST 外部的顶点。C-E 边的权重（3）低于之前的 B-E MST 边（6），并且 C-H 边以权重 2 被包含在 MST 中。
顶点 H 是下一个要包含在 MST 中的顶点，因为它具有最低的边权重 6，并且顶点 H 在 parents 数组中成为顶点 G 的父节点。
下一个要包含在 MST 中的顶点是 E 或 F，因为它们都有最低的边权重：4。
在此演示中，我们选择顶点 E 作为下一个要包含在 MST 中的顶点。
下一个和最后两个要添加到 MST 的顶点是 F 和 G。D-F 是到 F 的 MST 边，E-G 是到 G 的 MST 边，因为这些边是当前 MST 的最低权重边。
运行下面的模拟，查看普里姆算法执行我们刚刚完成的手动步骤。
普里姆算法实现
为了让普里姆算法找到最小生成树 (MST)，我们创建一个 Graph 类。稍后我们将使用此 Graph 类中的方法来创建上面示例中的图，并在其上运行普里姆算法。
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data第 3-5 行：起初，邻接矩阵为空，表示图中没有边。此外，顶点一开始没有名称。
第 7-10 行： add_edge 方法用于在无向图中添加一条带权重的边。
第 12-14 行： add_vertex_data 方法用于为顶点命名，例如“A”或“B”。
现在图的创建结构已经到位，我们可以在 Graph 类中实现普里姆算法作为一种方法。
def prims_algorithm(self):
in_mst = [False] * self.size
key_values = [float('inf')] * self.size
parents = [-1] * self.size
key_values[0] = 0 # Starting vertex
print("Edge \tWeight")
for _ in range(self.size):
u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v])
in_mst[u] = True
if parents[u] != -1: # Skip printing for the first vertex since it has no parent
print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}")
for v in range(self.size):
if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:
key_values[v] = self.adj_matrix[u][v]
parents[v] = u第 17 行： in_mst 数组保存当前哪些顶点属于 MST 的状态。最初，没有顶点是 MST 的一部分。
第 18 行： key_values 数组保存从 MST 顶点到 MST 外部每个顶点的当前最短距离。
第 19 行： MST 边存储在 parents 数组中。每条 MST 边通过存储每个顶点的父索引来存储。
第 21 行：为了简单起见，并使此代码像上面的“手动运行”动画/示例一样运行，第一个顶点（索引 0 处的顶点 A）被设置为起始顶点。将索引更改为 4 将从顶点 E 运行普里姆算法，这也同样有效。
第 25 行：找到具有最低键值且尚未属于 MST 的顶点的索引。查看这些对 min 和 lambda 的解释，以更好地理解这一 Python 代码行。
第 32-35 行：将一个新顶点添加到 MST 后（第 27 行），代码的这部分会检查从这个新添加的 MST 顶点是否有可能降低到 MST 外部其他顶点的键值。如果存在这种情况，则相应地更新 key_values 和 parents 数组。在动画中，当一个新顶点被添加到 MST 并成为活动（当前）顶点时，这一点就很清楚了。
现在，让我们创建上面“手动运行”中的图，并在其上运行普里姆算法。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def prims_algorithm(self):
in_mst = [False] * self.size
key_values = [float('inf')] * self.size
parents = [-1] * self.size
key_values[0] = 0 # Starting vertex
print("Edge \tWeight")
for _ in range(self.size):
u = min((v for v in range(self.size) if not in_mst[v]), key=lambda v: key_values[v])
in_mst[u] = True
if parents[u] != -1: # Skip printing for the first vertex since it has no parent
print(f"{self.vertex_data[parents[u]]}-{self.vertex_data[u]} \t{self.adj_matrix[u][parents[u]]}")
for v in range(self.size):
if 0 < self.adj_matrix[u][v] < key_values[v] and not in_mst[v]:
key_values[v] = self.adj_matrix[u][v]
parents[v] = u
g = Graph(8)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_vertex_data(7, 'H')
g.add_edge(0, 1, 4) # A - B
g.add_edge(0, 3, 3) # A - D
g.add_edge(1, 2, 3) # B - C
g.add_edge(1, 3, 5) # B - D
g.add_edge(1, 4, 6) # B - E
g.add_edge(2, 4, 4) # C - E
g.add_edge(2, 7, 2) # C - H
g.add_edge(3, 4, 7) # D - E
g.add_edge(3, 5, 4) # D - F
g.add_edge(4, 5, 5) # E - F
g.add_edge(4, 6, 3) # E - G
g.add_edge(5, 6, 7) # F - G
g.add_edge(6, 7, 5) # G - H
print("Prim's Algorithm MST:")
g.prims_algorithm()第 32 行：通过将此行更改为 for _ in range(self.size - 1):，我们可以避免普里姆算法的最后一个循环。这是因为当只有一个顶点尚未包含在 MST 中时，该顶点的父顶点已在 parents 数组中正确设置，因此 MST 实际上在此点已经找到。
普里姆算法的时间复杂度
有关时间复杂度的一般性解释，请访问此页面。
设 \(V\) 为我们图中顶点的数量，普里姆算法的时间复杂度为
\[ O( V^2 ) \]
我们得到此时间复杂度的原因是普里姆算法内部的嵌套循环（一个 for 循环包含另外两个 for 循环）。
第一个 for 循环（第 24 行）遍历图中的所有顶点。其时间复杂度为 \(O(V)\)。
第二个 for 循环（第 25 行）遍历图中的所有相邻顶点，以查找具有最低键值且不在 MST 中的顶点，以便它可以是下一个包含在 MST 中的顶点。其时间复杂度为 \(O(V)\)。
在将一个新顶点包含在 MST 中后，第三个 for 循环（第 32 行）会检查所有其他顶点，以查看新添加的 MST 顶点是否有指向 MST 外部顶点的出边，这些边可能导致较低的键值和更新的父关系。此操作的时间复杂度也为 \(O(V)\)。
将时间复杂度组合起来，我们得到
\[ \begin{equation} \begin{aligned} O(V)\cdot (O(V)+O(V)) & = O(V)\cdot (2\cdot O(V)) \\ & = O(V\cdot 2\cdot V) \\ & = O(2\cdot V^2) \\\\ & = O(V^2) \end{aligned} \end{equation} \]
通过使用优先队列数据结构来管理键值，而不是像这里那样使用数组，普里姆算法的时间复杂度可以降低到
\[ O( E \cdot \log{V}) \]
其中 \(E\) 是图中的边数，\(V\) 是顶点数。
使用优先队列实现普里姆算法对于稀疏图是最佳的。当每个顶点只连接到其他少数几个顶点时，该图就是稀疏的。
