普里姆和克鲁斯卡尔最小生成树算法史上最详细菜鸟教程详解(c++版)

针对图数据结构最小生成树普里姆与克鲁斯卡尔算法详细讲解

1. 额外知识点必须知道的东西？首先什么图数据结构，什么又是树，图数据结构和树数据结构又有什么联系和区别，为什么我们的图数据结构需要换成最小生成树，这个生成树在实际中又有什么意义，
   普里姆和克鲁斯卡尔算法又分别是什么，他们之间有什么区别。

2. 图数据结构：首先你必须知道数据结构是什么，所谓数据结构就是数据之间的关系，比如一个队伍，假如导游给我们这个队伍安排一个任务，后面的那个人必须记住前面那个人的编号，这样当排队的时候你就知道你站在谁的后面。像这种利用前面的编号来正确不需要导游来干预的站队，并且每次队伍的前后序列都是固定的。 这个靠什么，其实就是游客和游客之间的关系，一对一的关系。
   如果你告诉游客你随便站，这样每次的排序肯定很难和上次队伍的序列是一样的。并且一个人肯定不能根据2个编号站队，也就是不能是一对二，否则排队序号会出现多个。
   现在就谈我们的主题也就是图数据结构，这个我们用什么例子呢，一个班级中的好朋友的关系网，比如张某某和李某某是好朋友，又和罗什么是好朋友，这些关系比较杂乱。
   或者像我们的网络，各台计算机之间的联系。 这样就有个问题我们假如想根据当前电脑发消息给具体一台计算机我们想找一条具体路径的话，会很多的路径，甚至我们想给每台电脑发次消息，并且不重复发送，也是很困难的。不像排队那种一对一的队伍， 你想遍历下这个队伍，只有从队首开始数就可以。

   像给网络中的具体一台电脑发送消息，我们假如网络通道是独占的，那么我们想快速的发送过去，那么我们必须找到一条最短路径，因为路径太多，这个时候我们算法大神普里姆与克鲁斯卡尔分别研究出来了牛B的算法寻找最短路径的算法。应用非常广，并且算法就用他们的名字命名了。

那么最小生成树又是个什么鬼？首先我们把现实中的网络系统比成一个图数据结构，比如电脑主机看成图中的节点数据，图中的边也就是连线可以表示边2端连接的主机可以通信。那么我们的边数据结构中可以保存2个主机的信息， 甚至比如这2台主机直接通信的也就是发消息接受到的时间确定了，那么我们可以把这个时间作为边的内容也就是权值。
总结，最小生成树其实就是我们修路的全部权值之和最小开销问题，一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。

最小生成树的意义和价值：比如修路，比如我们20个村庄之间需要修路，当然这20个村庄之间的关系就好比图数据结构那种关系，这个时候我们修路肯定是那种从一个村庄可以到其中任何一个村庄，并且路线单一不要重复，这样造价是最低的。这个时候我们需要在图数据结构中或者根据20个村如果要通可以修路的各种方案，并且需要计算出来每2个村庄之间修路的开销，这个时候我们可以从这些路之间找到全部修路的开销，并且要可以走通全部的村庄，还要路不能重复，既不能形成环。

案例就说一个，其实很多的应用场景。

3.我们当前的得到最小生成树的算法都是针对邻接矩阵存储结构来说的，并且针对的是无向图。也就是比如村庄之间修路是没。修路问题。那么邻接矩阵是什么东西呢，其实这个邻接矩阵保存的是每个村庄之间修路的全部开销，其实可以看成是权值 ,我们的村庄之间修路是没有方向，这个方向怎么说呢，比如A村庄修路到B村庄的开销和B村庄开始修路到A村庄的开销肯定是一样，花钱都是一条路啊，在邻接表中就是无向图了。
比如下图 A B C D 分别代表村庄A B C D

