devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++数据结构之图的连通性——最小生成树（Kruskal & Prim算法实现 带有图示与gif演示)_克鲁斯卡尔算法实现最小生成树功能结构图

作者：菜鸟追梦旅行 | 2024-03-15 18:01:27

赞

踩

克鲁斯卡尔算法实现最小生成树功能结构图

一、介绍

1）连通图与非连通图

连通图的定义：

        在图G = {V, {E} } （V为顶点集合，{E}为由顶点之间的连接关系构成的集合）中，若对于任何两个顶点V1, V2 都存在从V1到V2的路径，则称G是连通图

 如图所示，不管选择哪两个顶点，我们都能找到一条路径使得从一个顶点到达另外一个顶点，因此该图就是一个连通图。

非连通图的定义：：

        在图G = {V, {E} } 中，若存在两个顶点V1, V2 ，而无法找到任何一条路径可以从V1到达V2，则称G是非连通图

 如图所示，若选定顶点3和顶点1，会发现无法找到一条从顶点3到顶点1的路径，因此这个图就是非连通图。

2）无向图的连通分量

非连通图的极大连通子图叫做连通分量，连通图的连通分量只有一个也就是其本身，如下图所示：该非连通图存在三个连通分量分别是g1、g2、g3

 3)生成树和生成森林

如果从无向图的每一个分量中选择一个顶点作为起点，对其进行DFS或者BFS遍历，就可以求得的无向图的所有连通分量的生成树。

 如该非连通图，存在两个连通分量分别为g1和g2,分别选择一个顶点，左图选择顶点0,右图选择顶点8,进行DFS或者BFS遍历从而得到生成树

BFS：

DFS:

4)最小生成树

无向网的定义：

如果一个无向图的边上有权值，就称这个无向图为无向网，如下图所示。

连通网的定义：

如果无向网中的每个顶点都相通，就称其为连通网，同样的，如果一个无向图的边上有权值，但是这个无向图不是连通图，那么就称其为非连通网，如下面两图所示。

连通网
非连通网

最小生成树的定义：

最小生成树就是路径代价最小的连通网的生成树，也就是构成生成树的边的权值总和最小。

生成一颗最小生成树的准则：

1.必须使用且仅使用连通网中的n-1条边来连接连通网中的n个顶点。

2.不能使用产生回路的边。

3.各个边上的权值的总和达到最小。

以上图的连通网图为例，我们找到其的一颗最小生成树步骤如下所示：

1.观察连通网，我们可以发现一共有9个顶点，也就是说最小生成树是由8条边构成的

2.观察连通网我们可以发现这个连通网存在回路，即由顶点1、8、3构成的边，因此我们在寻找最小生成树的时候就要避免选择产生回路的边。

3.通过以上两个步骤我们可以得到下面两颗生成树

                   

 4.计算权值和

生成树1的权值和 = 1+3-1+1+2-1+3+2=10

生成树2的权值和 = 1+3-1+1+2+1+3+2=12

于是我们可以知道生成树1的权值和最小，因此生成树1就是我们所要寻找的最小生成树。

二、Kruskal(克鲁斯卡尔)算法

1)算法介绍

设N = {V, {E} } 为一个连通网（V为顶点集合，{E}为由顶点之间的连接关系构成的集合）

i.设N0={V, {E0} } 为一个非连通网（顶点集合与N相同，但是边关系E0集合为空），得到一个图中每个顶点自成一个连通分量的非连通图，也就是说有n个顶点，就有n个连通分量。

ii.在连通网N的边关系集合E中寻找一条  权值(代价)最小，且其上两个顶点分别存在于两个不同的连通分量  的边，并将其加入到T的边关系集合E0中。

iii.重复ii的操作，直到G中的所有顶点都在一个连通分量上，也就是说此时N0已经变成一个连通网了。

2)算法举例

