全部频道

首页 热点资讯 义务教育 高等教育 出国留学 考研考公
您的当前位置：首页正文

数据机构探险之图（下）篇：代码实战

2024-12-20 来源：化拓教育网

数据机构探险之图篇（代码编写）

  • 图的存储（邻接矩阵） & 图的深度优先 & 广度优先
  • 图的编码实战-最小生成树（普里姆算法）
  • 图的编码实战-最小生成树之克鲁斯卡尔算法

图的存储（邻接矩阵） & 图的深度优先 & 广度优先

要求 题目 
#ifndef NODE_H
#define NODE_H
class Node
{
public:
    Node(char data = 0);
    char m_cData;//数据值
    bool m_bIsVisited;//有没有被访问
};
#endif

#include "Node.h"

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

#ifndef CMAP_H
#define CMAP_H
#include "Node.h"
#include <vector>
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);//广度优先遍历

private:
    bool getValueFromMatrix(int row, int col, int &val);//从矩阵中获取权值
    void breadthFirstTraverseImpl(vector<int> preVec);//广度优先遍历实现函数

private:
    int m_iCapacity;
    //图中最多可以容纳的顶点数
    int m_iNodeCount;
    //已经添加的顶点（结点）个数
    Node *m_pNodeArray;
    //用来存放顶点数组
    int *m_pMatrix;
    //用来存放邻接矩阵
};

#endif

Cmap.cpp:

#include "CMap.h"
#include <iostream>
#include <vector>
#include "Node.h"
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];//邻接矩阵size乘size
    //邻接矩阵初始化为全0
    //memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));
    //将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值， 第一个值为指定的内存地址，块的大小由第三个参数指定
    for (int i=0;i<m_iCapacity*m_iCapacity;i++)
    {
        m_pMatrix[i] = 0;
    }

}

CMap::~CMap()
{
    delete []m_pNodeArray;
    delete[]m_pMatrix;
}

bool CMap::addNode(Node *pNode)
{
    if (pNode == NULL)
    {
        return false;
    }
    //保存节点数据
    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)
{
    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;
}
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::printMatrix()
{
    //两重循环（i行k列）
    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;
    }
}

//深度优先
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 !=0)//判断有弧连接其他顶点
        {
            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<int> curVec;
    curVec.push_back(nodeIndex);

    breadthFirstTraverseImpl(curVec);

}

void CMap::breadthFirstTraverseImpl(vector<int> preVec)
{
    int value = 0;
    vector<int> curVec;

    //prevec为上一层节点
    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
    {
        breadthFirstTraverseImpl(curVec);
    }

}

main.cpp:

#include "CMap.h"
#include <stdlib.h>
#include "Node.h"
#include <iostream>
using namespace std;

int main()
{
    CMap *pMap = new CMap(8);

    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');
    Node *pNodeG = new Node('G');
    Node *pNodeH = new Node('H');


    pMap->addNode(pNodeA);
    pMap->addNode(pNodeB);
    pMap->addNode(pNodeC);
    pMap->addNode(pNodeD);
    pMap->addNode(pNodeE);
    pMap->addNode(pNodeF);
    pMap->addNode(pNodeG);
    pMap->addNode(pNodeH);

    pMap->setValueToMatrixForUndirectedGraph(0, 1);
    pMap->setValueToMatrixForUndirectedGraph(0, 3);
    pMap->setValueToMatrixForUndirectedGraph(1, 2);
    pMap->setValueToMatrixForUndirectedGraph(1, 5);
    pMap->setValueToMatrixForUndirectedGraph(3, 6);
    pMap->setValueToMatrixForUndirectedGraph(3, 7);
    pMap->setValueToMatrixForUndirectedGraph(6, 7);
    pMap->setValueToMatrixForUndirectedGraph(2, 4);
    pMap->setValueToMatrixForUndirectedGraph(4, 5);

    pMap->printMatrix();
    cout << endl;

    pMap->resetNode();
    //指定起始点的索引
    pMap->depthFirstTraverse(0);
    cout << endl;

    pMap->resetNode();
    pMap->breadthFirstTraverse(0);
    cout << endl;

    system("pause");
    return 0;
}

运行结果：

运行结果

图的编码实战-最小生成树（普里姆算法）

例子

边与边之间存在权值。如a-b 为6

edge.h&cpp:

#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


#include "Edge.h"