//下面给出几个村庄之间的修路开销 ：
A到A本身不修路肯定就是0万 A村庄到B村庄修路开销是40万
A村庄到C村庄修路开销是100万 A村庄到D村庄修路开销150万
B到A村庄还是40万 B村庄到B村庄修路开销是0元
B村庄到C村庄修路开销是200万 B村庄到D村庄修路开销是190万
C村庄到A村庄修路开销是160万 C村庄到B村庄修路开销是230万
C村庄到C村庄修路开始是0万 C村庄到D村庄修路开销是220万
D村庄到A村庄修路开销是280万 D村庄到B村庄修路开销是250万
D村庄到C村庄修路开始是100万 D村庄到D村庄修路开销是0万
//下面是邻接矩阵 保存的是村庄之间的修路开销 由于是无向图 这个矩阵的开销肯定是对称的
这样的话其实是重复了内存保存村庄之间的开销 但是得到开销和设置开销比较简单

A   B   C   D    

A 0 40 100 150
B 40 0 200 190
C 0 230 0 220
D 280 250 100 0

算法的一些用到数据结构定义

1. 注意事项：我们的算法用的是邻接矩阵保存了图中顶点之间的关系，也就是保存边
   我们可以看成这个邻接矩阵保存了村庄之间的修路开销，这个开销可以看成是边的权值

   下面我们贴出图的示意图 比如村庄我们就用符号表示 比如村庄A 我们就用A表示 假如我们的村庄之间可以修路我们就用线连起来

      A
    / | \
   

   B–F–E A,B,C,D,E,F 这几个村庄相关数据假如我们用数组中对应的索引
   \ / \ / 0,1,2,3,4,5 对应
   C—D

2.
村庄开车分析图 树
A
/ \
B D
/ \ / \
C F G - H
\ /
E

深度优先遍历：A B C E F D G H

下面在来描述下对树数据结构的2种遍历方法，我们可以看成假如我们的村庄之间修路形成了一个树的关系图，我们需要从一个具体村庄也就是树的根节点开始访问每个村庄，可以看成开车去各个村庄，如果我们每个村庄就开车去一次，不重复去，这个时候我们根据当前村庄肯定有不同路线，那么我们开车路线有2种办法，第一次叫深度优先遍历算法，也就是我们开车是怎么开呢，比如我从A村庄开始开车，先需要查看地图和A村庄相通的村庄是什么，我们这里是B,D2个村庄，我们先查看B村庄是不是开过，如果没有开过我们就开车进去，然后在查看B村庄的通路，有A村庄和F村庄和C村庄，
我们发现A村庄已经开过，因此在检查C村庄，发现没有开始，这个时候我们就开到c这里，这个时候我们开到E这里，然后开到F这里，这个时候在查询和F相同的村庄发现都开过了。这个时候我们就开车掉头回到E村庄，看看还有没有开过的村庄么，没有就在回退在C,在回退在B,还是没有找到就回退A村庄，发现A的通路D没有开，就开D,然后开到G村庄，回退到D,在开到H村庄，回退，直接到A发现村庄全部被开完了。深度遍历完毕。

那么广度遍历算法的开车办法是什么样的呢？

村庄开车分析图 树
A
/ \
B D
/ \ / \
C F G - H
\ /
E
广度优先遍历：A B D C F G H E
我们开车假如还是从A点开始开，先找到和A村庄的通路存就是B和D村 那么我先开B村，在回退A,在开D村，在回退到B，开始把C,F依次 然后在回退到D，开始G H,在回到C,在E

正式开始上算法代码

/* 下面宏定义让我们实现整数类型0 给我们程序员看返回失败的标志 1是成功*/
#define BOOL int //我们给int类型取一个别名 我们这里int数据类型就取0 1两个数据
#define FALSE O //给0取别名FALSE 
#define TRUE 1 //给1取别名TRUE 


//定义图数据结构中的节点数据类型
typedef struct tag_node
{
char data;      //保存节点中的数据 比如我们这里可以保存字符A,B,C,D,E,F表示村庄
    BOOL visited;   //用来标志当前村庄或者叫节点是不是已经访问过 0表示没有访问 1访问过
} Node; 


