本篇文章分享最小生成树，对你有帮助的话记得收藏一下，看极客资料网收获更多编程知识

用最小的代价将连通图中所有节点连接起来

生成树

生成树是一个连通图的最小连通子图，包含图中所有n个顶点，但只包含n-1条边

• 一个连通图可以有多个生成树
• 生成树节点个数为图中节点个数n，边数为n-1
• 生成树中不存在环（树中不存在环），生成树中添加一条边会形成环
• 对于包含n个顶点的完全无向图，最多包含$n^{n-2}$个生成树
• 有向图和无向非连通图不存在生成树

最小生成树

生成树的所有边的权值和最小

Kruskal算法

将森林合并成树，关心边

• 从邻接矩阵中初始化边集数组
• 在边集中找一条权值最小的边，可以直接排序，也可以用最小堆
• 判断这条边的两个顶点是否属于同一棵树（并查集）
  • 若不属于同一棵树，收纳这条边（相当于合并两颗树），再将这条边从边集中删除（若是排好序的就不用）
  • 若属于同一棵树，这条边会导致树中存在环，所以要彻底无视这条边，即把这条边从边集中排除（若是排好序的就直接跳过）
• 进入下一次循环找权值最小的边，直到访问过所有边，退出循环
• 返回权值和

typedef struct edge{    //边结构
	int v1,v2;    //两个顶点
	int weight;
}Edge;

Edge edges[MaxNum];    //图的边集
Edge result[MaxNum];    //最小生成树（结果）的边集

int minTree[MaxNum];    //最小生成树，父亲表示法

//初始化边集数组
void initEdgeSet(const MGraph* graph,Edge edges[]){
	int k=0;
	for(int i=0;i<graph->vertexNum;i++){
		for(int j=0;j<i;j++){
			if(graph->edges[i][j]!=0&&graph->edges[i][j]!=INFI){
				edge[k].v1=i;
				edge[k].v2=j;
				edge[k].weight=graph->edges[i][j];
				k++;
			}
		}
	}
}

//初始化树
void initTree(MGraph* graph,int minTree[]){
	for(int i=0;i<graph->edgeNum;i++){
		minTree[i]=-1;
	}
}

int kruskal(MGraph* graph,Edge edges[],int minTree[],Edge result[]){
	//排序边集数组
	sort(edges,edges+graph->edgeNum,[](Edge e1,Edge e2){return e1.weight<e2.weight;});
	int sum=0;    //权值和
	int root1,root2;
	int k=0;
	for(int i=0;i<graph->edgeNum;i++){
		//查根
		root1=findRoot(minTree,edges[i].v1);
		root2=findRoot(minTree,edges[i].v2);
		if(root1!=root2){
			minTree[root1]=root2;   //合并树
			sum+=edges[i].weight;
			result[k].v1=edges[i].v1;
			result[k].v2=edges[i].v2;
			result[k].weight=edges[i].weight;
			k++;
		}
	}
	return sum;
}

路径压缩的并查集的查找事件复杂度为O(1)，维护最小堆的时间复杂度为O($logE$)，遍历所有边的时间复杂度为O($E$)，总的时间复杂度为O($ElogE$)，E为边数

Prim算法

一棵树的扩增，关心点

Kruskal算法和Prim算法得到的最小生成树可能不一样，但边的权值和一样

Kruskal算法是收录边，而Prim算法是收录顶点，需要维护一个distance数组，表示所有顶点距离目前的树的最小距离，初始全部为INFI，相当于从树上只能看到和树挨着的节点，其他节点都看不到
每次迭代：

• 选择未收录的顶点中距离树最小的一个顶点收录（局部最优值），收录之后距离变为0（因为这个节点已经在树中）
• 收录之后可能会影响这个顶点的所有邻接点到树的最小距离，需要更新所有邻接点到树的最小距离为对应边权值，还需要更新这个节点的父节点为刚收录的节点

由于每次都是从未收录的顶点中选择一个收录，所以不需要考虑环，能判断是否是连通图

typedef struct Edge{    //边结构
	int v1,v2;    //两个顶点
	int weight;
}

Edge result[MaxNum];    //最小生成树（结果）的边集

int minTree[MaxNum];    //最小生成树，父亲表示法

int distance[MaxNum];    //每个顶点离树的最小距离

int Prim(const MGraph* graph,int start,Edge result[],int minTree[],int distance[]){    //start就是最小生成树的根节点
	int sum=0;    //权值和
	//收录第一个顶点start
	//distance[start]=0;
	for(int i=0;i<graph->vertexNum;i++){
		distance[i]=graph->edges[start][i];
		if(distance[i]!=INFI&&distance[i]!=0)minTree[i]=start;
		else minTree[i]=-1;
	}
	//minTree[start]=-1;
	//收录剩下的节点
	for(int i=0;i<graph->vertexNum-1;i++){
		//找最小值
		int min=INFI;   //离树的距离的最小值
		int m;    //最小值对应的节点
		for(int j=0;j<graph->vertexNum;j++){
			if(distance[j]!=0&&distance[j]<min){
				min=distance[j];
				m=j;
			}
		}
		if(min==INFI){
			return -1;    //图不连通
		}
		//收录m节点
		distance[m]=0;
		sum+=min;
		result[i]={minTree[m],m,min};
		//更新m的未收录的邻接点
		for(int j=0;j<graph->veretxNum;j++){
			if(graph->edges[m][j]<distance[j]){
				distance[j]=graph->edges[m][j];
				minTree[j]=m;
			}
		}
	}
	return sum;
}

时间复杂度O($V^{2}$)，堆优化后是O($VlogV$)

文章来源:https://www.cnblogs.com/mofei1214/p/19852791
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！