数据结构中图结构的最小生成树克鲁斯卡尔算法详解
我一直想把克鲁斯卡尔算法实现,但是由于马上就要考试了,而且自己由于天气寒冷等各种原因没能如愿。不过在昨天一天的努力中,我终于完成了克鲁斯卡尔算法的实现。算法是c++的,图的数据结构是以邻接矩阵为基础,并且使用了模板,所以可以对任何类型的顶点进行最小生成树的生成。
更新于12月19日:由于自己发现了一些错误和解释不清的现象,所以将一张图片和少数文字进行了更正。
克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边,如果满足条件就将其构造,最后生成一个最小生成树。它首先是一系列的顶点集合,并没有边,然后我们从邻接矩阵中寻找最小的边,看看它是否和现有的边连接成一个环,如果连接成环,则舍弃,另外取其它的边。如果不连接成环,则接受这个边,并把其纳入集合中。以此类推。我们知道,一课有n个顶点的树(无论是树还是二叉树),它必定有n-1个边。我们只需要对上述操作循环至少n-1次(因为可能选出的边会构成环,不是我们需要的边)。
下面就是我寻找最小边的c++代码:
- min = INFINITY;
- for ( i = 0; i < vexnum; i++ )
- {
- for ( j = i; j < vexnum; j++ )
- {
- if ( arcs[i][j].adj != INFINITY && min > arcs[i][j].adj )
- {
- if ( arcs[i][j].adj >= vexSet.lowcost && !vexSet.IsAlreadyIn( i, j ) )
- {
- min = arcs[i][j].adj;
- track_i = i;
- track_j = j;
- }
- }
- }
- }
首先让min为最大(INFINITY),然后让其与邻接矩阵的一个个元素进行比较,我在遍历邻接矩阵的时候使用的是上三角(◥)法,因为无向网的邻接矩阵是对称矩阵。当然我们必须记录满足调件的顶点的下标,所以track_i、track_j就变得必要了。又因为我们要满足每次选取的最小权值的边呈递增数列,所以arcs[i][j].adj > vexSet.lowcost(其中vexSet.lowcost为上次保存的最小边)就变得必要了。同时我们还要注意一点,如果一个图有多条边的权值相同(如右图),那么我们必须在这里添加上=号,变成arcs[i][j].adj >= vexSet.lowcost。并且要从顶点集合(VertexSet,稍后会提到)中的顶点位置中查找是否已经存在。这里我使用了IsAlreadyIn()函数来实现它。
然后我们必须要判断我们新加入的边是否和原有边构成环。由于边在邻接矩阵的表现形式是两个顶点的集合。所以这时我们的顶点下标track_i、track_j就派上用场了,它们被保存到vexPos中。这里我写了一个函数(IsCycle()),用来判断是否构成环。
试着考虑下列数列:
1 2 1 3 2 4 3 4
①②③④⑤⑥⑦⑧
其中3 4是我将要加上的边。他们构成的关系图如下所示:(图)
显然加上了3 4的话,就会构成环了。怎样用c++来判断是否构成环呢?我们可以这么考虑:
令x=3,也就是⑦号位的3,然后从①号位开始遍历这个数组,如果找到了3,则记下这个3的位置。这里是④号位。然后如果是偶数号位,那么我们找到它相邻的奇数位,如果是奇数号位,那么我们要找它相邻的偶数号位。这里我们找到③号位1。然后我们再以1为关键字,找到另外一个1。这里找到了①号位。我们再找它的相邻位即②号位2。这时又以2为关键字,遍历数组。此时我们需注意,从左遍历起的时候可能会找到原来的2。这时我们要尽量避免找到它。这里使用一个if语句进行判断即可实现。下面就是我这个函数的代码:
- /*--------------------------------------------------------------------------*/
- // 判断顶点集合是否构成回路的函数,若构成回路,则返回真
- template <typename CustomType>
- bool JMatrixGraph<CustomType>::IsCycle( VertexSet<CustomType> objSet )
- {
- if ( objSet.vexCount == 0 ) return false;// 如果顶点集合为空,则不构成回路
- int s = objSet.vexCount;
- CustomType x = objSet.vertices[s];// 一个迭代变量,初始化为以objSet.vexCount为下标的顶点元素
- int i = s;// s为原有的变量的下标,在i递增的时候,如果目标变量在原有变量之前,则跳过该下标
- while ( 1 )// 一直循环下去,不过一定会有出口
- {
- if ( i == 0 ) i = 1;
- else i = 0;
- for ( ; objSet.vertices[i] != x; )// 让i递增,直到匹配时为止
- {
- if ( i > objSet.vexCount + 1 ) return false;// 如果超过了存储的最大值,那么没找到,一定不构成环
- if ( i + 1 == s ) i += 2;// 跳过原有变量的位置
- else i++;
- }
- if ( x == objSet.vertices[objSet.vexCount+1] ) return true;// 如果一系列循环后与v匹配,则一定构成环
- if ( i % 2 != 0 ) i -= 1;// 如果数字的位置是偶数,那么定位到于此配对的奇数下标
- else i += 1;// 如果数字的位置是奇数,那么定位到于此配对的偶数下标
- x = objSet.vertices[i];// 让x的值为配对的值
- s = i;// 保存原有变量的下标
- }
- }
- /*--------------------------------------------------------------------------*/
下面就是我为最小生成树(克鲁斯卡尔算法)这个功能写的代码:
- /*--------------------------------------------------------------------------*/
- // 判断顶点集合是否构成回路的函数,若构成回路,则返回真
- template <typename CustomType>
- bool JMatrixGraph<CustomType>::IsCycle( VertexSet<CustomType> objSet )
- {
- if ( objSet.vexCount == 0 ) return false;// 如果顶点集合为空,则不构成回路
- int s = objSet.vexCount;
- CustomType x = objSet.vertices[s];// 一个迭代变量,初始化为以objSet.vexCount为下标的顶点元素
- int i = s;// s为原有的变量的下标,在i递增的时候,如果目标变量在原有变量之前,则跳过该下标
- while ( 1 )// 一直循环下去,不过一定会有出口
- {
- if ( i == 0 ) i = 1;
- else i = 0;
- for ( ; objSet.vertices[i] != x; )// 让i递增,直到匹配时为止
- {
- if ( i > objSet.vexCount + 1 ) return false;// 如果超过了存储的最大值,那么没找到,一定不构成环
- if ( i + 1 == s ) i += 2;// 跳过原有变量的位置
- else i++;
- }
- if ( x == objSet.vertices[objSet.vexCount+1] ) return true;// 如果一系列循环后与v匹配,则一定构成环
- if ( i % 2 != 0 ) i -= 1;// 如果数字的位置是偶数,那么定位到于此配对的奇数下标
- else i += 1;// 如果数字的位置是奇数,那么定位到于此配对的偶数下标
- x = objSet.vertices[i];// 让x的值为配对的值
- s = i;// 保存原有变量的下标
- }
- }
- /*--------------------------------------------------------------------------*/
- // 克鲁斯卡尔算法求最小生成树
- template <typename CustomType>
- void JMatrixGraph<CustomType>::MiniSpanTree_KRUSKAL( void )
- {
- VertexSet<CustomType> vexSet;
- int i, j, k, track_i = 0, track_j = 0;
- unsigned int min;
- while ( vexSet.vexCount != ( vexnum - 1 ) * 2 )// 最小生成树的边为(顶点-1)×2
- {
- min = INFINITY;
- for ( i = 0; i < vexnum; i++ )
- {
- for ( j = i; j < vexnum; j++ )
- {
- if ( arcs[i][j].adj != INFINITY && min > arcs[i][j].adj )
- {
- if ( arcs[i][j].adj >= vexSet.lowcost && !vexSet.IsAlreadyIn( i, j ) )
- {
- min = arcs[i][j].adj;
- track_i = i;
- track_j = j;
- }
- }
- }
- }
- vexSet.vertices[vexSet.vexCount] = vexs[track_i];// 添加各个顶点
- vexSet.vertices[vexSet.vexCount+1] = vexs[track_j];
- vexSet.vexPos[vexSet.vexCount] = track_i, vexSet.vexPos[vexSet.vexCount+1] = track_j;// 保存上条边所邻接的两个顶点位置
- vexSet.lowcost = min;// 存放最小边
- if ( !IsCycle( vexSet ) ) vexSet.vexCount += 2;// 计数器加二
- }
- /*-------------------------------------*/
- #ifdef _JDEBUG_// 调试版本的
- cout<<"邻接矩阵为:/n";
- for ( i = 0; i < vexnum; i++ )
- {
- for ( j = 0; j < vexnum; j++ )
- {
- if ( arcs[i][j].adj == INFINITY )
- cout<<"∞ ";
- else cout<<arcs[i][j].adj<<" ";
- }
- cout<<'/n';
- }
- #endif
- /*-------------------------------------*/
- for ( i = 0; i < vexSet.vexCount; i += 2 )// 遍历顶点集合,显示构造过程
- {
- cout<<vexSet.vertices[i]<<"→"<<vexSet.vertices[i+1]<<'/n';
- }
- }
- /*--------------------------------------------------------------------------*/
为了适应这个算法,必须添加一个新的数据结构。由于这个结构的成员主要以顶点为主,所以命名为VertexSet。下面就是这个数据结构体的定义:
- // 顶点的集合,用于克鲁斯卡尔算法
- template <typename CustomType>
- struct VertexSet
- {
- VertexSet(): lowcost(0), vexCount(0){}// 默认构造函数
- bool IsAlreadyIn( int i_in, int j_in )// 判断顶点是否已经在顶点集合内
- {
- int k;
- for ( k = 0; k < vexCount + 2; k += 2 )
- if ( vexPos[k] == i_in && vexPos[k+1] == j_in ) return true;
- return false;
- }
- CustomType vertices[MAX_VERTEX_NUM];// 顶点
- int vexPos[MAX_VERTEX_NUM*(MAX_VERTEX_NUM)/2];// 所保存边所连接的两个顶点的位置
- VRType lowcost;// 最短边权值
- int vexCount;// 顶点的计数
- };
我使用这样的主函数进行调用:
- #define _JDEBUG_// 调试的开关(可注释)
- #include "JGraph.h"
- int main( int argc, char** argv )
- {
- JMatrixGraph<char> jmg;
- char temp;
- jmg.CreateGraph( UDN );
- /*--------普里姆算法---------
- cout<<"请输入起始的顶点值。/n";
- cin>>temp;
- cout<<"普里姆算法遍历的结果是:/n";
- jmg.MiniSpanTree_PRIM( temp );
- /*-------------------------*/
- /*--------克鲁斯卡尔算法---------*/
- cout<<"克鲁斯卡尔算法遍历的结果是:/n";
- jmg.MiniSpanTree_KRUSKAL();
- return 0;
- }
- /*----------------------------------------------------------------------------
- 这里有些例子,可以复制粘贴
- 6 10 0 A B C D E F
- 1 2 6
- 1 3 1
- 1 4 5
- 2 3 5
- 3 4 5
- 2 5 3
- 3 5 6
- 3 6 4
- 4 6 2
- 5 6 6
- 6 8 0 A B C D E F
- 1 2 3
- 1 3 2
- 2 4 2
- 3 4 4
- 2 5 3
- 3 6 3
- 4 6 2
- 5 6 1
- 7 8 0 A B C D E F G
- 1 2 5
- 1 3 1
- 1 7 3
- 2 4 4
- 2 6 6
- 3 5 4
- 3 6 3
- 4 5 2
- /*--------------------------------------------------------------------------*/
对照数据结构书上的176页图,我们可以看到克鲁斯卡尔算法中构造最小生成树的过程。
对照数据结构书上的186页图,并改为无向图,我们可以看到克鲁斯卡尔算法中构造最小生成树的过程。
我自己画了一个图,并且在计算机中完美地显示出来了。
克鲁斯卡尔算法是我从昨天就开始着手的工程,直到现在才完工。从这个算法中我得知设计一个算法的重要性。另外,我的算法可能很不高效,远没有书上所讲的效率高(看我那么多for循环就知道了)。但是由于书上和网上没有很多实例,所以我就觉得自己还是要设计一个算法,以后同学们遇到困难的话,这样就不至于迷茫了。希望同学们能够自己开动脑筋,作出比我的算法更加优秀的克鲁斯卡尔算法,我到时候就会看看大家的算法,大家一同努力!