//定义数据结构中的边数据类型
typedef struct tag_edge
{
int nodeA;    //当前边的一端节点 比如A和B村庄修路 这个保存A村庄
int nodeB;    //当前边的另一端节点 保存B村庄
int weight;   //当前边的权值 A和B村庄之间修路的开销 
     BOOL selected; //当前边是不是被选入最小生成树的集合去 当我们得到修路最少开销的时候需要选择哪2个村之间修路 选择了我们就存入一个集合保存起来
} Edge;  


//开始正式定义图数据结构类型
typedef struct tag_map
{
int capacity;    //图中节点的个数 也就村庄的个数
    Node *pNodeArray;  //图中的节点集合 也就是存放全部村庄的的一个指针
int nodeCount;     //图中节点的计数 比如图中增加一个村庄我们就加1 
    Edge *pEdge;      //存放全部的边的指针 比如2个村庄之间的关系 组成的序列
} Map; 


//开始申明我们需要的方法

//pMap 二级指针 
//capacity创建图的时候我们需要指定多少个节点 比如构造村庄之间修路的时候指定多少个村庄
void CreatMap(Map **pMap, int capacity);  

//销毁图 只需要给我一个图的指针 
void DestoryMap(Map *pMap);

//给图中增加节点 比如往里面增加新村庄
BOOL AddNode(Map *pMap, Node *pNode);     //添加结点

//把已经访问过的节点 其实就是设置了访问标志的顶点复位
//让程序第二次遍历还是可以访问的
void ResetNodes(Map *pMap);               //重置结点


//给邻接矩阵中设置值 我们针对无向图 需要具体行和列 作为下标
//设置邻接矩阵中的值 其实就是设置row col下标指定的村庄之间的修路开销
//返回值是 0 或者 1 用来表示我们设置邻接矩阵中的值成功还是失败
BOOL SetValueToMatrixForUndirectedGraph(Map *pMap, int row, int col, int val);  


//从邻接矩阵中得到row和col指定的val数值 用来确定村庄A和B之间是不是会修路
//记住我们的村庄A, B, C,D,E,F 分别是用0 1 2 3 4 5来表示
BOOL GetValueFromMatrix(Map *pMap, int row, int col, int &val);



//输出邻接矩阵中的值 可以查看我们设置的值是不是和我们想的一样
void PrintMatrix(Map *pMap); 


//深度优先搜索 我们需要图和第一个顶点数据
void DepthFirstTraverse(Map *pMap, int nodeIndex); 

//图的广度优先搜索 我们还是需要图以及第一个搜索顶点
void BreadthFirstTraverse(Map *pMap, int nodeIndex); //广度优先遍历


void PrimTree(Map *pMap, int nodeIndex);   //普里姆算法

void KruskalTree(Map *pMap);               //克鲁斯卡尔算法

//广度优先遍历算法 需要上次给的顶点集合
void BreadthFirstTraverseImpl(Map *pMap, vector<int> preVec);

int GetMinEdge(vector<Edge> vec);               //获取最小边索引

BOOL IsInSet(vector<int> nodeSet, int target);  //判断顶点索引是否在指定集合

void MergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB); //合并集合


int main(void)
{
//定义一个指针Map变量 准备保存map对象的内存地址
   Map *pMap = null;

//创建图 并且指定有8个顶点 也就是8个村庄
   CreatMap(&pMap,8);


return 0;
}

