一、需求图Prim算法最小生成树
无向图中点与点之间，边上的数字表示权值。
二、实现Prim算法最小生成树
1.边的描述
定义边的对象时应有以下属性：这条边连接两端的点（nodeIndexA，nodeIndexB），边的权值，以及这条边是否被选中
//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;
}
2.图的描述
CMap见：数据结构之图---深度优先遍历---C++实现
//在CMap.h中添加
void primTree(int nodeIndex); //普利姆算法实现最小生成树
int getMinEdge(vector<Edge> edgeVec); //获取待选边集合中权值最小的边
Edge *m_pEdge; //存放边
//在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) //算法结束的条件，最小生成树边的数量是容量的-1
{
int temp = nodeVec.back();
for (int i = 0; i < m_iCapacity;i++) //以一个顶点出发，遍历与该点连接的所有的边
{
getValueFromMatrix(temp, i, value);
if (value != 0)
{
if (m_pNodeArray[i].m_bisVisited)
{
continue;
}
else
{
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];
edgeCount++;
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;
for (i = 0; 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 < (int)edgeVec.size(); i++)
{
if (edgeVec[i].m_bSelected)
{
continue;
}
else
{
if (minWeight > edgeVec[i].m_iWeightValue)
{
minWeight = edgeVec[i].m_iWeightValue;
edgeIndex = i;
}
}
}
return edgeIndex;
}
//在构造函数中添加：CMap::CMap()添加
m_pEdge = new Edge[m_iCapacity-1]; //用来存最小生成树的边的个数
//在析构函数中添加：CMap::~CMap()添加
delete []m_pEdge;
3.算法的调用
//main.cpp
#include "stdio.h"
#include "stdlib.h"
#include "CMap.h"
#include <iostream>
/*
图的存储和图的遍历
*/
using namespace std;
void 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); //more
pMap->kruskalTree();
}
三、Prim算法的分析
算法思路：
1.从A开始，通过遍历邻接矩阵的第0行可得，与A相连接共有3条边(A-B(6)，A-F(1)，A-E(5))，把这3条边放入待选边集合中edgeVec。
2.从待选集合中选出权值最小的一条边，将这条边的已被选中的属性改为true，放入m_pEdge指向的数组中。
3.将最小边(A-F)的另外一个端点找到为F，将F放入点集合中nodeVec。
4.将与F点相连接的边(F-A(1)，F-B(2)，F-C(8)，F-D(4)，F-E(9)）,放入待选集合中edgeVec，此时待选边集合*有(A-B(6)，A-F(1)，A-E(5)，F-A(1)，F-B(2)，F-C(8)，F-D(4)，F-E(9))其中A-F(1)，F-A(1)指的是一条边并且已经本选中了，所有严格说来待选边合集*有(A-B(6)，A-E(5)，F-B(2)，F-C(8)，F-D(4)，F-E(9))6条边。
5.将待选集合中的6条边选出权值最小的边（F-B(2)），
6.依次类推