Edge::Edge(int nodeIndexA, int nodeIndexB, int weightValue)
{
    m_iNodeIndexA = nodeIndexA;
    m_iNodeIndexB = nodeIndexB;
    m_iWeightValue = weightValue;
    m_bSelected = false;
}

node.h&cpp:

#ifndef NODE_H
#define NODE_H
class Node
{
public:
    Node(char data = 0);
    char m_cData;//数据值
    bool m_bIsVisited;//有没有被访问
};
#endif


#include "Node.h"

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

cmap.h & cpp:

#ifndef CMAP_H
#define CMAP_H
#include "Node.h"
#include <vector>
#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); //普里姆生成树指定的第一个点，找出与他相连的最小边
private:
    bool getValueFromMatrix(int row, int col, int &val);//从矩阵中获取权值
    void breadthFirstTraverseImpl(vector<int> preVec);//广度优先遍历实现函数



    int getMinEdge(vector<Edge> edgeVec);



private:
    int m_iCapacity;
    //图中最多可以容纳的顶点数
    int m_iNodeCount;
    //已经添加的顶点（结点）个数
    Node *m_pNodeArray;
    //用来存放顶点数组
    int *m_pMatrix;
    //用来存放邻接矩阵

    Edge *m_pEdge;
    
};

#endif


#include "CMap.h"
#include <iostream>
#include <vector>
#include "Node.h"
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];//邻接矩阵size乘size
    //邻接矩阵初始化为全0
    //memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));
    //将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值， 第一个值为指定的内存地址，块的大小由第三个参数指定
    for (int i=0;i<m_iCapacity*m_iCapacity;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 false;
    }
    //保存节点数据
    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)
{
    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;
}
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::printMatrix()
{
    //两重循环（i行k列）
    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;
    }
}

//深度优先
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 !=0)//判断有弧连接其他顶点
        {
            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<int> curVec;
    curVec.push_back(nodeIndex);

    breadthFirstTraverseImpl(curVec);

}

void CMap::breadthFirstTraverseImpl(vector<int> preVec)
{
    int value = 0;
    vector<int> curVec;

    //prevec为上一层节点
    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
    {
        breadthFirstTraverseImpl(curVec);
    }

}

//普利姆生成树
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;
    //什么时候停下来，边数等于点数-1时
    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);
                }
            }
        }

        //才可选边集合中找出最小的边
        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 = 0;
    for ( ;i<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)
        {
            continue;
        }
        else
        {
            if (minWeight >edgeVec[i].m_iWeightValue)
            {
                minWeight = edgeVec[i].m_iWeightValue;
                edgeIndex = i;
            }
        }
    }
    return edgeIndex;
}

main.cpp:

#include "CMap.h"
#include <stdlib.h>
#include "Node.h"
#include <iostream>
using namespace std;

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

    system("pause");
    return 0;
}

运行结果：

运行结果

图的编码实战-最小生成树之克鲁斯卡尔算法

题目
  • 找出所有的边
  • 在边中找到最小生成树的集合

node.cpp&h edge.cpp&h与上面的一样

cmap.h&cpp

#ifndef CMAP_H
#define CMAP_H
#include "Node.h"
#include <vector>
#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); //普里姆生成树指定的第一个点，找出与他相连的最小边
    void kruskalTree();//克鲁斯卡尔算法生成树


private:
    bool getValueFromMatrix(int row, int col, int &val);//从矩阵中获取权值
    void breadthFirstTraverseImpl(vector<int> preVec);//广度优先遍历实现函数
    bool isInSet(vector<int> nodeSet, int target); //判断顶点是否在点集合中
    void mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB);//合并两个点集合


    int getMinEdge(vector<Edge> edgeVec);



private:
    int m_iCapacity;
    //图中最多可以容纳的顶点数
    int m_iNodeCount;
    //已经添加的顶点（结点）个数
    Node *m_pNodeArray;
    //用来存放顶点数组
    int *m_pMatrix;
    //用来存放邻接矩阵

    Edge *m_pEdge;
    
};

#endif

#include "CMap.h"
#include <iostream>
#include <vector>
#include "Node.h"
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];//邻接矩阵size乘size
    //邻接矩阵初始化为全0
    //memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int));
    //将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值， 第一个值为指定的内存地址，块的大小由第三个参数指定
    for (int i=0;i<m_iCapacity*m_iCapacity;i++)
    {
        m_pMatrix[i] = 0;
    }

    m_pEdge = new Edge[m_iCapacity - 1];

}

