最小生成树(Minimum Spanning Tree, MST)中的 Prim 算法详解(C语言实现)

1. 什么是最小生成树?

在学习 Prim 算法之前,我们首先需要理解什么是最小生成树(Minimum Spanning Tree,MST)。


1.1 图的基本概念

图(Graph)通常表示为:

\[ G=(V,E) \]

其中:

  • V:顶点集合(Vertex)
  • E:边集合(Edge)

例如:

        2
    A ------- B
    | \       |
  6 |  \3     | 1
    |   \     |
    C ------- D
        4

顶点集合:

V={A,B,C,D}

边集合:

E={(A,B),(A,C),(A,D),(B,D),(C,D)}

如果每条边具有一个权值,那么这个图称为:

带权无向图(Weighted Undirected Graph)

例如:

A-B = 2

A-C = 6

A-D = 3

B-D = 1

C-D = 4

2. 什么是生成树?

对于一个连通图,如果选择其中一部分边,使其满足:

  1. 包含所有顶点
  2. 任意两个顶点之间都有路径
  3. 不存在环

那么得到的子图称为:

生成树(Spanning Tree)

例如:

原图:

A ----- B
| \     |
|  \    |
C ----- D

选择:

A-B

A-C

B-D

得到:

A ----- B
|
|
C

B ----- D

满足:

  • 所有节点都连接
  • 没有环

所以它是一棵生成树。


3. 什么是最小生成树?

一个图可能存在很多棵生成树。

不同生成树的边权值总和不同。

例如:

生成树1

选择:

A-B = 2

B-D = 1

D-C = 4

总权值:

\[ 2+1+4=7 \]

生成树2

选择:

A-D = 3

D-B = 1

A-C = 6

总权值:

\[ 3+1+6=10 \]

显然:

第一棵树权值更小。

因此:

权值总和最小的生成树称为最小生成树。


4. Prim算法基本思想

Prim算法是一种典型的:

贪心算法(Greedy Algorithm)

它的核心思想:

从任意一个顶点开始,每次选择连接当前生成树和外部节点的最小权值边,将新的节点加入生成树。

可以理解为:

已经加入生成树的节点

          |

          |

寻找最短边

          |

          |

加入新的节点

不断重复这个过程,直到所有节点都加入。


5. Prim算法执行过程

假设有如下图:

        2
    A ------- B
    |         |
  6 |         | 1
    |         |
    C ------- D
        4

A-D = 3

对应邻接矩阵:

      A   B   C   D

A     0   2   6   3

B     2   0   ∞   1

C     6   ∞   0   4

D     3   1   4   0

其中:

  • 0表示自己到自己
  • ∞表示两个节点之间没有直接连接

第一步:选择起点A

当前生成树:

A

已经加入:

U={A}

寻找连接A的最小边:

A-B=2

A-D=3

A-C=6

最小:

A-B=2

加入B。

现在:

U={A,B}

生成树:

A------B

   2

第二步:选择D

当前:

已经加入:

A,B

未加入:

C,D

寻找最小边:

A-D=3

A-C=6

B-D=1

最小:

B-D=1

加入D。

现在:

U={A,B,D}

生成树:

A------B
       |
       |
       D

第三步:选择C

剩余节点:

C

连接C的边:

A-C=6

D-C=4

选择:

D-C=4

加入C。

最终:

A------B
       |
       |
       D
       |
       C

总权值:

\[ 2+1+4=7 \]

这就是最小生成树。


6. Prim算法中的三个核心数组

在程序实现中,需要维护三个重要数组:


6.1 visited数组

作用:

判断某个顶点是否已经加入最小生成树。

例如:

visited[i]=1;

表示:

节点i已经加入MST

例如:

节点:

A B C D


visited:

1 1 0 1

表示:

A、B、D已经加入。


6.2 lowcost数组

作用:

保存当前生成树连接每个未加入节点的最小边权值。

例如:

当前:

生成树:

A,B

对于节点:

C:

A-C=6

D:

B-D=1

因此:

lowcost[C]=6

lowcost[D]=1

Prim算法每一步就是:

寻找:

lowcost最小的节点

然后加入。


6.3 parent数组

作用:

记录当前节点由哪个节点连接进来。

例如:

D通过B加入:

parent[D]=B

最终可以得到:

A-B

B-D

D-C

7. Prim算法流程总结

伪代码:

Prim(G)

1. 初始化visited数组

2. 选择一个起点

3. 将起点加入生成树


4. 重复 n-1 次:

      找到lowcost最小的节点k

      将k加入生成树

      更新其它节点的lowcost


5. 输出最小生成树

8. C语言实现(邻接矩阵)

8.1 完整代码

#include<stdio.h>


#define MAX 100

#define INF 999999



void Prim(int graph[MAX][MAX], int n)
{

    int visited[MAX]={0};

    int lowcost[MAX];

    int parent[MAX];


    //初始化

    for(int i=0;i<n;i++)
    {
        lowcost[i]=graph[0][i];

        parent[i]=0;
    }


    //默认从0号节点开始

    visited[0]=1;


    int sum=0;



    //加入n-1条边

    for(int i=1;i<n;i++)
    {

        int min=INF;

        int k=-1;



        //寻找最小边

        for(int j=0;j<n;j++)
        {

            if(!visited[j] && lowcost[j]<min)
            {

                min=lowcost[j];

                k=j;

            }

        }



        //加入节点k

        visited[k]=1;



        printf("%d -- %d  权值:%d\n",
               parent[k],
               k,
               lowcost[k]);



        sum+=lowcost[k];



        //更新lowcost

        for(int j=0;j<n;j++)
        {

            if(!visited[j] &&
               graph[k][j]<lowcost[j])
            {

                lowcost[j]=graph[k][j];

                parent[j]=k;

            }

        }

    }



    printf("最小生成树权值:%d\n",sum);

}



int main()
{

    int graph[MAX][MAX]=
    {

        {0,2,6,3},

        {2,0,INF,1},

        {6,INF,0,4},

        {3,1,4,0}

    };


    Prim(graph,4);


    return 0;

}

9. 代码执行过程分析

初始化:

visited:

A B C D

1 0 0 0


lowcost:

0 2 6 3

第一次:

寻找最小:

B

因为:

lowcost[B]=2

加入:

A-B

更新:

D的距离变成1

第二次:

寻找:

D

因为:

lowcost[D]=1

加入:

B-D

第三次:

寻找:

C

因为:

lowcost[C]=4

加入:

D-C

最终:

A-B  权值2

B-D  权值1

D-C  权值4

总权值:

7

10. Prim算法时间复杂度分析

采用邻接矩阵实现。

每次寻找最小lowcost:

需要:

\[ O(V) \]

更新距离:

需要:

\[ O(V) \]

总共执行:

\[ V-1 \]

所以:

\[ O(V^2) \]

因此:

邻接矩阵版本Prim算法时间复杂度为 O(V²)


11. Prim算法与Kruskal算法比较

Prim算法 Kruskal算法
核心思想 扩展顶点 选择最小边
策略 点驱动 边驱动
主要数据结构 邻接矩阵 并查集
适合图 稠密图 稀疏图
时间复杂度 O(V²) O(ElogE)

12. 学习Prim算法需要掌握的重点

visited

表示:

哪些节点已经加入MST

lowcost

表示:

当前情况下,
生成树连接外部节点的最短距离

parent

表示:

当前节点由哪个节点连接进入MST

13. 一句话理解Prim算法

Prim算法就是从一个顶点开始,不断寻找距离当前生成树最近的节点,并把它加入生成树,直到所有节点都被连接,最终形成最小生成树。

整个过程:

选择起点

↓

寻找最近节点

↓

加入生成树

↓

更新距离

↓

重复

↓

得到MST