main.cpp:


#include <iostream>
#include "CMap.h"

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);




//    pMap->printMatrix();
//
//    cout<<endl;
//
//    pMap->depthFirstTraverse(0);
//    cout<<endl;
//    //广度遍历之前，由于之前的点都被表示为已经访问过
//    pMap->resetNode();
//    pMap->breadthFirstTraverse(0);
    return 0;
}

CMap.h:


#ifndef INC_0214_CMAP_H
#define INC_0214_CMAP_H

#include <vector>
#include "Node.h"
#include "Edge.h"
using namespace std;

class CMap{
public:
    CMap(int capacity);
    ~CMap();
    bool addNode(Node *pNode);  //向图中加入顶点（结点）
    void resetNode();           //重置顶点
    bool setValueToMatrixForDirectedGraph(int row,int col,int val = 1);     //为有向图设置邻接矩阵
    bool setValueToMatrixForUndirectedGraph(int row,int col,int val = 1);   //为无向图设置邻接矩阵

    void printMatrix();                         //打印邻接矩阵

    void depthFirstTraverse(int nodeIndex);      //深度优先遍历
    void breadthFirstTraverse(int nodeIndex);   //广度优先遍历

    void primTree(int nodeIndex);//Prim生成树

private:
    bool getValueFromMatrix(int row,int col,int &val);  //从矩阵中获取权值
    void breadthFirstTraverseImp(vector<int> preVec);    //广度优先遍历实现函数
    int getMinEdge(vector<Edge> edgeVec);//找最小边函数
private:
    int m_iCapacity;    //图中最多可以容纳的顶点数
    int m_iNodeCount;   //已经添加的顶点（结点）个数
    Node *m_pNodeArray; //用来指向一段内存，这段内存用来存放顶点数组
    int *m_pMatrix;     //用来存放邻接矩阵

    Edge *m_pEdge;//用于保存最小边，需要在cpp文件中申请一段内存
};

#endif //INC_0214_CMAP_H

CMap.cpp:
#include "CMap.h"
#include "Node.h"
#include <iostream>
#include <vector>
using namespace std;

CMap::CMap(int capacity) {
    m_iCapacity = capacity;
    m_iNodeCount = 0;
    m_pNodeArray = new Node[m_iCapacity];
    m_pMatrix = new int[m_iCapacity * m_iCapacity];
    memset(m_pMatrix,0,m_iCapacity * m_iCapacity * sizeof(int));//需要初始化将这个矩阵的各元素初始化为0；
//也可以用for循环进行初始化：但是注意m_pMatrix是一个一维数组
//    for(int i = 0;i < m_pMatrix*m_pMatrix;i++){
//        m_pMatrix[i] = 0;
//    }
    //存放最小边的空间大小
    m_pEdge = new Edge[m_iCapacity - 1];

}

CMap::~CMap() {//针对析构函数中申请的内存进行释放
    delete []m_pNodeArray;
    delete []m_pMatrix;
}


bool CMap::addNode(Node *pNode) {  //向图中加入顶点（结点）
    if(pNode == NULL){
        return NULL;
    }
    m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;//内存在构造函数时就已经申请好了，只需要付值了
    m_iNodeCount++;
    return true;
}

void CMap::resetNode() {           //重置顶点
    for(int i = 0;i < m_iNodeCount;i++){
        m_pNodeArray[i].m_bIsVisited = false;
    }
}

bool CMap::setValueToMatrixForDirectedGraph(int row,int col,int val) {     //为有向图设置邻接矩阵,函数声明时是int val = 1，但是定义时不加=1
    if(row < 0 || row >= m_iCapacity){
        return false;
    }
    if(col < 0 || col >= m_iCapacity){
        return false;
    }
    m_pMatrix[row * m_iCapacity + col] = val;
    return true;
}

bool CMap::setValueToMatrixForUndirectedGraph(int row,int col,int val) {   //为无向图设置邻接矩阵
    if(row < 0 || row >= m_iCapacity){
        return false;
    }
    if(col < 0 || col >= m_iCapacity){
        return false;
    }
    m_pMatrix[row * m_iCapacity + col] = val;
    m_pMatrix[col * m_iCapacity + row] = val;
    return true;
}

void CMap::printMatrix(){
    for(int i = 0;i < m_iCapacity;i++){
        for(int k = 0; k < m_iCapacity;k++){
            cout << m_pMatrix[i*m_iCapacity+k] << " ";
        }
        cout << endl;
    }
}

