DSA 普里姆算法
普里姆算法由捷克数学家沃伊捷赫·亚尔尼克于 1930 年发明。
该算法后来在 1957 年被罗伯特·C·普里姆重新发现，并在 1959 年被艾兹格·W·迪克斯特拉重新发现。因此，该算法有时也被称为“亚尔尼克算法”或“普里姆-亚尔尼克算法”。
普里姆算法
普里姆算法在连通且无向图中找到最小生成树 (MST)。
普里姆算法找到的 MST 是图中连接所有顶点的边的集合，其边权之和最小。
普里姆算法首先将一个随机顶点包含到 MST 中，然后找到从当前 MST 到外部顶点的边权最小的顶点，并将其包含到 MST 中。普里姆算法不断重复此过程，直到所有节点都包含在 MST 中。
普里姆算法是一种贪心算法，它具有直接创建最小生成树的方法。
为了使普里姆算法起作用，所有节点必须是连通的。为了在非连通图中找到 MST，可以使用克鲁斯卡尔算法。您可以在下一页阅读关于克鲁斯卡尔算法的内容。
工作原理
- 选择一个随机顶点作为起点，将其作为 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 边被包含到 MST 中，边权为 2。
顶点 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 并成为活动（当前）顶点时，在动画中可以清楚地看到这一点。
现在让我们从上面的“手动运行”中创建图，并在其上运行 Prim 算法
示例
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): 来避免 Prim 算法中的最后一个循环。这是因为当只有一个顶点不在 MST 中时，该顶点的父顶点已经在 parents 数组中正确设置，因此实际上此时 MST 已经找到了。
Prim 算法的时间复杂度
有关时间复杂度的概括性解释，请访问 此页面。
设 \(V\) 为图中顶点的数量，Prim 算法的时间复杂度为
\[ O( V^2 ) \]
产生这种时间复杂度的原因是 Prim 算法中的嵌套循环（一个 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} \]
通过使用优先级队列数据结构来管理键值，而不是像这里一样使用数组，Prim 算法的时间复杂度可以降低到
\[ O( E \cdot \log{V}) \]
其中 \(E\) 是图中边的数量，\(V\) 是顶点的数量。
这种使用优先级队列实现 Prim 算法的方法最适合稀疏图。当每个顶点只连接到其他少数几个顶点时，图就是稀疏的。