i.如下图是一个连通网N，对其进行Kruskal算法得到最小生成树

 ii.通过原图可以得到一个非连通图N0，其中所有顶点自成一个连通分量

 iii.在E中找一条代价最小，且其两个顶点分别依附不同的连通分量的边，将其加入T中

 3)时间复杂度分析

        我们主要分析的Kruskal算法的时间复杂度，因此省略了求最小生成树之前的准备工作所需要的时间（也就是创建非连通图的操作），我们可以知道，该算法的核心就是每次从原图的边关系集合中找到权值最小的边并且加入到非连通图的边关系集合中，时间复杂度最高的一种情况就是每次都对原图的边集合进行遍历，找出权值最小的边并将其加入到非连通图中，这种情况的时间复杂度就是O（n^2),又因为Kruskal算法的核心就是对边进行排序，因此我们只需要引入一个辅助数组用来储存边，并且对其进行排序，然后按权值从小到大加入到非连通图中即可，对数组元素调用排序算法有十分多的选择，包括冒泡排序、快速排序、插入排序等等，不同的排序算法时间复杂度也不通。

4）算法实现

tips：本人为了贪图便利，且以为用邻接矩阵来实现会比较简单，就直接调用了之前的代码，导致有很多地方的代码比较晦涩难懂，敬请谅解。

1.我们需要先创建一个连通网用来储存原图和一个非连通网用来储存最小生成树

2.创建一个边类用来储存该边的权值，两个顶点以及用于标记访问的flag

网的组成：（网由无向图和带有权值的边组成）

边类：

  1. class line
  2. {
  3.     public:
  4.     int u,v;
  5.     int weight;
  6.     int flag;
  7. };

无向图类：

  1. class undigraph
  2. {
  3.     public:
  4.     line* linearray;
  5.     line* min;
  6.     int vertexnum=0;
  7.     int linenum=0;
  8.     int maxvertex=0;
  9.     int adjmatrix[maxsize][maxsize];//用来储存原图
  10.     int minimumtree[maxsize][maxsize];//用来储存最小生成树
  11.     void createundigraph();//创建原图
  12.     void printadjmatrix();//打印原图邻接矩阵
  13.     void printminimumtreematrix();//打印最小生成树的邻接矩阵
  14.     void printminimumtree();//打印最小生成树的各个树边
  15.     void kruskal();//克鲁斯卡尔算法
  16.     bool getfather(int u,int v,int prev);//检测是否构成回路
  17. };

3.创建原图

tips：由于是为了方便用户输入不同的图，因此代码中有较多的输入输出流和提示以及一系列的if语句用作判断用户输入，因此会显得比较冗长，如果觉得读不懂建议可以全篇代码运行一次就可以看懂了，全部代码在该小节的最后。

  1. void undigraph::createundigraph()
  2. { 
  3.     linearray=new line[(maxsize*(maxsize-1))/2];  //一个有着n个顶点的无向连通图最多有n(n-1)/2条边
  4.     int tempdata;
  5.     int adjvertex;
  6.     int i=0;
  7.     int j=0;
  8.     int symbol=0;
  9.     for(;;i++)
  10.     {
  11.         if (symbol==0)
  12.         {
  13.             while(true)
  14.             {
  15.             cout<<"请输入顶点"<<i<<"的相邻顶点:"<<endl;
  16.             cin>>adjvertex;
  17.             if (adjvertex==-1)//如果输入的相邻顶点为-1,表示相邻的顶点已经输入完毕
  18.             { 
  19.                 break;
  20.             }
  21.             else if (adjvertex==-2)//如果输入为-2表示无向图已经输入完毕
  22.             {
  23.                 symbol=1;
  24.                 break;
  25.             }
  26.             if (adjvertex>=maxvertex)
  27.             {
  28.                 maxvertex=adjvertex+1;//maxvertex用来记录最大顶点序号用于打印邻接矩阵
  29.             }
  30.             cout<<"请输入边("<<i<<","<<adjvertex<<")的权值:"<<endl;
  31.             int tempweight;
  32.             cin>>tempweight;
  33.             linenum+=1;
  34.             cout<<"linenum:"<<linenum<<endl;
  35.             linearray[j].u=i;//对边的实例进行赋值
  36.             linearray[j].v=adjvertex;
  37.             linearray[j].weight=tempweight; 
  38.             linearray[j].flag=0;        
  39.             cout<<"linearray["<<j<<"]:"<<"u="<<linearray[j].u<<"   v="<<linearray->v<<"   weight="<<linearray->weight<<endl;
  40.             j++;
  41.             adjmatrix[i][adjvertex]=tempweight;//对邻接矩阵进行赋值
  42.             adjmatrix[adjvertex][i]=tempweight;
  43.             }
  44.         }
  45.         else
  46.         {
  47.             break;
  48.         }
  49.         
  50.     }
  51.     cout<<"邻接矩阵构建完毕"<<endl;
  52.     cout<<"共有"<<linenum<<"条边"<<endl;
  53. }