bool CMap::getValueFromMatrix(int row,int col,int &val){
    if(row < 0 || row >= m_iCapacity){
        return false;
    }
    if(col < 0 || col >= m_iCapacity){
        return false;
    }
    val = m_pMatrix[row * m_iCapacity + col];
    return true;
}

void CMap::depthFirstTraverse(int nodeIndex){//需要用深度优先遍历实现
    int value = 0;
    cout << m_pNodeArray[nodeIndex].m_cData << " ";
    m_pNodeArray[nodeIndex].m_bIsVisited = true;

    for(int i = 0; i < m_iCapacity;i++){
        getValueFromMatrix(nodeIndex,i,value);//注意引用的写法
        if(value == 1){
            if(m_pNodeArray[i].m_bIsVisited){
                continue;
            } else{
                depthFirstTraverse(i);
            }
        } else{
            continue;
        }
    }
}

void CMap::breadthFirstTraverse(int nodeIndex){
    cout << m_pNodeArray[nodeIndex].m_cData << " ";
    m_pNodeArray[nodeIndex].m_bIsVisited = true;

    //需要用数组来保存被访问过的结点的索引，这里使用vector,标准模板库需要将头文件加入
    vector<int> curVec;
    curVec.push_back(nodeIndex);

    breadthFirstTraverseImp(curVec);
}


void CMap::breadthFirstTraverseImp(vector<int> preVec){
    int value = 0;//用于去邻接矩阵取值，看是否为0
    vector<int> curVec;//用来保存当前这一层的所有节点

    for(int j = 0;j < (int)preVec.size();j++){
        for(int i = 0; i < m_iCapacity;i++){
            getValueFromMatrix(preVec[j],i,value);
            if(value != 0){//如果边存在，还要看对应顶点被访问过没
                if(m_pNodeArray[i].m_bIsVisited){
                    continue;
                } else{//如果存在且没又被访问过
                    cout << m_pNodeArray[i].m_cData<<" ";
                    m_pNodeArray[i].m_bIsVisited = true;

                    curVec.push_back(i);
                }
            }
        }
    }
    //还需要判断这一层是否为空，为空则不必向下进行遍历
    if(curVec.size() == 0){
        return;
    } else{
        breadthFirstTraverseImp(curVec);
    }
}

void CMap::primTree(int nodeIndex) {//Prim生成树
    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);
            if(value != 0){
                if(m_pNodeArray[i].m_bIsVisited) {//看点被访问过没，而不是边
                    continue;
                } else{
                    //若这条边还没有被访问过，放进数组
                    Edge edge(temp,i,value);//用构造函数实例化一个边的对象
                    edgeVec.push_back(edge);
                }
            }
        }
        //此时与temp连接的边都放入了备选边中，不会重复放入同一条边

        //从可选边集合中找出最小的边，连着这条边的另一个顶点就放入点的集合中
        //从可选边集合中找出最小的边函数：
        int edgeIndex = getMinEdge(edgeVec);
        edgeVec[edgeIndex].m_bSelected = true;//把选中的边置为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);//放入点时需要将访问置为true
        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 < edgeVec.size();i++){

        if(!edgeVec[i].m_bSelected){//先看selected是不是为假
            minWeight = edgeVec[i].m_iWeightValue;
            //还需要记录最小边的索引
            edgeIndex = i;
            break;//找到第一个点之后就要跳出循环
        }
    }

    if(minWeight == 0){//找最小边失败，返回-1
        return -1;
    }

    for(;i < edgeVec.size();i++){
        if(edgeVec[i].m_bSelected){//若为true
            continue;
        } else{
            if(minWeight > edgeVec[i].m_iWeightValue){
                minWeight = edgeVec[i].m_iWeightValue;
                edgeIndex = i;
            }
        }
    }

    return edgeIndex;
}

Node.h:



#ifndef INC_0214_NODE_H
#define INC_0214_NODE_H

class Node{
public:
    Node(char data =0);
    char m_cData;
    bool m_bIsVisited;//访问过了是true
};

#endif //INC_0214_NODE_H

Node.cpp:



#include "Node.h"

Node::Node(char data) {
    m_cData = data;
    m_bIsVisited = false;
}

Edge.h:

#ifndef INC_0214_EDGE_H
#define INC_0214_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 //INC_0214_EDGE_H

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;//false为未访问过
}