Prim最小生成树算法（贪心算法）
最小生成树的性质：
一棵树
没有回路n 个顶点含有 n - 1 条边
生成树
所有顶点都在里面n - 1 条边都在图中边的权重最小
在生成树的图中任意加一条边都会形成回路
适用于稠密图
Vertex FindMinDist( MGraph Graph, int dist[] ){int MinV, V;int MinDist = INFINITY;for (V = 0; V < Graph->Nv; V++){if ( dist[V] != 0 && dist[V] < MinDist){MinDist = dist[V]; //更新最小距离 MinV = V; //更新对应顶点}}if (MinDist < INFINITY) //若找到最小distreturn MinV; else return 0; // 若这样的顶点不存在}int Prim( MGraph Graph, LGraph MST ){int dist[MaxVertexNum], TotalWeight = 0; // 初始化权重和 int parent[MaxVertexNum], V, W;int VCount = 0; //初始化收录的顶点数Edge E;for (V = 0; V < Graph->Nv; V++)// 初始化。默认初始点下标是0 {dist[V] = Graph->G[0][V];//假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY parent[V] = 0;}MST = CreateGraph(Graph->Nv);E = (Edge)malloc( sizeof(struct ENode) ); //建立空的边结点dist[0] = 0;//将初始点0收录进MSTVCount ++;parent[0] = -1; //当前树根是0while (1) {V = FindMinDist( Graph, dist );//未被收录顶点中最小的distif ( V == 0 ) // 若这样的V不存在 break;E->V1 = parent[V];// 将V及相应的边<parent[V], V>收录进MST E->V2 = V;E->Weight = dist[V];InsertEdge( MST, E );TotalWeight += dist[V];dist[V] = 0; //收录进MST VCount++;for( W = 0; W < Graph->Nv; W++ ) //对图中的每个顶点W{if ( dist[W] != 0 && Graph->G[V][W] < INFINITY ) {if ( Graph->G[V][W] < dist[W] ){dist[W] = Graph->G[V][W]; //更新dist[W]parent[W] = V;}}} }if ( VCount < Graph->Nv ) //MST中收的顶点不到|V|个TotalWeight = 0;return TotalWeight; }
Kruskal算法—将森林合并成树
(来源于中国MOOC-浙大-数据结构)
克鲁斯卡尔算法第一种方法生成最小树
typedef ElementType SetType[MaxVertexNum]; //集合元素下标从0开始void InitializeVSet( SetType S, int N ){ElementType X;for ( X=0; X<N; X++ ) S[X] = -1;}void Union( SetType S, int Root1, int Root2 )// /小集合并入大集合{if ( S[Root2] < S[Root1] ) {S[Root2] += S[Root1];S[Root1] = Root2;}else {S[Root1] += S[Root2];S[Root2] = Root1;}}int Find( SetType S, ElementType X ){if ( S[X] < 0 ) // 找到根return X;elsereturn S[X] = Find( S, S[X] ); // 路径压缩 }int CheckCycle( SetType VSet, Vertex V1, Vertex V2 )// 检查连V1和V2的边是否在生成树子构成回路 {Vertex Root1, Root2;Root1 = Find( VSet, V1 );Root2 = Find( VSet, V2 );if( Root1==Root2 ) //若V1和V2已经连通,忽略该边 return 0;else {Union( VSet, Root1, Root2 );return 1;}}void PercDown( Edge ESet, int p, int N )//调整最小堆 {int Parent, Child;struct ENode X;X = ESet[p]; // 取出根结点存放的值for( Parent = p; Parent*2 < N - 1; Parent = Child ) //N - 1条边 {Child = Parent * 2 + 1;if( (Child != N-1) && (ESet[Child].Weight > ESet[Child+1].Weight) ) // Child指向左右子结点的较小者Child++; if( X.Weight <= ESet[Child].Weight ) break;elseESet[Parent] = ESet[Child];}ESet[Parent] = X;}void InitializeESet( LGraph Graph, Edge ESet ){Vertex V;PtrToAdjVNode W;int ECount;ECount = 0;for ( V = 0; V < Graph->Nv; V++ ){for ( W = Graph->G[V].FirstEdge; W; W = W->Next ){if ( V < W->AdjV ) //避免重复录入无向图的边，只收V1<V2的边{ESet[ECount].V1 = V;ESet[ECount].V2 = W->AdjV;ESet[ECount++].Weight = W->Weight;}}} for ( ECount = Graph->Ne/2; ECount >= 0; ECount-- )//形成最小堆 PercDown( ESet, ECount, Graph->Ne );}int GetEdge( Edge ESet, int CurrentSize )//给定当前堆的大小CurrentSize，将当前最小边位置弹出并调整堆 {Swap( &ESet[0], &ESet[CurrentSize-1]); //将最小边与当前堆的最后一个位置的边交换PercDown( ESet, 0, CurrentSize-1 ); //将剩下的边继续调整成最小堆return CurrentSize-1; // 返回最小边所在位置}int Kruskal( LGraph Graph, LGraph MST ){WeightType TotalWeight;int ECount, NextEdge;SetType VSet; //顶点数组Edge ESet; //边数组InitializeVSet( VSet, Graph->Nv ); //初始化顶点并查集ESet = (Edge)malloc( sizeof(struct ENode)*Graph->Ne );InitializeESet( Graph, ESet );//初始化边的最小堆MST = CreateGraph(Graph->Nv);TotalWeight = 0;ECount = 0; NextEdge = Graph->Ne; //原始边集的规模while ( ECount < Graph->Nv-1 )// 当收集的边不足以构成树时{NextEdge = GetEdge( ESet, NextEdge ); //从边集中得到最小边的位置if (NextEdge < 0) //边集已空break;if ( CheckCycle( VSet, ESet[NextEdge].V1, ESet[NextEdge].V2 )==true )//如果该边的加入不构成回路，即两端结点不属于同一连通集{InsertEdge( MST, ESet+NextEdge );TotalWeight += ESet[NextEdge].Weight; //累计权重 ECount++; // 生成树中边数加1}}if ( ECount < Graph->Nv-1 )TotalWeight = -1; //表示生成树不存在return TotalWeight;}
克鲁斯卡尔算法另外一种方法生成最小树（来源于清华出版社-胡昭民著的《数据结构》）
思维导图
该方法和上一个最不一样的地方在于该方法判断是否形成回路时，将被纳入集合树的每个边的两端点进行计数，v[mceptr->from]++;//该点经过次数 v[mceptr->to]++;//该点经过次数，那么只要两者同时大于等于2，那么肯定是有回路形成，可以自己想象。
#include <stdio.h>#include <stdlib.h>#define VERTS 6/*图的顶点数*/struct edge /*声明边的结构*/{int from,to;int find,val;struct edge* next;};typedef struct edge node;typedef node* mst;int v[VERTS+1];mst findmincost(mst head) /*所示成本最小的边*/{int minval = 100;mst ptr,retptr;ptr = head;while(ptr != NULL){if(ptr->val < minval && ptr->find==0){/*假如ptr->val的值小于minval*/minval = ptr->val; /*就把ptr->val设为最小值*/retptr = ptr;/*并且把ptr记录下来*/}ptr=ptr->next;}retptr->find = 1; /*将retptr设为已找到的边*/return retptr;/*返回retptr*/}void mintree(mst head) /*最小成本生成树函数*/{mst ptr,mceptr;int i,result = 0;ptr = head;for(i = 0;i <= VERTS;i++)v[i] = 0;while(ptr != NULL){mceptr = findmincost(head);v[mceptr->from]++;//该点经过次数 v[mceptr->to]++;//该点经过次数 if(v[ mceptr->from ] > 1 && v[ mceptr->to ] > 1 ) //防止出现闭合的回路 {v[mceptr->from]--;v[mceptr->to]--;result = 1;//直接舍去，到该循环的最后一步ptr=ptr->next; }elseresult = 0;if(result == 0)printf("起始顶点 [%d] -> 终止顶点 [%d] -> 路径长度 [%d]\n",mceptr->from,mceptr->to,mceptr->val);ptr = ptr->next;//整个顶点数等于遍历次数，保证每个点都在里面 }}int main(){int data[10][3]={{1,2,6},{1,6,12},{1,5,10},{2,3,3}, /*成本表数组*/{2,4,5},{2,6,8 },{3,4,7},{4,6,11},{4,5,9},{5,6,16}};int i,j;mst head,ptr,newnode;head = NULL;for(i = 0;i < 10;i++)/*建立图的链表*/{for(j = 1;j <= VERTS;j++){if(data[i][0] == j){newnode = (mst)malloc(sizeof(node));newnode->from = data[i][0];newnode->to = data[i][1];newnode->val = data[i][2];newnode->find = 0;newnode->next = NULL;if(head == NULL){head = newnode;head->next = NULL;ptr = head;} else{ptr->next = newnode;ptr = ptr->next;}}}}mintree(head); /*建立最小成本生成树*/return 0;}
c++语言实现：
#include<iostream>using namespace std;#include<cstdio>#include<algorithm>const int N = 100;int nodeset[N];int n,m;struct Edge{int v;//起始点 int u;//终端点 int w;//权重 }e[N*N]; //邻接矩阵 bool comp(Edge x,Edge y){return x.w < y.w;//升序排序 } void Init(int n){for(int i = 1;i <= n;i++)nodeset[i] = i;//初始化为自身 } int Find(int n)//寻找集合点根 {if(nodeset[n] != n)nodeset[n] = Find(nodeset[n]);return nodeset[n];}int Merge(int a,int b){int p = Find(a);int q = Find(b);if(p == q)//形成必和圈 return 0;if(p > q) //小的集合号赋给大的集合号 nodeset[p] = q;elsenodeset[q] = p;return 1;} int Kruskal(int n){int ans = 0;for(int i = 0;i < m;i++){if(Merge(e[i].v,e[i].u) != 0) //未形成闭合圈 {ans += e[i].w;//权重累计和 n--;if(n == 1)//只有一个点时 return ans;}}return 0;}int main(){cout<<"输入节点数n和边数m: "<<endl;cin>>n>>m;Init(n);cout<<"输入结点数v,u和边值w: "<<endl;for(int i = 0;i < m;i++)cin>>e[i].v>>e[i].u>>e[i].w;sort(e,e+m,comp); //库函数排序 int ans = Kruskal(n);cout<<"最小的花费是： "<<ans<<endl;return 0; }