4.克鲁斯卡尔算法

  1. void undigraph::kruskal()
  2. {
  3.     line min=linearray[0];//初始化最小权值边为第一条边
  4.     int minindex=0;//初始化最小权值边的下标序号
  5.     for (int j = 0; j < maxvertex+1; j++)//循环签到得到所有边中权值最小的边
  6.     {
  7.         for (int i = 0; i <linenum; i++)
  8.         {   
  9.             if (linearray[i].weight<min.weight&&linearray[i].flag==0)
  10.             {
  11.                 minindex=i;
  12.                 min=linearray[i];
  13.             }            
  14.         }
  15.         if (getfather(min.u,min.v,-1))//检测是否构成回路
  16.         {
  17.             cout<<"("<<min.u<<")"<<"-----"<<min.weight<<"-----"<<"("<<min.v<<")构成回路！"<<endl;
  18.         }
  19.         else//未构成回路就将这个边加入到最小生成树中
  20.         {
  21.         minimumtree[min.u][min.v]=min.weight;
  22.         minimumtree[min.v][min.u]=min.weight;
  23.         }
  24.         linearray[minindex].flag=1;//并将这条边进行标记，下次循环遍历最小边就不会将其算入其中
  25.         while (linearray[minindex].flag==1)//将当前最小边设置为下一个未被访问的边
  26.         {
  27.             minindex+=1;
  28.             if (minindex==linenum)
  29.             {
  30.                 minindex=0;
  31.             }
  32.         } 
  33.         min=linearray[minindex]; 
  34.     }
  35. }

5.回路检测算法

  1. bool undigraph::getfather(int u,int v,int prev)//检测当前边是否能够插入最小生成树的参数有三个
  2. {                                              //u和v为边的两个顶点，prev为顶点v前一个访问过的顶点
  3.     int i=0;
  4.     for (; i < maxvertex; i++)
  5.     {    
  6.         if (minimumtree[v][i]>0&&i!=prev)//若检测到最小生成
  7.         {
  8.             cout<<"minimumtree[v][i]:"<<minimumtree[v][i]<<endl;
  9.             prev=v;
  10.             if (u==i)
  11.             {
  12.                 return true; //如果能够找到另外一条路径到达顶点u说明加入边(u,v)会导致构成回路
  13.             }
  14.             else
  15.             {
  16.             return(getfather(u,i,prev));//递归查找是否能够从另外一条路径到达顶点u
  17.             }
  18.         }
  19.     }
  20.         return false; //如果无法找到一条路径到达顶点u说明加入 边(u,v)不会导致构成回路     
  21. }

5）代码执行结果

将下图导入到该算法中可以得出以下结果：

期望结果

 其中前面两行表示检测到的一旦加入最小生成树就会构成回路的边，下面的两个邻接矩阵第一个表示原图的邻接矩阵（为0的地方表示未连接，大于0的地方表示连接且权值就是该值），最下面的6条带权值的边即是最小生成树中的六条边，完全符合前面我们的图示结果。

三、Prim(普里姆)算法

1）算法介绍

有N = {V, {E} } 为一个连通网（V为顶点集合，{E}为由顶点之间的连接关系构成的集合),并定义了一个数组vertexarray[]用来储存他的所有顶点