//初始化图这个数据结构对象 其实就是组拼村庄之间的修路信息
//传进来一个二级指针和图的顶点数
void CreateMap(Map **pMap, int capacity)
{
//开始分配图数据结构map对象的内存 p是保存了指针的内存地址 指针是什么呢比如里面保存了对象 
//内存地址 *p就是对p对应的内存地址得到里面的内容其实就是指针了
    *pMap = (Map *)mallco(sizeof(map));

//开始初始化图中的顶点个数 其实就是村庄的个数
   (*pMap)->Capacity = capacity;

//开始给图中的顶点集合分配内存 其实就是全部村庄的内存
  (*pMap)->pNodeArray = (Node *)malloc(sizeof(Node)*capacity);

//开始遍历每个村庄 也就是每个顶点 设置默认初始值
for(int i = 0; i < capacity; i++)
 {
      (*pMap)->pNodeArray[i].data = 0;     
      (*pMap)->pNodeArray[i].Visited = FALSE;
 }

//开始图中村庄相关的邻接矩阵构造内存 
//规则 我们这里的权值就取0 和1 0表示村庄之间不修路 1表示修路
//如果我们用邻接矩阵来存村庄之间修路的情况 比如村庄是8个 那么他们之间的关系就是8*8 = 60个关系
//也就是
 (*pMap)->pMatrix = (int *)malloc(sizeof(int)*capacity*capacity);

//开始给邻接矩阵赋初始数值
for(int i = 0; i < capacity*capacity; i++)
 {
     (*pMap)->pMatrix[i] = 0;    //值为0 表示村庄之间不修路 
 }

//图中顶点计数变量初始化
 (*pMap)->nodeCount = 0;

//图的顶点的边分配内存 其实我们的最小生成树的顶点数和边的关系是顶点数比边的树大1
(*pMap)->pEdge = (Edge *)malloc((capacity-1) * sizeof(Edge));


//遍历每条边 初始化数据
for(i = 0; i < capacity - 1; i++)
    {
//边的顶点数据 权值 选择标志初始化 
        (*pMap)->pEdge[i].nodeA = -1;
        (*pMap)->pEdge[i].nodeB = -1;
        (*pMap)->pEdge[i].weight = 0;
        (*pMap)->pEdge[i].selected = FALSE;
    }

}


//销毁图的方法 就是把初始化的时候分配的内存都释放就可以了
void DestoryMap(Map *pMap)
{
//释放节点占的内存
free(pMap->pNodeArray);

//指针内容改写
    pMap->pNodeArray = NULL;

//释放边
free(pMap->pEdge);
    pMap->pEdge = NULL;


//邻接矩阵的内存释放
free(pMap->pMatrix);

    pMap->pMatrix = NULL;
}

//给图中加节点 加入新村庄的操作
BOOL AddNode(Map *pMap, Node *pNode)
{
//数据合法性判断
if(pNode ==null)
     {
return FLASE;    //节点数据是null，直接返回一个添加失败的标志
     }

//节点存在 准备存入内存
     pMap->pNodeArray[pMap->nodeCount].data = pNode->data;

//节点计数++ 为下次存节点数据准备
    pMap->nodeCount++;

//返回添加节点成功的标志
return TRUE;
}


//重置节点中数据的访问标志位 这样下次遍历才不会已经是访问过的
void ResetNodes(Map *pMap)
{
//需要遍历每个节点数据
for(int i = 0; i < pMap->capacity; i++)
    {
//得到节点集合中的具体顶点数据
         pMap->pNodeArray[i].visited = FALSE;   //设置节点访问标志位为0
    }
}


//设置邻接矩阵中的值 其实就是设置村庄之间是不是需要修路 需要修路就是用1表示
//村庄就直接用下标表示 
//low 和col就是可以看成是村庄 val是设置到邻接矩阵中的值
BOOL SetValueToMatrixForUndirectGraph(Map *pMap,int low, int col, int val)
{
//下标合法性判断 就是判断下标不能超过村庄数量 
if(low > pMap->capacity - 1 || col > pMap->capacity || low < 0 || col < 0)
     {
return FALSE;   //返回设置失败标识
     }

//下标合法 开始设置邻接表 其实就是指定村庄之间是不是修路
    pMap->pMatrix[low*capacity + col] = val;
//设置矩阵中的对称数据
    pMap->pMatrix[col*capacity + low] = val;

//返回设置成功标志
return TRUE;

}