CMap::~CMap()
{
    delete []m_pNodeArray;
    delete[]m_pMatrix;
    delete[]m_pEdge;
}

bool CMap::addNode(Node *pNode)
{
    if (pNode == NULL)
    {
        return false;
    }
    //保存节点数据
    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)
{
    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;
}
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::printMatrix()
{
    //两重循环（i行k列）
    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;
    }
}

//深度优先
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 !=0)//判断有弧连接其他顶点
        {
            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<int> curVec;
    curVec.push_back(nodeIndex);

    breadthFirstTraverseImpl(curVec);

}

void CMap::breadthFirstTraverseImpl(vector<int> preVec)
{
    int value = 0;
    vector<int> curVec;

    //prevec为上一层节点
    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
    {
        breadthFirstTraverseImpl(curVec);
    }

}

//普利姆生成树
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;
    //什么时候停下来，边数等于点数-1时
    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);
                }
            }
        }

        //才可选边集合中找出最小的边
        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 = 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<(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;
}

//克鲁斯卡尔算法生成树
void CMap::kruskalTree()
{
    int value = 0;//用来取权值的

    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!=0)
            {
                Edge edge(i, k, value);
                edgeVec.push_back(edge);


            }
        }
    }

    //第二步：从所有边中取出最小生成树的边
    //1. 找到算法的结束条件（边数等于顶点数-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 <(int)nodeSets.size(); i++)
        {
            nodeAIsInSet = isInSet(nodeSets[i],nodeAIndex);
            if (nodeAIsInSet)
            {
                //保存i的值
                nodeAInSetLabel = i;
            }
        }
        for (int i = 0; i < (int)nodeSets.size(); i++)
        {
            nodeBIsInSet = isInSet(nodeSets[i], nodeBIndex);
            if (nodeBIsInSet)
            {
                //保存i的值
                nodeBInSetLabel = i;
            }
        }
        //5. 根据点所在集合的不同做出不同处理
        if (nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
        {
            vector<int> vec;
            vec.push_back(nodeAIndex);
            vec.push_back(nodeBIndex);

            nodeSets.push_back(vec);
        }

        else if (nodeAInSetLabel == -1 && nodeBInSetLabel !=-1)
        {
            //此时a不在任何一个集合中。而nodeB已经在某一集合中
            //因为nodea&b为一边的两点。所有将a也加入b的集合
            nodeSets[nodeBInSetLabel].push_back(nodeAIndex);
        }
        else if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1)
        {
            //此时b不在任何一个集合中。而nodeA已经在某一集合中
            //因为nodea&b为一边的两点。所有将b也加入a的集合
            nodeSets[nodeAInSetLabel].push_back(nodeBIndex);
        }
        else if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel)
        {
            //两者在两个不同的集合中，将集合合并
            mergeNodeSet(nodeSets[nodeAInSetLabel], nodeSets[nodeBInSetLabel]);

            for (int k = nodeBInSetLabel;k<(int)nodeSets.size()-1;k++)
            {
                //相当于删除了一个节点后面的都向前挪一位
                nodeSets[k] = nodeSets[k + 1];

            }

        }
        else if(nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel == nodeBInSetLabel)
        {
            //两个都不等于-1.相等还在同一个集合中。
            continue;
        }

        m_pEdge[edgeCount] = edgeVec[minEdgeIndex];
        edgeCount++;


        cout << edgeVec[minEdgeIndex].m_iNodeIndexA << "---" << edgeVec[minEdgeIndex].m_iNodeIndexB << "  ";
        cout << edgeVec[minEdgeIndex].m_iWeightValue << endl;
    }
    

}

bool CMap::isInSet(vector<int> nodeSet, int target)
{
    //参数一点的集合。参数二点的索引
    for (int i=0;i<(int)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<(int)nodeSetB.size();i++)
    {
        //合并就是将b的点依次加到a的后面
        nodeSetA.push_back(nodeSetB[i]);
    }
}

main.cpp:

#include "CMap.h"
#include <stdlib.h>
#include "Node.h"
#include <iostream>
using namespace std;

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->kruskalTree();
    system("pause");
    return 0;
}

运行结果：

运行结果
显示全文