i.设N0={{}, {} } 为一个非连通网（顶点集合为空，边关系集合为空）即一个空的网络，并创建一个数组minitreevertex[]用于储存该图的顶点。

ii. 选择任意一个顶点作为起点v0,此时N0={{v0},{}},把v0加入minitreevertex[]中,将vertexarray[]中的v0删除。

iii.遍历N0的顶点集合minitreevertex[]与图N1的顶点集合vertexarray[]所构成的边，选出权值最小的一条边(v0,v1)，把该边和v1加入到N0中，把v1加入minitreevertex[]中并把vertexarray[]中的v1删除。以此类推直到vertexarray[]中的所有顶点加入到minitreevertex[]中。

2）算法举例

i.如下图所示是一个连通网N={V,{E}}，其内部定义了一个数组vertexarray[]用来储存他的所有顶点,对其进行Prim算法得到最小生成树

N

 N的顶点数组vertexarray[]:

ii.先创建一个空网络N0={V0={},E0={}}（因为是空网络就无法用图示表示了），并创建一个数组用来储存顶点。

N0的顶点数组minitreevertex[]:


 

 iii.选定一个起点，在这里我们选择顶点0作为起点，并把该点加入到minitreevertex[]和V0中，此时N0={V0={0},{}},并删除掉 vertexarray[]中的顶点0。

N0的顶点数组minitreevertex[]:

 N的顶点数组vertexarray[]:

 iv.此时我们遍历由V0和V1所含的顶点构成的边，也就是顶点0与顶点1、2、3、4、5、6所构成的边，我们可以得到以下边权值表格

 v.找出权值最小的边，我们可以发现是(0,5)这条边，然后我们就可以把（0，5）这条边加入到N中，并且把顶点5加入到N0的顶点集合minitreevertex[]中,并把顶点5从vertexarray[]中删除

N0

N0的顶点数组minitreevertex[]:

N的顶点数组vertexarray[]:

vi.此时我们遍历由V0和V1所含的顶点构成的边，也就是顶点0、5与顶点1、2、3、4、6所构成的边，我们可以得到以下边权值表格

vii.找出权值最小的边，我们可以发现是(5,4)这条边，然后我们就可以把（5，4）这条边加入到N中，并且把顶点4加入到N0的顶点集合minitreevertex[]中,并把顶点4从vertexarray[]中删除

N0

 N0的顶点数组minitreevertex[]:

 N的顶点数组vertexarray[]:

这样下去依次类推，直到vertexarray[]中的所有顶点都被加入到N0中算法即为结束。

3）时间复杂度分析

设一个连通图有n个顶点，当minitreevertex[]中只有一个顶点的时候，需要遍历至多n-1次边的权值并找到权值最小边，当minitreevertex[]中有两个顶点的时候，需要至多遍历2(n-2)次边的权值并找到权值最小边，这样以此类推当minitreevertex[]中有n个顶点,且vertexarray[]为空时，就不需要进行遍历了，将所有项相加最终会得到一个最高项为n^2的式子，因此时间复杂度为O(n^2)。

4)算法实现

