数据结构和算法学习笔记⼋：带权连通图的最⼩⽣成树⼀.简介: 对于⼀个n个顶点的连通图,其最⼩⽣成树是指将所有顶点连接起来的权值之和的最⼩树,树中包含n个顶点和n-1条边.最⼩⽣成树常见的⽣成算法有普⾥姆算法和克鲁斯卡尔算法,它们分别基于顶点的⾓度和边的⾓度⽣成最⼩⽣成树. 声明:对于本⽂中实现图结构的各种类,详见:⼆.两种算法简介 1.普⾥姆算法:普⾥姆算法基于顶点实现,基本思路是将所有已经纳⼊到最⼩⽣成树中的顶点存储起来,然后遍历当前的最⼩⽣成树的端点,找出权值最⼩且不会闭环的边并延伸最⼩⽣成树,然后将新的顶点纳⼊到最⼩⽣成树中(和其他已经纳⼊到树中的顶点⼀起存储起来) 2.克鲁斯卡尔算法:克鲁斯卡尔算法基于边实现,⾸先将所有边按照权值由⼩到⼤排序,然后再从⼩到达依次遍历所有边,⼀⼀判断当前边加⼊最⼩⽣成树中后是否会形成环路,在不形成环路的情况下将此边加⼊最⼩⽣成树,并将顶点存储起来.顶点的存储结构类似于倒置的树,根节点在最下⽅.在最⼩⽣成树的⽣成过程中可能会同时存在多颗顶点树,但是最终所有顶点树会汇聚成⼀颗.三.代码实现(c#)/************************************* 创建⼈：movin* 创建时间：2021/7/4 19:55:02* 版权所有：个⼈***********************************/using System;using System.Collections.Generic;using System.Text;namespace GraphCore{///<summary>///最⼩⽣成树算法///</summary>public class MinimumCostSpanningTreeUtil{///<summary>///计算最⼩⽣成树-普⾥姆算法///要求参数必须是⼀个连通图,此处没有校验参数graph是否是连通图的过程,可⾃⾏添加///</summary>///<param name="graph"></param>///<param name="findAEdgeCallBack">找到⼀条边后的回调函数,参数为边的两个关联点下标和权值</param>public static void MiniSpanTree_Prim(AdjacencyMatrixGraph graph,Action<int,int,int> findAEdgeCallBack = null){//数组lowcast,数组的长度和顶点的个数⼀致,数组中每个下标的值和顶点⼀⼀对应//lowcast的作⽤有两个,以lowcast[1] = 5为例,意思是当前已经找过的顶点中到1顶点的最短路径权值为5//所以作⽤⼀是某下标对应值不为0时代表当前已经⽣成的部分最⼩⽣成树到某下标对应顶点的权值最⼩的边的权值//作⽤⼆是某下标对应值为0时代表此下标对应顶点已经在最⼩⽣成树中,不再参与继续⽣成最⼩⽣成树int[] lowcast = new int[graph.Count];//数组adjvex,这个数组作⽤是对应记录lowcast中最⼩权值边的另⼀个依附顶点下标(⼀个依附顶点下标就是lowcast下标)int[] adjvex = new int[graph.Count];lowcast[0] = 0;//从0号顶点开始⽣成最⼩⽣成树,⾸先将0号顶点对应位置置为0//adjvex[0] = 0;//这句代码加不加都ok,0号位已经加⼊最⼩⽣成树,这个值也就⽤不上了//初始化lowcast数组的其他下标值for(int i = 1;i < lowcast.Length; i++){//当前最⼩⽣成树中只有0号顶点,所以以0号顶点到i号顶点的边的权值就是当前的最⼩边权值lowcast[i] = graph.adjacencyMatrix[0, i];//这些边的另⼀个依附顶点当然是0号顶点adjvex[i] = 0;}//开始计算最⼩⽣成树,结果存储到result中int min = int.MaxValue;//⽤来存储找到的最⼩权值边的权值的临时变量int tempIndex = 0;//⽤来存储即将加⼊最⼩⽣成树的边的顶点(也就是即将加⼊最⼩⽣成树的顶点)的临时变量,另⼀个顶点存储在adjvex数组中//循环length-1次,每次将⼀个顶点和⼀条边加⼊最⼩⽣成树中for(int i = 1;i < graph.Count; i++){//循环在当前的lowcast中找到⾮0的最⼩值(到没有找过的顶点中的最⼩边)min = int.MaxValue;tempIndex = 0;for(int j = 1;j < lowcast.Length; j++){if(lowcast[j] != 0 && lowcast[j] < min){min = lowcast[j];tempIndex = j;}}//找到边后调⽤回调函数if(findAEdgeCallBack != null){findAEdgeCallBack(tempIndex, adjvex[tempIndex], lowcast[tempIndex]);}//更新lowcast数组lowcast[tempIndex] = 0;//每次延申了最⼩⽣成树后需要将lowcast中的值更新,⽅便下次继续延申最⼩⽣成树//刚才将下标为tempIndex的顶点和⼀条边加⼊了最⼩⽣成树,接下来只需要更新这个顶点相关的边即可for(int j = 1;j < lowcast.Length;j++){//判断顶点tempIndex和顶点j之间的边//j顶点不在最⼩⽣成树中且这条边的权值⽐lowcast中记录的最⼩权值要⼩时//更新到顶点j的最⼩权值边的权值,并且记录到顶点j的最⼩权值边的另⼀个顶点为tempIndexif(lowcast[j] != 0 && lowcast[j] > graph.adjacencyMatrix[tempIndex, j]){lowcast[j] = graph.adjacencyMatrix[tempIndex, j];adjvex[j] = tempIndex;}}}}///<summary>///计算最⼩⽣成树-克鲁斯卡尔算法///要求参数必须是连通图///</summary>///<param name="graph"></param>///<param name="findAEdgeCallBack">找到⼀条边后的回调函数,参数为边的两个关联点下标和权值</param>public static void MinSpanTree_Kruskal(EdgesetArrayGraph graph, Action<int, int, int> findAEdgeCallBack = null){//将边集数组排序SortEdgeNode(graph.edgeNodes);//声明⼀个数组,数组下标对应顶点下标//数组中值为-1时代表对应顶点还没有加⼊最⼩⽣成树//当某个顶点被加⼊最⼩⽣成树后,将数组中对应的下标的值修改,修改后的值指向下⼀个加⼊最⼩⽣成树的顶点下标//如vertices[5] = 7代表5号顶点和7号顶点都在最⼩⽣成树中,其中5号顶点的下⼀个顶点是7号顶点//在构建最⼩⽣成树的过程中会通过这个数组检验当前边添加进数组是否会构成环//分析后⾯的代码可以知道,最终数组中length-1个值会被修改,刚好对应添加到最⼩⽣成树中的length-1条边int[] vertices = new int[graph.edgeNodes.Length];//数组初始值都为-1for (int i = 0; i < vertices.Length; i++){vertices[i] = -1;}//下⾯构建最⼩⽣成树//循环遍历所有边,⼀⼀校验是否可以加⼊最⼩⽣成树for (int i = 0; i < graph.edgeNodes.Length; i++){EdgesetArrayEdgeNode node = graph.edgeNodes[i];int startIndex = GetNextVertex(vertices, node.headIndex);int endIndex = GetNextVertex(vertices, node.tailIndex);//检验是否成环,不成环则这条边可以加⼊最⼩⽣成树if (startIndex != endIndex){vertices[startIndex] = endIndex;if(findAEdgeCallBack != null){findAEdgeCallBack(node.headIndex, node.tailIndex, node.weight);}}}}///<summary>///在vertices中,顶点之间的先后次序最终的存储⽅式类似于⼀颗倒过来的树,根顶点在最下⽅,存储时会⼀直向下找,直到找到根顶点,存储时会将下⼀个存储到最⼩⽣成树中的顶点挂到根顶点下⽅成为新///查找时看此顶点是否有后继顶点,如果有那么继续查找后继顶点的后继顶点...以此类推,直到某个顶点对应下标值为-1,即没有后继顶点,返回这个顶点下标///如果两个顶点之间会构成环路,那么它们所在的顶点的后继中⼀定会有相同的顶点,最终查找下去得到的值为顶点相同///</summary>///<param name="vertices"></param>///<param name="index"></param>///<returns></returns>private static int GetNextVertex(int[] vertices,int index){while(vertices[index] != -1){index = vertices[index];}return index;}///<summary>///将给定边集数组按照从⼩到达排序///采⽤选择排序///</summary>///<param name="graph"></param>private static void SortEdgeNode(EdgesetArrayEdgeNode[] edgeNodes){for (int i = 0; i < edgeNodes.Length; i++){int minIndex = i;for (int j = i + 1; j < edgeNodes.Length; j++){if(edgeNodes[minIndex].weight > edgeNodes[j].weight){minIndex = j;}}if(minIndex != i){EdgesetArrayEdgeNode temp = edgeNodes[i];edgeNodes[i] = edgeNodes[minIndex];edgeNodes[minIndex] = temp;}}}}}。
