数据结构之图---最小生成树Prim算法---C++实现

时间:2021-12-04 12:37:11

一、需求图Prim算法最小生成树

数据结构之图---最小生成树Prim算法---C++实现

无向图中点与点之间,边上的数字表示权值。

二、实现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.依次类推