数据结构图之二（最小生成树--克鲁斯卡尔算法）

【1】克鲁斯卡尔算法

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

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

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

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

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

数据结构图之二（最小生成树--克鲁斯卡尔算法）

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

数据结构图之二（最小生成树--克鲁斯卡尔算法）

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

数据结构图之二（最小生成树--克鲁斯卡尔算法）

【2】克鲁斯卡尔算法及详解

克鲁斯卡尔算法及其详解：

数据结构图之二（最小生成树--克鲁斯卡尔算法）

鉴于此算法很简单，当 i=0, i=1, i=2时执行结果可以眼观，不再赘述。直接分析重点：

数据结构图之二（最小生成树--克鲁斯卡尔算法）

此算法的Find函数由边数e决定，时间复杂度为O(loge),而外面有一个for循环e次。

所以克鲁斯卡尔算法的时间复杂度为O(eloge)

对比两个算法：

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

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

【3】克鲁斯卡尔算法实现

实现代码如下：

  1 #include <iostream>
  2 using namespace std;
  3 
  4 #define    MAXVER  9
  5 #define MAXEDGE 15
  6 
  7 typedef struct Node
  8 {
  9     int begin;        // 起点
 10     int weight;     // 权值
 11     int end;        // 末点
 12 } edgeNode;
 13 
 14 class Graph
 15 {
 16 private:
 17     edgeNode edge[MAXEDGE];
 18 public:
 19     Graph()
 20     {
 21         for (int i = 0; i < MAXEDGE; ++i)
 22         {
 23             edge[i].begin = edge[i].weight = edge[i].end = 0;
 24         }
 25     }
 26     ~Graph()
 27     {}
 28 
 29 public:
 30     void InsertSort()
 31     {
 32        for (int i = 0; i < MAXEDGE- 1; ++i)
 33        {
 34             if (edge[i+1].weight < edge[i].weight)
 35             {
 36                  Node temp = edge[i+1];
 37                  int j = i + 1;
 38                  do
 39                  {
 40                      edge[j] = edge[j-1];
 41                      --j;
 42                  } while(j >= 0 && edge[j].weight > temp.weight);
 43                                 
 44                  edge[j+1] = temp;
 45             }
 46         }
 47     }
 48 
 49     istream & operator>>(istream &in)
 50     {
 51         int begin, value, end;
 52         cout << "请输入15条边的起点 终点 权值：" << endl;
 53         for (int i = 0; i < MAXEDGE; ++i)
 54         {
 55             in >> begin >> end >> value;
 56             edge[i].begin = begin;
 57             edge[i].weight = value;
 58             edge[i].end = end;
 59         }
 60         return in;
 61     }
 62     ostream & operator<<(ostream &out)
 63     {
 64         // 插入排序
 65         InsertSort();
 66         out << "输出排序边权值后信息:" << endl;
 67         for (int i = 0; i < MAXEDGE; ++i)
 68         {
 69             out << "edge[" << i << "] " << edge[i].begin << "  " << edge[i].weight << " " << edge[i].end << endl;
 70         }
 71         return out;
 72     }
 73     // 克鲁斯卡尔算法
 74     void MiniSpanTree_Kruskal()
 75     {
 76         int i = 0, n = 0, m = 0;
 77         int parent[MAXVER];
 78         for ( ; i < MAXVER; ++i)
 79             parent[i] = 0;
 80         for (i = 0; i < MAXEDGE; ++i)
 81         {
 82             n = Find(parent, edge[i].begin);
 83             m = Find(parent, edge[i].end);
 84             if (n != m)
 85             {
 86                 parent[n] = m;
 87                 cout << " " << edge[i].begin << " " << edge[i].end << " " << edge[i].weight << endl;
 88             }
 89         }
 90     }
 91 
 92     int Find(int *parent, int f)
 93     {
 94         while (parent[f] > 0)
 95             f = parent[f];
 96         return f;
 97     }
 98 };
 99 
100 istream & operator>>(istream &in, Graph &g)
101 {
102     g >> in;
103     return in;
104 }
105 
106 ostream & operator<<(ostream &out, Graph &g)
107 {
108     g << out;
109     return out;
110 }
111 
112 void main()
113 {
114     Graph myg;
115     cin >> myg;
116     cout << myg;
117     myg.MiniSpanTree_Kruskal();
118 }
119  // 备注：
120  // 最小生成树克鲁斯卡尔算法实现
121  // 整理于2013-12-04
122  // 测试需要输入：
123  /*
124  起始   终点   权值
125  0 1 10
126  0 5 11
127  1 2 18
128  1 8 12
129  1 6 16
130  2 8 8
131  2 3 22
132  3 8 21
133  3 6 24
134  3 7 16
135  3 4 20
136  4 7 7
137  4 5 26
138  5 6 17
139  6 7 19
140   */

View Code

数据结构图之二（最小生成树--克鲁斯卡尔算法）

相关推荐