//从邻接矩阵中得到下标对应的value 其实就是村庄之间的是不是修路的标志
//low col 是对应矩形中的行和列 value是一个变量 我们用来保存从邻接表中得到的值
BOOL GetValueFromMatrix(Map *pMap,int low, int col, int &value)
{
//下标合法性判断 就是判断下标不能超过村庄数量 
if(low > pMap->capacity - 1 || col > pMap->capacity || low < 0 || col < 0)
     {
return FALSE;   //返回设置失败标识
     }
//开始从邻接表中取value
     value = pMap->pMatrix[low*capacity + col]
//设置取值成功的标识
return TRUE;
}

//输出我们的图中的邻接表中的数据 验证正确性
void PrintMatrix(Map *pMap)
{
//开始遍历邻接矩阵中每个value
for(int i = 0; i < capacity; i++)
    {
//我们只需要输出上三角的value 就可以得到村庄之间2个之间是不是要修路
for(int j = 0; j < capacity; j++)
        {
printf("%d",pMap->pMatrix[i*capacity + j]);
        }
//当输完1行之后 我们就换行
printf("\n");
    }
}


//针对图数据结构的深度优先遍历算法
void  DepthFirstTraverse(Map *pMap, int indexNode)
{
//开始访问我们当前的节点 其实就是读节点内存里面对应的data数据 就一次访问
printf("%d",pMap->pNodeArray[indexNode].data);

//开始标识图中的当前节点已经被访问的标志位 防止重复访问
     pMap->pNodeArray[indexNode].visited = TRUE;

//现在要开始得到当前indexNode节点的有关系的全部节点 找到后我们就开始访问这些节点
//开始遍历全部节点索引 用索引和当前节点去邻接表中匹配是不是存在关系
for(int i = 0; i < pMap->capacity; i++)
    {
//通过当前索引我们可以去邻接表取对应的value 也就是权值
//定义变量vlaue保存从邻接矩阵中得到的权值
int value;
          GetValueFromMatrix(pMap,i,indexNode,value);

//开始判断取的权值具体数值
if(value == 0)  //当前2个索引对应的村庄之间不修路 也就是没有边
          {
//那么就比较下个村庄
continue;
          }else   //说明value == 1 当前索引对应的村庄之间修路
          {
//说明找到了和当前节点有关系的另一个节点
//开始判断当前节点是不是访问过
if(pMap->pNodeArray[i].visited == FALSE)
              {
//当前节点还没访问过 那么我们就开始访问 我们用递归
                  DethFirstTraverse(pMap,i);
              }else
              {
//当前节点已经被访问咯 
//那怎么办接着找没有被访问过的节点啊
                  Continue;
              }
          }
    }
}

//从邻接矩阵中得到索引对应的权值
BOOL GetValueFromMatrix(Map *pMap, int row,int col, int &value)
{
//下标合法性判断 就是判断下标不能超过村庄数量 
if(low > pMap->capacity - 1 || col > pMap->capacity || low < 0 || col < 0)
     {
return FALSE;   //返回设置失败标识
     } 

//参数合法 准备从邻接矩阵中取权值
     vlaue = pMap->pMatrix[row*capacity + col];
//返回取值成功的标志
return TRUE;
}

//广度优先遍历算法
void BreadthFirsrtTraverse(Map *pMap, int indexNode)
{
//开始访问当前节点数据
printf("%d",pMap->pNodeArray[indexNode].data);
//开始设置已经访问的标志
     pMap->pNodeArray[indexNode].visited = TRUE;
//定义临时缓存 把当前访问过的节点缓存起来
vector<int> curVec;
     curVec.push_back(indexNode);
//注意我们把缓存的节点传给下面的函数
    BreadthFirstTraverseImpl(pMap,curVec);
}

