prim算法基础详解（无向赋权图的最小生成树MST）

带权图分为有向和无向，无向图的最短路径又叫做最小生成树，有prime算法和kruskal算法

生成树的概念：联通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树生成树是联通图的极小连通子图。

所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。生成树各边的权值总和称为生成树的权。

权最小的生成树称为最小生成树，常用的算法有prime算法和kruskal算法。这里仅介绍prime算法..

算法描述如下：

1.将所有的结点分成两个集合。一部分是在最小生成树中的点（记为集合A），另一部分是不在最小生成树中的点（即待加入的点，记为集合B）。

2.开始的时候取任意一个点v作为顶点加入最小生成树中（A），然后遍历集合B，选取一个点vj使得（v，vj）的权值最小，然后将vj加入A集合，B集合中删去vj（删去操作可以用一个intree[i]数组来进行操作）

3.重复2步骤直到所有点遍历完毕。

注意：这里说的重复步骤2是指每次找的与顶点v的边权值最小的结点！

结合例子来看一下。（如下图）

prim算法基础详解（无向赋权图的最小生成树MST）

选择1为初始结点，intree[1]标记为1.

遍历剩下的6个结点，找到（1，vj）中weight最小的那一个，显然是3，让3加入集合A，即intree[3]标记为1

prim算法基础详解（无向赋权图的最小生成树MST）

然后注意此时集合A中有了两个元素（结点1和结点3）开始的时候我认为是从3开始遍历找3与其他点的最小权值，但是再次注意我们每次只找与顶点（这里就1结点）边权值最小的点。

3结点入队后，1就可以与5结点间接相连了，所以每次在A中加入一个结点，都要更新顶结点与其他结点的关联与否以及权值。

这一点非常重要是算法的重要步骤。

正如此时（1,5） = 8 （1,4） = 5 （1,2） = 6 ，显然下一次应该加入A集合的是点4，所以：

prim算法基础详解（无向赋权图的最小生成树MST）

接下来就是：

prim算法基础详解（无向赋权图的最小生成树MST）

附上代码及测试样例。

[cpp]view
plain copy

#include <stdio.h>  

#include <string.h>  

#define maxn 10  

#define INF  100000  

int node;  

int G[maxn + 1][maxn + 1];/*构建的图,必须是一个无向连通赋权图,G[i][j]存取权值*/   

int intree[maxn];/*结点i在最小生成树中*/   

int minweight[maxn];/*到i点的最小权重*/   

int sumweight;  

void initialize()  

{  

    memset(intree,0,sizeof(intree));  

    memset(minweight,0,sizeof(minweight));  

    for(int i = 0 ; i <= maxn ; i++)  

        for(int j = 0 ; j <= maxn ; j++)  

            G[i][j] = INF;  

    sumweight = 0;  

}  

void prime(int n)  

{  

    int node,Minweight;  

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

        minweight[i] = G[1][i];  

    /*先把1结点放进最小生成树，那么要知道1到其余结点的最小权重*/  

    intree[1] = 1;/*1点进入集合A,最小生成树集*/   

    for(int i = 2 ; i <= n ; i++)  

    /*一共n个点，已经把1加入最小生成树，那么还剩下n-1个点*/   

    {  

        Minweight = INF;  

        for(int j = 1 ; j <= n ; j++)  

        {  

            if(minweight[j] < Minweight && !intree[j])  

            {  

                Minweight = minweight[j];  

                node = j;  

            }  

        }  

        printf("选择的结点标号为：%d\n",node);   

        intree[node] = 1;  

        sumweight += Minweight;  

        /*每次在A中加入新的点，更新顶结点到各节点的权重*/   

        for(int j = 1 ; j <= n ; j++)  

            if(!intree[j] && minweight[j] > G[node][j])  

            /*更新B集合*/   

                minweight[j] = G[node][j];   

    }  

}  

int main()  

{  

    int Node,Edge;  

    int vertex1,vertex2,weight;  

    initialize();  

    scanf("%d%d",&Node,&Edge);  

    for(int i = 1 ; i <= Edge ; i++)  

    {  

        scanf("%d%d%d",&vertex1,&vertex2,&weight);  

        G[vertex1][vertex2] = weight;  

        G[vertex2][vertex1] = weight;  

    }  

    prime(Node);  

    printf("%d\n",sumweight);  

    return 0;  

}  

/* 

7 9 

1 2 6 

1 3 2 

1 4 5 

2 5 2 

2 7 4 

3 5 8 

4 6 7 

4 7 5 

5 6 10 

答案是25  

*/

图例描述

图例	说明	不可选	可选	已选（Vnew）
	此为原始的加权连通图。每条边一侧的数字代表其权值。	-	-	-
	顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。	C, G	A, B, E, F	D
	下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。	C, G	B, E, F	A, D
	算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。	C	B, E, G	A, D, F
	在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。点E最近，因此将顶点E与相应边BE高亮表示。	无	C, E, G	A, D, F, B
	这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。	无	C, G	A, D, F, B, E
	顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。	无	G	A, D, F, B, E, C
	现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。	无	无	A, D, F, B, E, C, G

c代码

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

#include<stdio.h>

#include<stdlib.h>

#definemax1000000000;

inta[1001][1001],d[1001],p[1001];

intmain(){

inti,j,k,m,n,min,ans,t;

intx,y,z;

scanf("%d%d",&n,&m);

for(i=1;i<=m;i++){

scanf("%d%d%d",&x,&y,&z);

a[x][y]=z;

a[y][x]=z;

}

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

d[i]=1000000000;

d[1]=0;

for(i=2;i<=n;i++){

min=max;

for(j=1;j<=n;j++)

if(!p[j]&&min>d[j])

min=d[j];

t=j;

}

p[t]=j;

for(j=1;j<=n;j++)

if(a[t][j]=0&&d[j]>a[t][j]){

d[j]=a[t][j];

ans+=min;

}

printf("%d",ans);

return0;

}

prim算法基础详解（无向赋权图的最小生成树MST）

图例描述

c代码

相关推荐