数据结构之最小生成树(克鲁斯卡尔算法)

时间:2022-05-13 11:40:02

1)克鲁斯卡尔算法

普里姆算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树。

克鲁斯卡尔算法是直接以边为目标去构建。

因为权值是在边上,直接去找最小权值的边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路而已。

此时我们用到了图的存储结构中的边集数组结构。

以下是边集数组结构的定义代码:

1 typedef struct
2 {
3     int begin;                         //边的起点的下标
4     int end;                           //边的终点的下标
5     int weight;                        //边的权值
6 }Edge;

本算法所用同普里姆算法的实例,我们直接创建图的边集数组。

数据结构之最小生成树(克鲁斯卡尔算法)

并对边的权值从小到大排序后如下图:

数据结构之最小生成树(克鲁斯卡尔算法)

重点分析:

数据结构之最小生成树(克鲁斯卡尔算法)

克鲁斯卡尔算法主要针对边展开,边数少时效率会很高,所以对于稀疏图有优势

而普利姆算法对于稠密图,即边数非常多的情况会好些。

代码实现如下:

  1 #include "stdafx.h"
  2 #include<iostream>
  3 #include<string>
  4 using namespace std;
  5 typedef struct MGraph
  6 {
  7     string vexs[60];                   //存放顶点
  8     int arcs[100][100];                //存放邻接矩阵矩阵
  9     int vexnum, arcum;                 //总顶点数以及总边数
 10 }MGraph;
 11 typedef struct
 12 {
 13     int begin;                         //边的起点的下标
 14     int end;                           //边的终点的下标
 15     int weight;                        //边的权值
 16 }Edge;
 17 
 18 int locateVex(MGraph G, string u)      //找到则返回i,否则返回-1
 19 {
 20     for (int i = 0; i < G.vexnum; i++)
 21         if (G.vexs[i] == u)
 22             return i;
 23     return -1;
 24 }
 25 
 26 void CreateGraphUDG(MGraph &G)         //构造无向图
 27 {
 28     string v1, v2;                     //两个顶点信息
 29     int w;                             //两顶点间边的权值
 30     int i, j, k;
 31     cout << "请输入顶点数和边数:";
 32     cin >> G.vexnum >> G.arcum;
 33 
 34     cout << "请输入顶点:";
 35     for (i = 0; i < G.vexnum; i++)
 36         cin >> G.vexs[i];
 37 
 38     for (i = 0; i < G.vexnum; i++)     //先将邻接矩阵中所有元素都设为无穷大,这里默认10000为无穷大
 39         for (j = 0; j < G.vexnum; j++)
 40             G.arcs[i][j] = 10000;
 41 
 42     cout << "请输入边和权值:" << endl;
 43     for (k = 0; k < G.arcum; k++)
 44     {
 45         cin >> v1 >> v2 >> w;
 46         i = locateVex(G, v1);
 47         j = locateVex(G, v2);
 48         G.arcs[i][j] = G.arcs[j][i] = w;//关于主对角线对称的元素是相等的
 49     }
 50 
 51 }
 52 
 53 int cmp(const void* a, const void* b) 
 54 {
 55     return (*(Edge*)a).weight - (*(Edge*)b).weight;
 56 }
 57 
 58 int Find(int *parent, int f)           //查找连接顶点的尾部下标  
 59 {
 60     while (parent[f] > 0) 
 61         f = parent[f];
 62     return f;
 63 }
 64 
 65 void MiniSpanTree_Kruskal(MGraph G) 
 66 {
 67     int i, j, n, m;
 68     int k = 0;
 69     int parent[100];                   //用于寻找根节点的数组   
 70     Edge edges[100];                   //定义边集数组,edge的结构为begin,end,weight,均为整型  
 71     for (i = 0; i < G.vexnum - 1; i++) // 用来构建边集数组并排序(将邻接矩阵的对角线右边的部分存入边集数组中)  
 72     {
 73         for (j = i + 1; j < G.vexnum; j++) 
 74         {
 75             if (G.arcs[i][j] < 10000) 
 76             {
 77                 edges[k].begin = i;    //编号较小的结点为首 
 78                 edges[k].end = j;      //编号较大的结点为尾  
 79                 edges[k].weight = G.arcs[i][j];
 80                 k++;
 81             }
 82         }
 83     }
 84     qsort(edges, G.arcum, sizeof(Edge), cmp);//为边集数组Edge排序  
 85 
 86     for (i = 0; i < G.vexnum; i++)
 87         parent[i] = 0;
 88 
 89     cout << "打印最小生成树:" << endl;
 90     for (i = 0; i < G.arcum; i++) 
 91     {
 92         n = Find(parent, edges[i].begin); //寻找边edge[i]的“首节点”所在树的树根  
 93         m = Find(parent, edges[i].end);   //寻找边edge[i]的“尾节点”所在树的树根
 94         if (n != m)                       //假如n与m不等,说明两个顶点不在一棵树内,因此这条边的加入不会使已经选择的边集产生回路
 95         {
 96             parent[n] = m;                //将此边的结尾顶点放入下标为起点的parent中,表示此顶点已经在生成树集合中
 97             cout << G.vexs[edges[i].begin] << "-" <<G.vexs[ edges[i].end] << " " << edges[i].weight << endl;
 98         }
 99     }
100 }
101 
102 int main()
103 {
104     MGraph G;
105     CreateGraphUDG(G);
106     MiniSpanTree_Kruskal(G);
107     cout << endl;
108     return 0;
109 }

输出结果:

 

数据结构之最小生成树(克鲁斯卡尔算法)