c++实现克鲁斯卡尔算法生成树

野性酷女 2022-02-16 05:58 275阅读 0赞

### 普利姆算法 ###

[图部分代码][Link 1]  
Edge.h

#ifndef EDGE_H_
    #define EDGE_H_
    class Edge
    {
    public:
    	Edge(int nodeIndexA = 0,int nodeIndexB = 0,int weightValue = 0);
    	int m_iNodeIndexA;
    	int m_iNodeIndexB;
    	int m_iWeightValue;
    	bool m_bSelected;
    };
    #endif

Edge.cpp

#include "Edge.h"
    
    Edge::Edge(int nodeIndexA, int nodeIndexB, int weightValue)
    {
    	m_iNodeIndexA = nodeIndexA;
    	m_iNodeIndexB = nodeIndexB;
    	m_iWeightValue = weightValue;
    	m_bSelected = false;
    }

CMap.h

bool isInSet(vector<int> nodeSet, int target); //判断顶点是否在集合中
    	void mergeNodeSet(vector<int>&nodeSetA,vector<int>nodeSetB);//合并两集合
    	void kruskalTree(); //克鲁斯卡尔算法生成树

Cmap.cpp

void CMap::kruskalTree()
    {
    	int value;  //用来取边的权值
    	int edgeCount = 0; //存储的边的个数
    	
    	//定义存放结点集合的数组
    	vector<vector<int>> nodeSets;
    
    	//第一步：取出所有边
    	vector<Edge> edgeVec;
    	for (int i = 0; i < m_iCapacity; i++)
    	{
    		//取出邻接矩阵上三角部分的值
    		for (int k = i + 1; k < m_iCapacity; k++)
    		{
    			getValueFromMatrix(i, k, value);
    			if (value)
    			{
    				Edge edge(i,k,value);
    				edgeVec.push_back(edge);
    			}
    		}
    	}
    
    	//第二部：从所有边中取出组成最小生成树的边 
    	//1.找到算法结束条件
    	while (edgeCount < m_iCapacity - 1)
    	{
    		//2.从边集合中找到最小边
    		int minEdgeIndex = getMinEdge(edgeVec);
    		edgeVec[minEdgeIndex].m_bSelected = true;
    
    		//3.找到最小边连接的点
    		int nodeAIndex = edgeVec[minEdgeIndex].m_iNodeIndexA;
    		int nodeBIndex = edgeVec[minEdgeIndex].m_iNodeIndexB;
    
    		bool nodeAIsInSet = false;
    		bool nodeBIsInSet = false;
    		int nodeAInSetLabel = -1;
    		int nodeBInSetLabel = -1;
    
    		//4.找出点所在的点集合
    		for (int i = 0; i < nodeSets.size(); i++)
    		{
    			nodeAIsInSet = isInSet(nodeSets[i], nodeAIndex);
    			if (nodeAIsInSet)//判断点是否在该集合中
    			{
    				//A只可能在一个集合中
    				nodeAInSetLabel = i;//保存A所在的集合索引
    			}
    		}
    		for (int i = 0; i < nodeSets.size(); i++)
    		{
    			nodeBIsInSet = isInSet(nodeSets[i], nodeBIndex);
    			if (nodeBIsInSet)//判断点是否在该集合中
    			{
    				//A只可能在一个集合中
    				nodeBInSetLabel = i;//保存A所在的集合索引
    			}
    		}
    		//判断A,B两个查找结果，即两个索引
    		if (nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
    		{
    			vector<int> vec;
    			vec.push_back(nodeAIndex);
    			vec.push_back(nodeBIndex);
    			nodeSets.push_back(vec);
    		}
    		if (nodeAInSetLabel == -1 && nodeBInSetLabel != -1)
    		{
    			nodeSets[nodeBInSetLabel].push_back(nodeAIndex);
    		}
    		else if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1)
    		{
    			nodeSets[nodeAInSetLabel].push_back(nodeBIndex);
    		}
    		else if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel)
    		{
    			//合并两个集合
    			mergeNodeSet(nodeSets[nodeAInSetLabel], nodeSets[nodeBInSetLabel]);
    			//去掉nodeSets中B集合
    			for (int k = nodeBInSetLabel; k < (int)nodeSets.size()-1; k++)
    			{
    				nodeSets[k] = nodeSets[k + 1];
    			}
    		}
    		else if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel)
    		{
    			//两个点在同一个集合中，则不处理
    			continue;
    		}
    		m_pEdge[edgeCount++] = edgeVec[minEdgeIndex]; //保存边结点
    		cout << edgeVec[minEdgeIndex].m_iNodeIndexA << "--" << edgeVec[minEdgeIndex].m_iNodeIndexB
    			<< edgeVec[minEdgeIndex].m_iWeightValue << endl;
    			//5.根据点所在集合的不同做出不同处理
    	}
    }
    bool CMap::isInSet(vector<int> nodeSet, int target)
    {
    	for (int i = 0; i < nodeSet.size(); i++)
    	{
    		if (nodeSet[i] == target)
    		{
    			return true;
    		}
    	}
    	return false;
    }
    
    void CMap::mergeNodeSet(vector<int>& nodeSetA, vector<int> nodeSetB)
    {
    	for (int i = 0; i < nodeSetB.size(); i++)
    	{
    		nodeSetA.push_back(nodeSetB[i]);
    	}
    }

[Link 1]: https://blog.csdn.net/xgy123xx/article/details/89409350