//正式的广度优先遍历算法 需要一个节点缓存 和图 是上层传过来的数据 注意是递归
//思路我们这个函数会取出一个顶点 然后查询和当前顶点有关系的全部节点 然后保存在一个集合
//在传给下个函数调用 去使用
void BreadthFirstTraverseImpl(Map *pMap, vector<int> preVec)
{
//定义一个value变量 用来保存我们从邻接矩阵中得到下标对应的权值
int value;

//定义向量集合 保存我们当前的函数得到的实参顶点相关的全部顶点集合集合
vector<int> curVec;

//开始遍历preVec中的顶点集合来和邻接矩阵比对对应的右关系的村庄
for(int i = 0; i < preVec.size(); i++)
    {
//开始遍历图中的全部节点索引
for(int j= 0; j < pMap->capacity; j++)
          {
//从邻接矩阵得到对应位置的权值来判断顶点之间是不是有联系
               GetVlaueFromMatrix(pMap,i,j,value);

//开始判断value权值
if(value == 0)
              {
//说明没有关系
//那就比对下个村庄
continue;
              }else
              {
//value == 1 说明找到了顶点的关系顶点
//首先要检查是不是已经访问了
if(pMap->pNodeArray[j].visited == TRUE)
                  {
//那就找其他没有访问的
continue;
                  }else
                  {
//还没有访问
//开始准备访问
printf("%d",pMap->pNodeArrar[j].data);
//设置访问标志
                       pMap->pNodeArray[j].visited = TRUE;

//准备保存当前节点到临时缓存 为了下个调用方法好找下个顶点
                       curVec.push_back(j);
                  }
              }
          }
    }

//执行到这里出了循环 就是当前函数得到的顶点集合的全部边都已经访问过了
//开始判断是不是访问结束 我们根据缓存集合中有没有顶点
if(curVec.size() == 0)
   {
//已经全部访问完毕了
return;
   }else
   {
//说明还有下一层节点需要访问 我们就用递归
        BreadthFirstTraverse(pMap,curVec);
   }

}


//普里姆算法最小生成树
void PrimTree(Map* pMap,int indexNode)
{

//value用于保存从邻接矩阵取出来的边的权值
int value = 0;                  //用于取权值

//边计数器 就是最小生成树的边的个数 
//通过这个边的数量和顶点个数 -1 知道已经完成生成树的过程
int edgeCount = 0;          //为最小生成树的边计数
//定义临时缓存 存放我们已经从图中拿出来的顶点

vector<int> nodeVec;
//把当前顶点索引加入缓存
    nodeVec.push_back(indexNode);

//设置访问过的标识 标识我们已经选择当前顶点作为我们生成树的第一个起点
    pMap->pNodeArrar[indexNode].visited = TRUE;

//当我们加入新的点之后这个顶点就有他的边 这个时候我们把他的全部边都加入到这个缓存中保存
//这个集合中的边 我们会从中选择一个权值最小的边 这个时候对应的一个顶点 就可以加入到我们 
//的顶点缓存咯
vector<Edge> edgeVec;   //用于存放可供选择的边

//设置一个循环来寻找我们的生成树 其实就是找全部的边
//刚好树的边是顶点数-1
while(edgeCount < pMap->capacity - 1) //说明我们还没有找完全部的边
    {
//开始从缓存中取出我们的顶点数据 开始寻找边了
int temp = nodeVec.back();

//开始遍历当前图中全部的顶点
for(int i = 0; i < pMap->capacity; i++)
        {
//开始比对邻接矩阵
               GetValueFromMatrix(pMap,temp,i,value);

//value的权值做判断
if(value == 0)
               {
//说明当前i索引对应的村庄和temp顶点没有关系
//我们就进行下一个比对
continue;
               }else
               {
//说明找到了边
//判断当前顶点是不是被访问过
if(pMap->pNodeArray[i].visited == FALSE)
                    {
//没有被访问
//我们就找到了边
//开始创建边 并且准备加入到缓存中保存
                          Edge edge;
//保存边的2个相关顶点
                          edge.nodeA = temp;
                          edge.nodeB = i;
//设置权值
                          edge.weight = value;
//默认当前边还没有被选择到最小生成树中
                          edge.selected = FALSE;
//加入缓存
                          edgeVec.push_back(edge);

                    }else
                    {
//说明当前顶点已经被访问了 那么我们就换一个顶点
continue;
                    }
               }
        }

//现在我们开始从当前边集合中得到一个权值最小的边做为生成树中的一部分
//我们是得到对应的索引
int edgeIndex = GetMinEdge(edgeVec);
//设置当前边被选的标志
        edge[edgeIndex].selected = TRUE;
//将权值最小边放入最小生成树的边集合
        pMap->edge[edgeCount] = edge[edgeIndex];

//边计数器++
        edgeCount++;
//找到与当前最小边连接的点 需要存入点集合 先取出来
int nextNodeIndex = edgeVec[edgeIndex].nodeB;

//输出边的顶点以及边的权值
printf("%d--%d %d\n", edgeVec[edgeIndex].nodeA, edgeVec[edgeIndex].nodeB,     
        edgeVec[edgeIndex].weight);
printf("%d\n", nextNodeIndex);

//将该点放入点集合
        nodeVec.push_back(nextNodeIndex);

//设置访问过的标志 
        pMap->pNodeArray[nextNodeIndex].visited = TRUE;
    }

}

