最小生成树（Prim算法）

1. 应用领域
   
2. 基本概念
   1）生成树：连通图的生成树是包含全部顶点的极小连通子图。（含有n-1条边）（从任意节点出发都能到达任意一个顶点）
   2）生成树代价：在无向连通网中，生成树上各边的权值之和。
   3）最小生成树：在无向连通网中，代价最小的生成树。
   
   4）MST性质：假设𝑮=(𝑽,𝑬)是一个连通图，𝑼是顶点集𝑽的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中 𝒖∊ 𝑼 ，𝒗∊(𝑽−𝑼)，则必存在一颗包含边(𝒖,𝒗)的最小生成树。
3. 算法的基本思想
   1）由MST性质——关键是如何找到连接U和V-U的最短边。
   
   2）

算法：Prim
输入：无向连通网G=(V，E)
输出：最小生成树T=(U，TE)
 1. 初始化：U = {v}； TE={ }； 
 2. 重复下述操作直到U = V： 
           2.1 在E中寻找最短边(i，j)，且满足i∈U，j∈V-U；
           2.2 U = U + {j}；
           2.3 TE = TE + {(i，j)}；

4. 运行实例
   

5. 存储结构
   1）采用邻接矩阵：因为需要不断读取任意两个顶点之间边的权值。
   2）如何存储连接U与V-U的候选最短边？
   
   含义：候选最短边（i,j）的权值为w，其中i∈V-U，j∈U

6. 算法详细描述
   1）初始时：

lowcost[v] = 0，表示将顶点v加入集合U中；

adjvex[i] = v;//相当于数组的下标是终点，里面的内容是起点（知识相当于，因为是无向图）
lowcost[i] = edge[v][i]（0 ≤ i ≤ n-1）

void Prim(MGraph *G, int v)                                       /*假设从顶点v出发*/
{   
    int i, j, k, adjvex[MaxSize], lowcost[MaxSize];
	for (i = 0; i < G->vertexNum; i++)  /*初始化辅助数组shortEdge*/
    {
        lowcost[i] = G->edge[v][i]; adjvex[i] = v;
    }
    lowcost[v] = 0;  /*将顶点v加入集合U*/                                                        

2）迭代：

设数组lowcost[n]中的最小权值是lowcost [j]，则令lowcost[j] = 0，表示将顶点 j 加入集合U中；
由于顶点 j 从集合V-U进入集合U，候选最短边集发生变化，需要更新：

lowcost[i] = min{lowcost[i], edge[i][j]}
adjvex[i] = j（如果edge[i][j] < lowcost[i]>//（0≤ i ≤ n-1）

	for (k = 1; k < G->vertexNum; k++) /*迭代n-1次*/
	{
	        j = MinEdge(lowcost, G->vertexNum) /*寻找最短边的邻接点j*/
	        printf("(%d, %d)%d ", j, adjvex[j], lowcost[j]);    
	        lowcost[j] = 0; 
	        for (i = 0; i < G->vertexNum; i++) /*调整数组shortEdge[n]*/
	        {
	            if G->edge[i][j] < lowcost[i] 
	            {
	                lowcost[i] = G->edge[i][j]; 
	                adjvex[i] = j;
	            }
	         }
	}
}

3）总体图示：

void Prim(MGraph *G, int v)                                       /*假设从顶点v出发*/
{   
    int i, j, k, adjvex[MaxSize], lowcost[MaxSize];
	for (i = 0; i < G->vertexNum; i++)  /*初始化辅助数组shortEdge*/
    {
        lowcost[i] = G->edge[v][i]; adjvex[i] = v;
    }
    lowcost[v] = 0;  /*将顶点v加入集合U*/        
    for (k = 1; k < G->vertexNum; k++) /*迭代n-1次*/
	{
	        j = MinEdge(lowcost, G->vertexNum) /*寻找最短边的邻接点j*/
	        printf("(%d, %d)%d ", j, adjvex[j], lowcost[j]);    
	        lowcost[j] = 0; 
	        for (i = 0; i < G->vertexNum; i++) /*调整数组shortEdge[n]*/
	        {
	            if G->edge[i][j] < lowcost[i] 
	            {
	                lowcost[i] = G->edge[i][j]; 
	                adjvex[i] = j;
	            }
	         }
	}
}

7. 实验

