数据结构之图的最小生成树_在已确定的图上找最小生成树

我是自动化专业的应届研究生，最终拿到了tplink、华为、vivo等公司的ssp的offer，分享自己学习过的计算机基础知识（C语言+操作系统+计算机网络+linux）以及数据结构与算法的相关知识，保证看完让你有所成长。
欢迎关注我，学习资料免费分享给你哦！还有其他超多学习资源，都是我自己学习过的，经过过滤之后的资源，免去你还在因为拥有大量资源不知如何入手的纠结，让你体系化学习。

最小生成树的概念

所谓的最小生成树就是在一个图中（N个顶点）选出一些边（N-1）使图中所有的顶点都连通，而且所花费的权重最小，如果在添加一条边，就构成了环路。

Prim算法

Prim算法的思想是从顶点出发，一个顶点一个顶点的选取，怎么选取呢？选取边的权值最小的顶点添加到最小生成树中。

首先初始化一个dist数组，这个数组表示的是顶点到最小生成树的最小距离。什么意思呢？假设首先将1添加到最小生成树中，那么对于0，2，3都是相邻的边，那么它们到达最小生成树的距离就是4，1，2其余顶点因为不能到达最小生成树，所以dist值都为无穷大。

如果下一次把3添加到最小生成树中，那么此时0到最小生成树的距离就会变为2，因为边03的权值更小，即dist[0]=2,此时4，5，6的dist值也会更新。所以dist数组表示的意思就是顶点到最小生成树的最小距离。

所以这个算法的思路就是首先将一个顶点添加到最小生成树中，然后将其dist[i]=0,更新其余dist值，判断与它有边的顶点d，如果顶点d没有加入到最小生成树中（dist[d]值是否为0就可以判断），然后在判断边id的权值与dist[d]的大小，如果dist[d]>边id，说明i点添加到最小生成树后，d点到最小生成树的距离变小了。然后扫描dist数组，找出下一个要添加的顶点，直到所有顶点都添加到了最小生成树中。如果此时最小生成树中的顶点数=图的顶点数。说明最小生成树可以生成，如果不是，说明不存在最小生成树。以上图为例寻找一个最小生成树。初始化一个dist数组。

假设先从1开始寻找，那么把dist[1]=0添加到最小生成树中，然后更新其余顶点到最小生成树的距离。

接下来找到dist值最小的顶点，也就是距离生成树最近的顶点3，然后把3添加到生成树中，也就是把13这个边添加到了生成树了。

然后更新各个顶点到最小生成树的距离，也就与3相连接且没有添加到最小生成树的节点，0，2，4，5，6，更新他们的dist，因为边03权值小，所以dist[0]=2,但是边23权值大于dist[2]，所以不更新，其余节点都需要更新。

然后接下来找到最小的dist，比如是顶点0，重复上述过程，更新dist。

之后就是选择顶点2，没有可以更新的dist，然后是顶点4，也没有可以更新的，然后是顶点5，因为边56权值小于dist[6],更新dist[6],最后一个节点6,完成了最小生成树。

代码如下：

int find_min(Graph graph,int *weight)//寻找最小的dist，不存在就返回-1
{
   
	int i=0;
	int d=-1;
	int min_weight=INT_MAX;
	for(i=0;i<graph->Nv;i++)
	{
   
		
		if(weight[i]!=0&&weight[i]<min_weight)
		{
   
			min_weight=weight[i];
			d=i;
		}
	}
	if(min_weight==INT_MAX)
	{
   
		return -1;
	}
	else
	{
   
		return d;
	}
}
int Prim(Graph graph,int d) //图是邻接表实现
{
   
    int *dist;
	int t,count=0;
	Gnode tmp;
	int weight=0;
	dist=(int *)malloc(sizeof(int)*graph->Nv);
	if(dist==NULL)
	{
   
		return -1;
	}
	for(t=0;t<graph->Nv;t++)
	{
   
		dist[t]=INT_MAX;
	}
    dist[d]=0;
	for(tmp=graph->G[d].next;tmp!=NULL;tmp=tmp->next)
	{
   
        dist[tmp->end]=tmp->weight
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50