数据结构----C++实现Kruskal算法（贪心算法）

红太狼 2022-10-25 14:03 204阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70][]

**（1）Kruskal算法——存储结构**

![20210131234755122.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1][]

**（2）如何存储连通分量呢？**

**并查集：集合中的元素组织成树的形式：**

**1. 查找两个元素是否属于同一集合：所在树的根结点是否相同**

**2. 合并两个集合——将一个集合的根结点作为另一个集合根结点的孩子**

**（3）Kruskal算法关键**

**显然，实现Kruskal算法的关键是：如何判断被考察边的两个顶点是否位于两个连通分量（即是否与生成树中的边形成回路）。如果将同一个连通分量的顶点放入一个集合中，则Kruskal算法需要**

**判断被考察边的两个顶点是否位于两个集合，以及将两个集合进行合并等操作。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4][]

**下面给出图的编辑数组存储的类定义，其中成员变量实现图的边集数组存储结构，成员函数实现Kruskal算法。**

**C++实现Kruskal算法：**

#include <iostream>
    using namespace std;
    const int MaxVertex = 10;
    const int MaxEdge = 100;
    const int vertexNum = 6; 
    typedef string DataType;
    struct EdgeType
    {
    	int from;
    	int to;
    	int weight;
    };
    
    class EdgeGraph
    {
    	public:
    		EdgeGraph(); //构造函数
    		~EdgeGraph(); //析构函数
    		void Kruskal();
    	private:
    		int FindRoot(int parent[], int v); //求顶点V所在集合的根 
    		DataType vertex[MaxVertex] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //存储顶点的一维数组
    		struct EdgeType edge[MaxEdge] = {
    			{1,4,12}, {2,3,17}, {0,5,19}, {2,5,25}, {3,5,25}, {4,5,26}, {0,1,34}, {3,4,38}, {0,2,46}}; //存储边的边集数组 
    };
    //构造函数
    EdgeGraph::EdgeGraph(){
    
    }
    //析构函数
    EdgeGraph::~EdgeGraph(){
    	
    }
    //求顶点V所在集合的根
    int EdgeGraph::FindRoot(int parent[], int v){
    	int t = v;
    	while(parent[t] > -1) //求顶点t的双亲一直到根 
    		t = parent[t];
    	return t;
    } 
    //Kruskal算法 
    void EdgeGraph::Kruskal(){
    	int num = 0, i, vex1, vex2;
    	int parent[vertexNum];
    	for(i=0; i<vertexNum; i++)
    	{
    		parent[i] = -1; //初始化n个连通分量 
    	} 
    	for(num=0, i=0; num<vertexNum-1; i++) //依次考察最短边 
    	{
    		vex1 = FindRoot(parent, edge[i].from);
    		vex2 = FindRoot(parent, edge[i].to);
    		if(vex1 != vex2) //位于不同集合 
    		{
    			cout<<"("<<vertex[edge[i].from]<<","<<vertex[edge[i].to]<<") "<<edge[i].weight<<endl;
    			parent[vex2] = vex1; //合并集合 
    			num++;
    		}
    	}
    }
    
    int main()
    {
    	EdgeGraph EG{};
    	EG.Kruskal(); 
    }

**实验结果图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 5][]![20210201002205538.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70]: /images/20221024/15bed3334c77412082ff0f582d167fd5.png
[20210131234755122.png]: /images/20221024/001039be3a6f480a9ac5fa5f5aa6dc24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1]: /images/20221024/c7c8adbdaea54bd195f8cee010578f8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2]: /images/20221024/024eeb3f823b44199dcf48bf06d8c1d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3]: /images/20221024/7026fe5c7c854bef857754310e7aba4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4]: /images/20221024/5f0b41c5e54840159c011ec1462142cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210201002122943.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[20210201002205538.png]: /images/20221024/ea2ddf11d2c14468a642d52dff5030e5.png