我们只要按照上面的算法介绍中的步骤，一步一步进行编写程序，并且加入循环来使得不断重复prim算法的操作直到得到最小生成树即可。

  1. void undigraph::prim()
  2. {
  3.     //初始化最小生成树顶点数组
  4.     for (int i = 0; i < maxsize; i++)
  5.     {
  6.         minivertexarray[i]=0;
  7.     }
  8.     //选择一个起点调用prim算法来生成最小生成树
  9.     cout<<"请输入起点:"<<endl;
  10.     int start;
  11.     cin>>start;
  12.     minivertexarray[0]=start;//输入起点之后就把这个起点从原图的顶点数组中去除
  13.     minivertexarraylength=1;//顶点数组的长度-1
  14.     vertexarray[0]=-1;//把删除掉的元素置为-1
  15.     int min=65536;
  16.     int mini;//定义最小下标
  17.     int minj;
  18.     int symbol=0;//定义一个标志位用来跳出算法循环
  19.     for(int index=1,deletetime=1;symbol==0;)
  20.     {
  21.         min=65536;//每次都要将最小值给重新复位
  22.         for (int i = 0; i <minivertexarraylength; i++)//循环嵌套（因为要遍历两个顶点数组构成的边）
  23.         {
  24.             for (int j = 0; j < vertexarraylength; j++)
  25.             {
  26.                 cout<<"比较("<<minivertexarray[i]<<","<<vertexarray[j]<<")"<<endl;
  27.                 if (vertexarray[j]==-1)//如果发现当前顶点数组中的元素为-1说明是被删除的元素
  28.                 {
  29.                     continue;//跳过该元素
  30.                 }
  31.                 //下面的判断条件解析如下
  32.                 //当边小于当前最小边权值min以及不为0时就将其设为最小边权值min，判断不为0的意义是判断是否相连
  33.                 if (adjmatrix[minivertexarray[i]][vertexarray[j]]!=0&&adjmatrix[minivertexarray[i]][vertexarray[j]]<min)
  34.                 {
  35.                     min=adjmatrix[minivertexarray[i]][vertexarray[j]];//三个变量用来记录临时最小边权值以及对应的下标
  36.                     mini=i;
  37.                     minj=j;
  38.                 }
  39.             }
  40.         }    
  41.         //因为最小生成树是用邻接矩阵储存的，因此要对称赋值
  42.         minimumtree[minivertexarray[mini]][vertexarray[minj]]=min;
  43.         minimumtree[vertexarray[minj]][minivertexarray[mini]]=min;
  44.         cout<<"添加最小生成树边:"<<minivertexarray[mini]<<"----"<<min<<"------"<<vertexarray[minj]<<endl;
  45.         //最小生成树顶点数组加入顶点
  46.         minivertexarray[index]=minj;
  47.         minivertexarraylength+=1;
  48.         //原图数组删除顶点
  49.         vertexarray[minj]=-1;
  50.         //我们使用一个变量deletetime用来计算删除的次数从而来确定原图顶点数组是否删除完毕
  51.         deletetime+=1;
  52.         //最小生成树顶点数组下标加1
  53.         index+=1;
  54.         if (deletetime==vertexnum)//当删除次数达到了原图最开始的顶点数量时表示删除完毕
  55.         {
  56.             symbol=1;//标志位置1
  57.             cout<<"全部顶点已经添加完毕！"<<endl;
  58.         }
  59.     }
  60. }

5）代码执行结果

将下图导入到该算法中可以得出以下结果：

