最小生成树算法总结

迷南。 2022-04-03 05:14 179阅读 0赞

# 最小生成树算法总结 #

## 1前言 ##

最小生成树的定义,\[最小生成树\]\[[https://baike.baidu.com/item/最小生成树/5223845][https_baike.baidu.com_item_5223845]\].书上总共给出了两种算法，一种为prim算法，一种为Kruscal算法，两种算法的时间复杂度在堆优化的情况下，各为O(elge)和O(eLgv)其中e为图的边数，v为图的顶点数。

## 2.prim算法 ##

prim算法的主要思想是，先随意选择一个点作为起始点，先对每一个点到起点的距离进行初始化，如果两点间存在边，那么距离更新为边的权值，如果不存在，那么两点间的值变为无限大。然后在每一次搜索的过程中，挑选出当前节点所连接的最短的路径，之后以这条路径中的另一个节点来更新起点到其他点的距离，prim算法中由于每次所要找的是最短路径，所以并不需要进行松弛操作，而仅仅只是更新最小值而已，同时，每一次选择路径，都会在标记数组中进行标记，所以不会出现点重复访问的问题，且可以保证最小生成树的获得。

可能听描述还是一脸懵，我们直接来看代码吧。

int graph[maxn][maxn];
    void prim(int **graph)
    {
    	int key = 1;
    	int inf = 1e9 + 7;//最大值
    	int cost[maxn] = { 0 };//辅助数组
    	int min = inf;
    	int value = 0;
    	int flag = 0;
    	int visit[maxn] = { 0 };//标记数组
    	for(int i=1;i<=n;i++)//进行初始化
    	{
    		if (graph[key][i])
    			cost[i] = graph[key][i];
    		else
    			cost[i] = inf;
    	}
    	for (int i = 1; i < n; i++)
    	{
    		min = inf;
    		for (int j = 1; j <= n; j++)
    		{
    			if (!visit[j] && min > cost[i])//寻找最短路径
    			{
    				min = cost[j];
    				flag = j;
    			}
    		}
    		value += min;
    		for (int j = 1; j <= n; j++)
    		{
    			if (cost[j] > graph[flag][j]&&graph[flag][j])//更新辅助数组
    			{
    				cost[j] = graph[flag][j];
    			}
    		}
    	}
    }

## 3 Kruscla算法 ##

Kruscla算法更prim算法有比较大的区别，Kruscal也是每一次只选择最短的边加入最小生成树，但多了一个判断两条边是否属于不同的联通分量的判断，如果不属于同一个联通分量的话，就加入生成树，如果属于同一个连通分量的话，就进行下一次的挑选。重要的是如何判断两条边是否属于不同的联通的分量。详细代码如下

#include <algorithm>
    using namespace std;
    
    typedef struct eadge 
    {
    	int from;
    	int  to;
    	int  value;
    }eadge;//边的定义
    
    bool cmp(eadge a,eadge b)
    {
    	return a.value < b.value;
    }
    
    int find_root(int x,int *find)
    {
    	if(x!=find[x])
    	{
    		find_root(find[x], find);
    	}
    	return x;
    }
    
    void Kruscal(eadge *test)
    {
    	int find[maxn];
    	int value = 0;
    	sort(test + 1, test + n + 1, cmp);
    	for (int i = 1; i <= sum_of_node; i++)
    	{
    		find[i] = i;
    	}
    	for(int i=1;i<=sum_of_eadge;i++)
    	{
    		int x = find_root(test[i].from);
    		int y = find_root(test[i].to);
    		if(x!=y)
    		{
    			find[x] = y;
    			value += test[i].value;
    		}
    	}
    }

## 4.总结 ##

以上就是关于Kruscal以及Prim算法的一些总结，我们可以发现两个算法的比较重要的一点就是要寻找到，所有边中的最短边。我们可以将有关边的信息存入到**堆**数据结构中，生成最小堆，每次只要从堆的最顶点取元素即可，关于这一点日后会慢慢补上，以前学过了堆的知识，现在又忘了，orz。

[https_baike.baidu.com_item_5223845]: https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91/5223845