//从边集合中得到一个权值最小的边
int GetMinEdge(vector<Edge> edge)
{
//边的权值
int weight = 0;
//边的索引
int edgeIndex = 0;

//遍历集合中的全部的边
for(int i = 0; i < edge.size(); i++)
      {
//判断当前边是不是被选择了
if(edge.selected == FALSE)
            {
//只有还没被选择我们才
                weight = edge.weight;
                edgeIndex = i;
break;
            }
      }

//也可能我们还没有找到一条边
if(weight == 0)
      {
//直接退出
return;
      }

//现在开始比较边 找到最小的边 权值最小的边
for(int i = 0; i < edge.size(); i++)
     {
//当前边被选择了 我们就找下个边
if(edge.selected == TRUE)
           {
               Continue;
           }else
           {
if(edge[i].weight < weight)
               {
                    weight = edge.weigt;
                    edgeIndex = i;
               }
           } 
     }

return edgeIndex;

}


//克鲁斯卡尔最小生成树算法
void krusalTree(Map* pMap)
{
//定义vlua 变量准备接受从邻接矩阵中拿到的权值 来判断顶点之间的关系
int value = 0;  //默认是0
//定义生成树的边计数器
int edgeCount = 0;   // 默认是0条边 
//定义保存生成树边集合的向量集合数据结构变量
vector<Edge> edgeVec;   

//开始遍历图的全部顶点 准备构造全部的边
for(int i = 0; i < capacity; i++)
     {
//由于是邻接矩阵存储的边 因此我们只需要上三角的元素
for(int j = i + 1; j < capacity; j++)
          {
//取出边的值
               GetValueFromMatrix(pMap, i, k, value);
if(value != 0)
               {
//找到了边
//准备构建边对象
                   Edge edge;
                   edge.nodeA = i;
                   edg.nodeB = j;
                   edge.weight = value;
                   edge.selected = FALSE;
//开始加入缓存
                   edgeVec.push_back(edge);
               }
          }
     }

//开始循环构造最小生成树 选择的边数少于顶点数-1就一直执行循环选择边生成最小生成树
while(edgeCount < pMap->capacity)
     {
//取出最小边 从上面构造的边集合
int minEdgeIndex = GetMinEdge(edgeVec);      
//标识当前边已经被选择的标志
        edgeVec[minEdgeIndex].selected = TRUE;

//得到边的顶点
int nodeAIndex = edgeVec[minEdgeIndex].nodeA;
int nodeBIndex = edgeVec[minEdgeIndex].nodeB;

//从所有点集合寻找该边连接的两个点
        BOOL nodeAIsInSet = FALSE;
        BOOL nodeBIsInSet = FALSE;

int nodeAInSetLabel = -1;   //用于记录A点所在的点集合索引
int nodeBInSetLabel = -1;   //用于记录B点所在的点集合索引

int i = 0;
//找出A结点所在的集合 遍历总边的集合得到具体一个边 比对点
for(i = 0; i < (int)nodeSets.size(); i++)
        {
//判断nodeAIndex点是不是在集合nodeSets[i]中
            nodeAIsInSet = IsInSet(nodeSets[i], nodeAIndex);

if(nodeAIsInSet) //在
            {
//我们就保存当前顶点集合的索引 其实就可以拿到这个顶点所在的边
                nodeAInSetLabel = i;
            }
        }
//找出B结点所在的集合 同A节点
for(i = 0; i < (int)nodeSets.size(); i++)
        {
            nodeBIsInSet = IsInSet(nodeSets[i], nodeBIndex);
if(nodeBIsInSet)
            {
                nodeBInSetLabel = i;
            }
        }

/*---根据nodeAInSetLabel与nodeBInSetLabel的值做出处理---*/

//开始判顶点和 顶点集合也就是边的关系

//边的两个结点均为新的结点，放在一个新的集合中
//说明我们得到的边是孤立的边
if(nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
        {
//点的集合 新边 没有和啥顶点有联系我们需要先加入缓存保存以后要用拼接最小生成
//树用
vector<int> vec;

//保存进去 单个顶点保存
            vec.push_back(nodeAIndex);
            vec.push_back(nodeBIndex);

//在整体保存到集合的集合中 
            nodeSets.push_back(vec);

        }
//A点在某集合中，B点不在任何集合中，将B点放在A点所在集合中
else if(nodeAInSetLabel != -1 && nodeBInSetLabel == -1)
        {
//这个时候我需要把B点加入到A点那个集合 因为他们是生成树中的整体了 不是孤立的
            nodeSets[nodeAInSetLabel].push_back(nodeBIndex);
        }
//B点在某集合中，A点不在任何集合中，将A点放在B点所在集合中
else if(nodeAInSetLabel == -1 && nodeBInSetLabel != -1)
        {
            nodeSets[nodeBInSetLabel].push_back(nodeAIndex);
        }
//A点在某集合中,B点在某集合中,如果所在集合相同，说明同一个集合两点均存在，
//形成了环路，摒弃该边
else if(nodeAInSetLabel == nodeBInSetLabel && nodeAInSetLabel != -1)  
        {
continue;
        }
//A点在某集合中,B点在某集合中,如果所在集合不相同，则说明这条边是连接两棵独立树的边，然后需要合并点集合
else if(nodeAInSetLabel != nodeBInSetLabel && nodeAInSetLabel != -1 && nodeBInSetLabel != -1)
        {
//合并A，B所在的点集合到A点所在集合
            MergeNodeSet(nodeSets[nodeAInSetLabel], nodeSets[nodeBInSetLabel]);
//删除B点所在集合
for(int k = nodeBInSetLabel; k < (int)nodeSets.size()-1; k++)
            {
                nodeSets[k] = nodeSets[k + 1];
            }
        }
else
        {
continue;
        }

//在以上所有情况中，除了边被摒弃的情况直接开始下一次循环外，能通过判断的边，可以加入到最小生成树的边集合中
printf("%d--%d %d\n", edgeVec[minEdgeIndex].nodeA, edgeVec[minEdgeIndex].nodeB, edgeVec[minEdgeIndex].weight);

//把边存进去
        pMap->pEdge[edgeCount] = edgeVec[minEdgeIndex];

//边计数器++
        edgeCount++;

     }
}

//合并点集合
void MergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB)
{
for(int i = 0; i < (int)nodeSetB.size(); i++)
    {
        nodeSetA.push_back(nodeSetB[i]);
    }
}
//判断某点是否在指定的点集合中
BOOL IsInSet(vector<int> nodeSet, int target)
{
for(int i = 0; i < (int)nodeSet.size(); i++)
    {
if(nodeSet[i] == target)
        {
return TRUE;
        }
    }
return FALSE;
}