Prim算法生成最小生成树

Prim算法是一种常见的求解最小生成树的算法，它的基本思想是从一个顶点开始，逐渐向外扩展生成最小生成树。具体实现过程如下：

1. 首先选定一个起始节点，将该节点加入生成树中。

2. 扫描与该节点相邻的所有节点，并记录它们到起始节点的边的权值，选取其中最小的边所连的节点，并将该节点加入生成树中。

3. 重复步骤2，直到所有节点都被加入到生成树中。

在实现Prim算法时，可以使用一个数组来记录每个节点是否已经被访问过，并且记录每个节点到已经访问过的节点的距离。每次选择距离最近的节点作为下一个访问的节点，直到所有节点都被访问为止。

相关问题

如何用Prim算法生成最小生成树

Prim算法是一种用于生成最小生成树的贪心算法。下面是Prim算法的基本思想和步骤：

1. 随机选择一个顶点作为起始点，将其加入到最小生成树中。
2. 从已经加入最小生成树的顶点集合出发，找到与其相邻的顶点中权值最小的边，将该边连接的顶点加入到最小生成树中。
3. 重复步骤2，直到所有的顶点都被加入到最小生成树中。

具体实现时，可以使用一个优先队列（或堆）来维护与已加入最小生成树的顶点相邻的顶点和边的权值，并选择其中权值最小的边进行加入。

下面是Prim算法的伪代码：

Prim(G, s):
    for each vertex v in G:
        key[v] = infinity
        parent[v] = null
    key[s] = 0
    Q = priority queue containing all vertices
    while Q is not empty:
        u = vertex in Q with smallest key value
        remove u from Q
        for each neighbor v of u:
            if v is still in Q and weight(u, v) < key[v]:
                parent[v] = u
                key[v] = weight(u, v)
                decrease-key(Q, v, key[v])
    return parent

其中，`G`是一个加权无向图，`s`是起始点，`key[v]`表示从起始点到顶点`v`的最小权值，`parent[v]`表示最小生成树中顶点`v`的父节点，`decrease-key(Q, v, key[v])`表示将优先队列`Q`中顶点`v`的权值减小为`key[v]`。

带权无向图Prim算法生成最小生成树

### 使用Prim算法构建最小生成树

#### 初始化阶段
对于给定的一个连通无向加权图 \(G = (V, E)\)，其中\(V\)表示顶点集合，而\(E\)则代表边集。为了初始化Prim算法，选取任意一个起始节点作为根节点，并将其加入到已访问过的节点列表中。

#### 边的选择过程
在每一轮迭代过程中，从未被选中的边集中挑选一条连接已被纳入MST（Minimal Spanning Tree）部分的节点与其他未加入该结构的新节点之间的最短路径上的边[^1]。这条边应当满足两个条件：一是它的一端位于当前形成的MST内；二是另一端处于尚未处理的部分之中。通过这种方式逐步扩展直到所有的顶点都被包含进来为止。

#### 实现细节
下面是一个基于Python实现的简单版本：

import sys
from collections import defaultdict


class Graph:

    def __init__(self, vertices):
        self.V = vertices  
        self.graph = [[0 for column in range(vertices)] 
                      for row in range(vertices)]

    
    # A utility function to find the vertex with minimum distance value,
    # from the set of vertices not yet included in shortest path tree.
    def minKey(self, key, mstSet):

        # Initialize min value
        min_val = sys.maxsize
        min_index = None
        
        for v in range(self.V):
            if key[v] < min_val and mstSet[v] == False:
                min_val = key[v]
                min_index = v
                
        return min_index
    
        
    def primMST(self):
        key = [sys.maxsize] * self.V  # Key values used to pick minimum weight edge in cut
        parent = [None] * self.V      # Array to store constructed MST
        key[0] = 0                    # Make key 0 so that this vertex is picked as first vertex
        mstSet = [False] * self.V     # To represent set of vertices not yet included in MST.

        parent[0] = -1                 # First node is always root of MST 

        for cout in range(self.V):     # The following loop traverses other V-1 vertices

            u = self.minKey(key, mstSet)

            mstSet[u] = True           # Add the picked vertex to the MST Set
            
            # Update key value and parent index of the adjacent vertices of the picked vertex.
            for v in range(self.V):
                
                # graph[u][v] is non zero only for adjacent vertices of m
                # mstSet[v] is false for vertices not yet included in MST
                # Update the key only if graph[u][v] is smaller than key[v]
                if ((self.graph[u][v] > 0) and 
                   mstSet[v] == False and 
                   key[v] > self.graph[u][v]):
                       key[v] = self.graph[u][v]
                       parent[v] = u
                        
                        
        print ("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

此代码片段展示了如何利用邻接矩阵来存储图的信息并执行Prim算法以找到最小生成树。每次循环都会选出一个新的节点及其对应的最优边加入到正在增长的MST中去[^4]。