期望结果

 四、全部代码

  1. #include<stdio.h>
  2. #include<iostream>
  3. #define maxsize 100
  4. using namespace std;
  5.  
  6. class line
  7. {
  8.     public:
  9.     int u,v;
  10.     int weight;
  11.     int flag;
  12. };
  13. //     =
  14. // {{0 ,  28  , 0  , 0  , 0 ,  10 ,  0},
  15. // {28 ,  0  , 16 ,  0  , 0 ,  0 , 14},
  16. // {0  , 16 ,  0 ,  12, 0 ,  0 ,  0},
  17. // {0 ,  0  , 12 ,  0  , 22 , 0  ,18},
  18. // {0 ,  0 ,  0  , 22 ,  0  , 0 ,  24},
  19. // {10 ,  0 ,  0  , 0  , 0 ,  0 ,  0},
  20. // {0  , 14 ,  0  , 18 ,  24  , 0  , 0   
  21. //     }};
  22. class undigraph
  23. {
  24.     public:
  25.     line* linearray;
  26.     line* min;
  27.     int vertexnum=0;
  28.     int linenum=0;
  29.     int maxvertex=0;
  30.     int vertexarray[maxsize];
  31.     int vertexarraylength=0;
  32.     int minivertexarray[maxsize];
  33.     int minivertexarraylength=0;
  34.     int adjmatrix[maxsize][maxsize];//用来储存原图
  35.     int minimumtree[maxsize][maxsize];//用来储存最小生成树
  36.     void createundigraph();//创建原图
  37.     void printadjmatrix();//打印原图邻接矩阵
  38.     void printminimumtreematrix();//打印最小生成树的邻接矩阵
  39.     void printminimumtree();//打印最小生成树的各个树边
  40.     void kruskal();//克鲁斯卡尔算法
  41.     bool getfather(int u,int v,int prev);//检测是否构成回路
  42.     void prim();//普利姆算法
  43.  
  44. };
  45.  
  46.  
  47. void undigraph::createundigraph()
  48. { 
  49.     //初始化原图的顶点数组
  50.     for (int i = 0; i < maxsize; i++)
  51.     {
  52.         vertexarray[i]=0;
  53.     }
  54.     
  55.     linearray=new line[(maxsize*(maxsize-1))/2];  //一个有着n个顶点的无向连通图最多有n(n-1)/2条边
  56.     int tempdata;
  57.     int adjvertex;
  58.     int i=0;
  59.     int j=0;
  60.     int k=0;
  61.     int symbol=0;
  62.     for(;;i++)
  63.     {
  64.         if (symbol==0)
  65.         {
  66.             vertexarray[k]=i;
  67.             vertexnum+=1;
  68.             vertexarraylength+=1;
  69.             k+=1;
  70.             while(true)
  71.             {
  72.             cout<<"请输入顶点"<<i<<"的相邻顶点:"<<endl;
  73.             cin>>adjvertex;
  74.             if (adjvertex==-1)//如果输入的相邻顶点为-1,表示相邻的顶点已经输入完毕
  75.             { 
  76.                 break;
  77.             }
  78.             else if (adjvertex==-2)//如果输入为-2表示无向图已经输入完毕
  79.             {
  80.                 symbol=1;
  81.                 break;
  82.             }
  83.             //导入到顶点数组
  84.             
  85.             
  86.             if (adjvertex>=maxvertex)
  87.             {
  88.                 maxvertex=adjvertex+1;//maxvertex用来记录最大顶点序号用于打印邻接矩阵
  89.             }
  90.             cout<<"请输入边("<<i<<","<<adjvertex<<")的权值:"<<endl;
  91.             int tempweight;
  92.             cin>>tempweight;
  93.             linenum+=1;
  94.             //cout<<"linenum:"<<linenum<<endl;
  95.             linearray[j].u=i;//对边的实例进行赋值
  96.             linearray[j].v=adjvertex;
  97.             linearray[j].weight=tempweight; 
  98.             linearray[j].flag=0;        
  99.             cout<<"linearray["<<j<<"]:"<<"u="<<linearray[j].u<<"   v="<<linearray->v<<"   weight="<<linearray->weight<<endl;
  100.             j++;
  101.             adjmatrix[i][adjvertex]=tempweight;//对邻接矩阵进行赋值
  102.             adjmatrix[adjvertex][i]=tempweight;
  103.             }
  104.         }
  105.         else
  106.         {
  107.             break;
  108.         }
  109.         
  110.     }
  111.     //cout<<"邻接矩阵构建完毕"<<endl;
  112.     //cout<<"共有"<<linenum<<"条边"<<endl;
  113. }
  114.  
  115. void undigraph::printadjmatrix()
  116. {
  117.     for (int i = 0; i < maxvertex; i++)
  118.     {
  119.         for (int j = 0; j < maxvertex; j++)
  120.         {
  121.             cout<<adjmatrix[i][j]<<"   ";
  122.         }
  123.         cout<<endl;
  124.     }
  125.     cout<<endl;
  126.     
  127. }
  128.  
  129. void undigraph::printminimumtreematrix()
  130. {
  131.     for (int i = 0; i < maxvertex; i++)
  132.     {
  133.         for (int j = 0; j < maxvertex; j++)
  134.         {
  135.             cout<<minimumtree[i][j]<<"   ";
  136.         }
  137.         cout<<endl;
  138.     }
  139. }
  140.  
  141. void undigraph::kruskal()
  142. {
  143.     line min=linearray[0];//初始化最小权值边为第一条边
  144.     int minindex=0;//初始化最小权值边的下标序号
  145.     for (int j = 0; j < maxvertex+1; j++)//循环签到得到所有边中权值最小的边
  146.     {
  147.         for (int i = 0; i <linenum; i++)
  148.         {   
  149.             if (linearray[i].weight<min.weight&&linearray[i].flag==0)
  150.             {
  151.                 //cout<<"当前最小:("<<linearray[i].u<<","<<linearray[i].v<<")"<<":"<<linearray[i].weight<<endl;
  152.                 minindex=i;
  153.                 min=linearray[i];
  154.                 // cout<<"min的weight:"<<min.weight<<endl;
  155.                 // cout<<"min的u:"<<min.u<<endl;
  156.                 // cout<<"min的v:"<<min.v<<endl;
  157.             }            
  158.         }
  159.         if (getfather(min.u,min.v,-1))//检测是否构成回路
  160.         {
  161.             cout<<"("<<min.u<<")"<<"-----"<<min.weight<<"-----"<<"("<<min.v<<")构成回路！"<<endl;
  162.         }
  163.         else//未构成回路就将这个边加入到最小生成树中
  164.         {
  165.         minimumtree[min.u][min.v]=min.weight;
  166.         minimumtree[min.v][min.u]=min.weight;
  167.         }
  168.         linearray[minindex].flag=1;//并将这条边进行标记，下次循环遍历最小边就不会将其算入其中
  169.         //cout<<"("<<linearray[minindex].u<<","<<linearray[minindex].v<<")"<<"被选择并被标记"<<endl;
  170.         while (linearray[minindex].flag==1)//将当前最小边设置为下一个未被访问的边
  171.         {
  172.             minindex+=1;
  173.             if (minindex==linenum)
  174.             {
  175.                 minindex=0;
  176.             }
  177.             
  178.         } 
  179.         min=linearray[minindex]; 
  180.         //cout<<"当前的min为:"<<min.weight<<endl;
  181.     }
  182.     
  183.     
  184.     //cout<<"权值最小的边为:("<<min.u<<","<<min.v<<")   为:"<<min.weight<<endl;
  185.  
  186. }
  187.  
  188. void undigraph::printminimumtree()
  189. {
  190.     int temptree[maxvertex][maxvertex];
  191.     for (int i = 0; i < maxvertex; i++)
  192.     {
  193.         for (int j = 0; j < maxvertex; j++)
  194.         {
  195.             temptree[i][j]=minimumtree[i][j];
  196.         }
  197.         
  198.     }
  199.     
  200.     for (int i = 0; i < maxvertex; i++)
  201.     {
  202.         for (int j = 0;j<maxvertex;j++)
  203.         {
  204.             if (temptree[i][j]!=0)
  205.             {
  206.                 cout<<"("<<i<<")"<<"-----"<<temptree[i][j]<<"-----"<<"("<<j<<")"<<endl;
  207.                 temptree[j][i]=0;
  208.             }
  209.             
  210.         }
  211.         
  212.     }
  213.     
  214. }
  215.  
  216. bool undigraph::getfather(int u,int v,int prev)//检测当前边是否能够插入最小生成树的参数有三个
  217. {                                              //u和v为边的两个顶点，prev为顶点v前一个访问过的顶点
  218.     int i=0;
  219.     for (; i < maxvertex; i++)
  220.     {    
  221.         if (minimumtree[v][i]>0&&i!=prev)//若检测到最小生成
  222.         {
  223.             //cout<<"minimumtree[v][i]:"<<minimumtree[v][i]<<endl;
  224.             prev=v;
  225.             if (u==i)
  226.             {
  227.                 return true; //如果能够找到另外一条路径到达顶点u说明加入边(u,v)会导致构成回路
  228.             }
  229.             else
  230.             {
  231.             return(getfather(u,i,prev));//递归查找是否能够从另外一条路径到达顶点u
  232.             }
  233.         }
  234.     }
  235.         return false; //如果无法找到一条路径到达顶点u说明加入 边(u,v)不会导致构成回路     
  236. }
  237.  
  238. void undigraph::prim()
  239. {
  240.     //初始化最小生成树顶点数组
  241.     for (int i = 0; i < maxsize; i++)
  242.     {
  243.         minivertexarray[i]=0;
  244.     }
  245.     //选择一个起点调用prim算法来生成最小生成树
  246.     cout<<"请输入起点:"<<endl;
  247.     int start;
  248.     cin>>start;
  249.     minivertexarray[0]=start;//输入起点之后就把这个起点从原图的顶点数组中去除
  250.     minivertexarraylength=1;//顶点数组的长度-1
  251.     vertexarray[0]=-1;//把删除掉的元素置为-1
  252.     int min=65536;
  253.     int mini;//定义最小下标
  254.     int minj;
  255.     int symbol=0;//定义一个标志位用来跳出算法循环
  256.     for(int index=1,deletetime=1;symbol==0;)
  257.     {
  258.         min=65536;//每次都要将最小值给重新复位
  259.         for (int i = 0; i <minivertexarraylength; i++)//循环嵌套（因为要遍历两个顶点数组构成的边）
  260.         {
  261.             for (int j = 0; j < vertexarraylength; j++)
  262.             {
  263.                 if (vertexarray[j]==-1)//如果发现当前顶点数组中的元素为-1说明是被删除的元素
  264.                 {
  265.                     continue;//跳过该元素
  266.                 }
  267.                 //下面的判断条件解析如下
  268.                 //当边小于当前最小边权值min以及不为0时就将其设为最小边权值min，判断不为0的意义是判断是否相连
  269.                 if (adjmatrix[minivertexarray[i]][vertexarray[j]]!=0&&adjmatrix[minivertexarray[i]][vertexarray[j]]<min)
  270.                 {
  271.                     min=adjmatrix[minivertexarray[i]][vertexarray[j]];//三个变量用来记录临时最小边权值以及对应的下标
  272.                     mini=i;
  273.                     minj=j;
  274.                 }
  275.             }
  276.         }    
  277.         //因为最小生成树是用邻接矩阵储存的，因此要对称赋值
  278.         minimumtree[minivertexarray[mini]][vertexarray[minj]]=min;
  279.         minimumtree[vertexarray[minj]][minivertexarray[mini]]=min;
  280.         cout<<"添加最小生成树边:"<<minivertexarray[mini]<<"----"<<min<<"------"<<vertexarray[minj]<<endl;
  281.         //最小生成树顶点数组加入顶点
  282.         minivertexarray[index]=minj;
  283.         minivertexarraylength+=1;
  284.         //原图数组删除顶点
  285.         vertexarray[minj]=-1;
  286.         //我们使用一个变量deletetime用来计算删除的次数从而来确定原图顶点数组是否删除完毕
  287.         deletetime+=1;
  288.         //最小生成树顶点数组下标加1
  289.         index+=1;
  290.         if (deletetime==vertexnum)//当删除次数达到了原图最开始的顶点数量时表示删除完毕
  291.         {
  292.             symbol=1;//标志位置1
  293.             cout<<"全部顶点已经添加完毕！"<<endl;
  294.         }
  295.     }
  296. }
  297.  
  298.  
  299. int main()
  300. {
  301.     // undigraph ug;
  302.     // ug.createundigraph();
  303.     // ug.kruskal();
  304.     // ug.printadjmatrix();
  305.     // ug.printminimumtreematrix();
  306.     // ug.printminimumtree();
  307.     // undigraph ug;
  308.     // ug.createundigraph();
  309.     // ug.prim();
  310.     // ug.printminimumtreematrix();
  311.     // ug.printminimumtree();
  312.     return 0;
  313. }

如果喜欢本文章的话请点点赞哦！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/243455
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号