最小生成树Prim算法（邻接矩阵和邻接表）

Prim算法是一种用于求解最小生成树的算法，以下分别介绍邻接矩阵和邻接表两种实现方式。

1. 邻接矩阵实现

Prim算法的基本思想是从一个初始顶点开始，逐步向外扩展最小生成树。首先将初始顶点加入最小生成树中，然后将与该顶点相邻的所有边加入到候选边集中，从中选取最小的边加入到最小生成树中，同时把与该边相邻的顶点加入到最小生成树的顶点集合中。接着，从候选边集中删除已选的边，再将新加入的顶点的所有未访问过的边加入到候选边集中，重复上述步骤，直到最小生成树中包含n-1条边。

邻接矩阵实现的Prim算法需要使用一个一维数组记录各个顶点的状态，另一个一维数组记录候选边集中与各个顶点相连的最小边的权值。具体实现过程如下：

（1）初始化

将初始顶点v加入最小生成树中，将数组visited[v]标记为已访问，将所有与v相邻的边加入候选边集中，对于每个顶点i，设置dist[i]为邻接矩阵中v到i的距离。

（2）循环

重复以下步骤n-1次，直到生成完整的最小生成树：

1. 从候选边集中选取权值最小的边e，将其加入最小生成树中。

2. 将与e相连的顶点u加入最小生成树的顶点集合中，将visited[u]标记为已访问。

3. 更新候选边集，将与u相邻的未访问顶点i的dist值更新为邻接矩阵中u到i的距离，如果dist[i]值小于候选边集中与i相邻的最小边的权值，则更新该边的权值。

实现代码如下：

def prim(adj_matrix):
    n = len(adj_matrix)
    visited = [False] * n
    dist = [float('inf')] * n
    dist[0] = 0
    for i in range(n):
        min_dist = float('inf')
        u = -1
        for j in range(n):
            if not visited[j] and dist[j] < min_dist:
                min_dist = dist[j]
                u = j
        visited[u] = True
        for v in range(n):
            if not visited[v] and adj_matrix[u][v] < dist[v]:
                dist[v] = adj_matrix[u][v]
    return sum(dist)

2. 邻接表实现

邻接表实现的Prim算法需要使用一个堆（优先队列）来维护候选边集的顶点，具体实现过程如下：

（1）初始化

将初始顶点v加入最小生成树中，将数组visited[v]标记为已访问，将与v相邻的所有边加入堆中，对于每个顶点i，设置dist[i]为与v相邻的最小边的权值。

（2）循环

重复以下步骤n-1次，直到生成完整的最小生成树：

1. 从堆中选取权值最小的边e，将其加入最小生成树中。

2. 如果该边连接的另一个顶点u未被访问，则将u加入最小生成树的顶点集合中，将visited[u]标记为已访问。

3. 更新堆，将与u相邻的未访问顶点i的dist值更新为与u相邻的最小边的权值，如果dist[i]值发生了变化，则将i加入堆中。

实现代码如下：

import heapq

def prim(adj_list):
    n = len(adj_list)
    visited = [False] * n
    dist = [float('inf')] * n
    dist[0] = 0
    heap = [(0, 0)]
    while heap:
        min_dist, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        for v, w in adj_list[u]:
            if not visited[v] and w < dist[v]:
                dist[v] = w
                heapq.heappush(heap, (w, v))
    return sum(dist)

以上就是Prim算法的邻接矩阵和邻接表实现方式。