【问题描述】
若在n个城市之间建通信网络，架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网络的最小生成树问题。
实验要求：利用Prim算法求网的最小生成树。
实现提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。
【输入形式】
首先，输入一个n，表示有n（编号1-n）个城市，m表示有m条边，接下来m行，每行输入a，b，c三个正整数（以空格分隔）。

这是一张无向图表示a，b之间有造价（代价）c。（2<=n<=1000, 1<=m<=50000,  1<=a,b<=n， 1<=c<=10000）
【输出形式】
输出保证连通的通信网最小造价（代价）。

//最小生成树——Prime 
//邻接矩阵  无向图 
#include<stdio.h>
#include<stdlib.h>
#define Max 10001
#define MaxSize 1000
//1)图的数据类型 
typedef struct 
{
	int vertex[MaxSize];//存储点的信息 
	int edge[MaxSize][MaxSize];//存储边之间的邻接关系 
	int vertexNum,edgeNum;//点的个数，边的个数 
}MGraph;
//2)构造一个图 
MGraph  CreatGraph(int n,int m)
{
	MGraph G;
	int i,j,a,b,c;
	//点 边 
	G.vertexNum=n;
	G.edgeNum=m;
	//点的信息
	for(i=1;i<=G.vertexNum;i++)
	{
		G.vertex[i]=i;
	} 
	//边邻接关系的初始化
	for(i=1;i<=G.vertexNum;i++)
	{
		for(j=1;j<=G.vertexNum;j++)
		{
			if(i==j)
			{
				G.edge[i][j]=0;
			} 
			else
			{
				G.edge[i][j]=Max;
			}	
		}
	}
	//输入m行边的信息 
	for(i=1;i<=G.edgeNum;i++)
	{
		scanf("%d %d %d",&a,&b,&c);
		G.edge[a][b]=c;
		G.edge[b][a]=c;//无向图 
	} 
	return G;
}
//3)求最短边
int  MinEdge(int *lowcost,int n)
{
	int i,j=0,min=Max;
	for(i=1;i<=n;i++)
	{
		if(lowcost[i]<min&&lowcost[i]!=0)
		{
			min=lowcost[i];
			j=i;
		}
	}
	return j;
}
//4)核心算法
void Prim(MGraph G, int v,int n)                                       /*假设从顶点v出发*/
{   
    //int i, j=0, k, adjvex[n], lowcost[n];
    int i, j=0, k,lowcost[n];
    int sum=0;
	for (i = 1;i<=G.vertexNum;i++)  /*初始化辅助数组shortEdge*/
    {
        lowcost[i] = G.edge[v][i]; 
		//adjvex[i] = v;
    }
    lowcost[v] = 0;  /*将顶点v加入集合U*/        
    for (k = 1; k < G.vertexNum; k++) /*迭代n-1次*/
	{
	    j = MinEdge(lowcost, G.vertexNum); /*寻找最短边的邻接点j*/  
	    sum=sum+lowcost[j];
		lowcost[j] = 0; 
	    for (i = 1; i <=G.vertexNum; i++) /*调整数组shortEdge[n]*/
	    {
	        if (G.edge[i][j] < lowcost[i] )
	        {
	            lowcost[i] = G.edge[i][j]; 
	            //adjvex[i] = j;
	        }
	    }
	}
	printf("%d",sum);
} 
int main()
{
	int n,m;//场所，边 
	scanf("%d %d",&n,&m);
	//创造 
	MGraph G;
	G=CreatGraph(n,m);
	
	//Prim
	int v;
	v=1;
	Prim(G,v,n); 

	return 0;
}
 
 

8.例题
1）最小生成树是指（连通网中所有生成树中权值之和为最小的生成树）

2）任何一个无向连通图的最小生成树 （一棵或多棵）

3）已知某带权连通无向图采用邻接矩阵存储方法，邻接矩阵以三元组表形式给出，不包括主对角线元素在内的下三角形部分元素对应的各三元组分别为(2,1,16)，(3,1,20)，(3,2,11)，(4,1,19)，(4,3,22)，(5,2,6)，(5,3,14)，(5,4,18)，(6,2,5)，(6,5,9)，(5,1,∞)，(6,1,∞)，(4,2,∞)，(6,3,∞)，(6,4,∞)。该连通图的最小生成树的权值是 （56）。