数据结构-最小生成树Prim算法的实现

悠悠 2024-03-17 11:21 49阅读 0赞

**目录**

一、前言

二、最小生成树

三、Prim算法

四、Prim算法的实现

--------------------

## 一、前言 ##

在计算机科学中，数据结构是一种组织和存储数据的方式，以便于访问和修改。数据结构是计算机科学的基础，它是算法的基础。在数据结构中，最小生成树是一种非常重要的概念。最小生成树是一个无向图的生成树，它的所有边的权值之和最小。最小生成树在许多领域都有广泛的应用，如网络设计、电路设计、城市规划等。

在本文中，我们将介绍最小生成树中的Prim算法，并用C++实现。我们将首先介绍最小生成树的概念，然后介绍Prim算法的原理和实现方法。最后，我们将给出C++代码实现，并对代码进行解析。

## 二、最小生成树 ##

最小生成树是一个无向图的生成树，它的所有边的权值之和最小。生成树是一个无向图的子图，它包含了原图的所有节点，并且是一个树结构。最小生成树可以用来解决许多问题，如网络设计、电路设计、城市规划等。

最小生成树有两种常见的算法：Prim算法和Kruskal算法。在本文中，我们将介绍Prim算法。

## 三、Prim算法 ##

Prim算法是一种贪心算法，它用于求解最小生成树。Prim算法的基本思想是从一个节点开始，不断地向外扩展，直到生成树包含了所有的节点。在扩展的过程中，我们选择与当前生成树相连的边中权值最小的边，并将其加入到生成树中。这个过程一直持续到生成树包含了所有的节点。

Prim算法的伪代码如下：

1. 从任意一个节点开始，将其加入到生成树中。  
2. 对于生成树中的每个节点，找到与其相连的边中权值最小的边，并将其加入到生成树中。  
3. 重复步骤2，直到生成树包含了所有的节点。

## 四、Prim算法的实现 ##

以下是C++实现Prim算法的示例代码：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <cstring>
    using namespace std;
    
    const int MAXN = 1005;
    const int INF = 0x3f3f3f3f;
    
    int n, m;
    int g[MAXN][MAXN]; // 存储图的邻接矩阵
    int dist[MAXN]; // 存储每个节点到最小生成树的距离
    bool vis[MAXN]; // 标记每个节点是否已经加入最小生成树
    
    int prim() {
        memset(dist, INF, sizeof(dist));
        memset(vis, false, sizeof(vis));
        dist[1] = 0; // 从节点1开始构建最小生成树
        int ans = 0; // 最小生成树的权值和
        for (int i = 1; i <= n; i++) {
            int u = -1;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;
                }
            }
            vis[u] = true;
            ans += dist[u];
            for (int v = 1; v <= n; v++) {
                if (!vis[v] && g[u][v] < dist[v]) {
                    dist[v] = g[u][v];
                }
            }
        }
        return ans;
    }
    
    int main() {
        cin >> n >> m;
        memset(g, INF, sizeof(g));
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u][v] = g[v][u] = w;
        }
        int ans = prim();
        cout << ans << endl;
        return 0;
    }

该算法的时间复杂度为 ![$O(n^2)$][O_n_2]，其中 ![$n$][n]表示节点数。如果使用堆优化可以将时间复杂度优化到 ![$O(m \\log n)$][O_m _log n]，其中 ![$m$][m] 表示边数。

这段代码实现了最小生成树算法的 Prim 算法。最小生成树是指在一个无向连通图中，找到一个生成树，使得这个生成树的所有边的权值之和最小。

具体实现过程如下：

1. 初始化 dist 数组为 INF，表示所有节点到最小生成树的距离都为无穷大，vis 数组为 false，表示所有节点都未被加入最小生成树。

2. 从节点 1 开始构建最小生成树，将 dist\[1\] 设为 0。

3. 在未加入最小生成树的节点中，找到距离最小的节点 u，将其加入最小生成树，并将 ans 加上 dist\[u\]。

4. 更新与节点 u 相邻的未加入最小生成树的节点 v 的 dist\[v\]，如果 g\[u\]\[v\] < dist\[v\]，则更新 dist\[v\] 为 g\[u\]\[v\]。

5. 重复步骤 3 和 4，直到所有节点都被加入最小生成树。

6. 返回 ans，即为最小生成树的权值和。

其中，g 数组存储了图的邻接矩阵，表示节点之间的边和权值。在输入时，将边的权值存入 g 数组中。

[O_n_2]: https://latex.csdn.net/eq?%24O%28n%5E2%29%24
[n]: https://latex.csdn.net/eq?%24n%24
[O_m _log n]: https://latex.csdn.net/eq?%24O%28m%20%5Clog%20n%29%24
[m]: https://latex.csdn.net/eq?%24m%24