c++实现普利姆算法生成树

墨蓝 2022-02-16 05:58 161阅读 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

void primTree(int nodeIndex); //普利姆生成树
    int getMinEdge(vector<Edge> edgeVec);

Cmap.cpp

//普利姆生成树
    void CMap::primTree(int nodeIndex)
    {
    	int value = 0;//用来存储边的权值 
    	int edgeCount = 0; //用来存储边的总数
    	vector<int> nodeVec; //用来点的集合
    	vector<Edge> edgeVec; //用来边的集合  备选边集合
    
    	cout << m_pNodeArray[nodeIndex].m_cData << endl;
    
    	nodeVec.push_back(nodeIndex);
    	m_pNodeArray[nodeIndex].m_bIsVisited = true;
    
    	//当边数达到最大值时退出循环
    	 while(edgeCount < m_iCapacity - 1)
    	{
    		 int temp = nodeVec.back(); //从容器中取出最后一个元素
    		 //寻找与该节点连接的所有边 放入备选边集合中
    		 for (int i = 0; i < m_iCapacity; i++)
    		 {
    			 getValueFromMatrix(temp, i, value);
    			 //权值不为0且没有被访问过
    			 if (value != 0&&!m_pNodeArray[i].m_bIsVisited)
    			 {
    				 Edge edge(temp, i, value);
    				 edgeVec.push_back(edge);
    
    			 }
    		 }
    		 //从可选边集合中找出最小的边
    		 int edgeIndex = getMinEdge(edgeVec);
    		 edgeVec[edgeIndex].m_bSelected = true; //将该边设置为已经选中状态
    		
    		 //打印这条边的信息
    		 cout << edgeVec[edgeIndex].m_iNodeIndexA << "--" << edgeVec[edgeIndex].m_iNodeIndexB << " ";
    		 cout << edgeVec[edgeIndex].m_iWeightValue << endl;
    
    		 m_pEdge[edgeCount++] = edgeVec[edgeIndex]; //将最小的边放入最小边集合中
    		 
    		 //找到与最小边连接的点  
    		 int nextNodeIndex = edgeVec[edgeIndex].m_iNodeIndexB;
    		 nodeVec.push_back(nextNodeIndex);
    		 m_pNodeArray[nextNodeIndex].m_bIsVisited = true; //这个点设置为已访问状态
    
    		 //打印这个点
    		 cout << m_pNodeArray[nextNodeIndex].m_cData << endl;
    
    	}
    }
    int CMap::getMinEdge(vector<Edge> edgeVec)
    {
    	//int minWeight = 0;
    	//int edgeIndex = 0;
    	//int i = 0;
    	//for (; i < int(edgeVec.size()); i++)
    	//{
    	//	//选出第一条没有被选择的边
    	//	if (!edgeVec[i].m_bSelected)
    	//	{
    	//		minWeight = edgeVec[i].m_iWeightValue;
    	//		edgeIndex = i;
    	//		break;
    	//	}
    	//}
    	//if (minWeight == 0)
    	//{
    	//	return -1;
    	//}
    	//for (; i < edgeVec.size(); i++)
    	//{
    	//	if (!edgeVec[i].m_bSelected&&minWeight > edgeVec[i].m_iWeightValue)
    	//	{
    	//		minWeight = edgeVec[i].m_iWeightValue;
    	//		edgeIndex = i;
    	//	}
    	//}
    
    	//优化版
    	int minWeight = INT32_MAX;  //将其设置为int最大值
    	int edgeIndex = 0;
    	for (int i = 0; i < edgeVec.size(); i++)
    	{
    		if (!edgeVec[i].m_bSelected&&minWeight > edgeVec[i].m_iWeightValue)
    		{
    			minWeight = edgeVec[i].m_iWeightValue;
    			edgeIndex = i;
    		}
    	}
    	if (minWeight == INT32_MAX)
    	{
    		return -1;
    	}
    	return edgeIndex;
    }

demo.cpp

#include <iostream>
    #include <cstdlib>
    #include "CMap.h"
    using namespace std;
    /*
    
    普利姆算法
          A
        / | \
       B--F--E
       \ / \ /
    	C---D
    ABCDEF
    012345
    A-B 6   A-E 5   A-F 1
    B-C 3   B-F 2
    C-F 8   C-D 7
    D-F 4   D-E 2
    E-F 9
    	*/
    int main() 
    {
    	CMap *pMap = new CMap(6);
    
    	Node *pNodeA = new Node('A');
    	Node *pNodeB = new Node('B');
    	Node *pNodeC = new Node('C');
    	Node *pNodeD = new Node('D');
    	Node *pNodeE = new Node('E');
    	Node *pNodeF = new Node('F');
    
    
    	pMap->addNode(pNodeA);
    	pMap->addNode(pNodeB);
    	pMap->addNode(pNodeC);
    	pMap->addNode(pNodeD);
    	pMap->addNode(pNodeE);
    	pMap->addNode(pNodeF);
    
    
    	pMap->setValueToMatrixForUndirectedGraph(0, 1,6);
    	pMap->setValueToMatrixForUndirectedGraph(0, 4,5);
    	pMap->setValueToMatrixForUndirectedGraph(0, 5,1);
    	pMap->setValueToMatrixForUndirectedGraph(1, 2,3);
    	pMap->setValueToMatrixForUndirectedGraph(1,5,2);
    	pMap->setValueToMatrixForUndirectedGraph(2,5,8);
    	pMap->setValueToMatrixForUndirectedGraph(2,3,7);
    	pMap->setValueToMatrixForUndirectedGraph(3,5,4);
    	pMap->setValueToMatrixForUndirectedGraph(3,4,2);
    	pMap->setValueToMatrixForUndirectedGraph(4,5,9);
    
    	pMap->primTree(0);
    	delete pMap;
    	system("pause");
    	return 0;
    }

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