数据结构——图(Graph)及其C++代码实现

图的基本概念

线性表和树两类数据结构,线性表中的元素是“一对一”的关系,树中的元素是“一对多”的关系,本章所述的图结构中的元素则是“多对多”的关系。图(Graph)是一种复杂的非线性结构,在图结构中,每个元素都可以有零个或多个前驱,也可以有零个或多个后继,也就是说,元素之间的关系是任意的。

图分为有向图和无向图。无向图中的一个边相当于有向图中的双向弧,如V1和V4之间的两条弧。

在有向图中,每个节点叫做顶点,每条带箭头的边叫做弧。一个顶点的入度等于指向它的箭头书,出度等于该节点射出的箭头数。

graph

无向图中有边连结的相邻的两个顶点叫做邻接点。

graph

无向图中,任意两个顶点都可以连通的图叫做连通图,包括间接的或直接的连通,如下图:

graph

无向图中,任意两个顶点之间都有边连结的图叫完全图,边数和顶点数n的关系如下:

graph

具有最少边数的可以使各个顶点连通的图叫做生成树,边数和顶点数n的关系如下:

graph


图的存储方法

图的存储方法主要分为邻接矩阵(有向图和无向图)、邻接表(有向图)、十字链表(有向图)、邻接多重表(无向图)

1.邻接矩阵——数组存储

有向图中弧的权值是这条弧的数据,比如两地之间的距离等

graph

顶点表示为顶点索引和顶点数据。

graph

在有向图中,下图矩阵中存储的是两两顶点之间有没有边,有记为1,无则为0

graph

无向图中,由于没有方向,矩阵的主对角线两边是对称的,往往为了节省空间而只存储一半。

graph

代码结构:

graph


2.邻接表——链接存储

graph

下图表示的是顶点以及其对应的弧链表(即弧是存储在链表结构中的,每个顶点对应一个链表)。注意链表最后要指向NULL。顶点后面的括号内为该顶点的索引值

graph

代码的结构

graph


3.十字链表

graph

代码的结构

graph

4.邻接多重表

graph

代码的结构

graph


图的遍历

图的遍历分为深度优先搜索和广度优先搜索。下图为例

graph

深度优先搜索类似于树的前序遍历,分支为优先。

graph

广度优先搜索可以理解为一层一从上到下一层一层的搜索,即遍历处在同一层的结点,然后再到下一层,而不是完成一个分支的所有节点再到下一个分支。

graph


基于邻接矩阵的存储的图的遍历的代码实现。代码共两个类,Node和CMap

// Node.h
#ifndef C_EX_NODE_H
#define C_EX_NODE_H
class Node 
{
public:
    Node(char data = 0); // data 为当前node顶点的值,不是索引
    char m_cData;
    bool m_bIsVisited; // 记录当前顶点是否被访问过
};
#endif //C_EX_NODE_H

// Node.cpp

#include "Node.h"

Node::Node(char data):m_cData(data)
{
    m_bIsVisited = false;
}
// CMap.h

#ifndef C_EX_CMAP_H
#define C_EX_CMAP_H

#include <vector>
#include "Node.h"

using namespace std;

class CMap {
public:
    CMap(int capacity);
    ~CMap();
    bool addNode(Node* pNode); // 向图中加入顶点
    void resetNode(); // 重置顶点,即将所有顶点都设置为没有访问过, a.k.a bIsVisited = false
    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 breadthFirstTraverseImpl(vector preVec);

private:
    int m_iCapacity; // 图中最多可容纳的顶点数
    int m_iNodeCount; // 已经添加的顶点个数
    Node* m_pNodeArray; // 用于存放顶点的数组,存放的是指针
    int* m_pMatrix; // 用来存放邻接矩阵
    bool getValueFromMatrix(int row, int col, int& val);
};

#endif //C_EX_CMAP_H
// CMap.cpp

#include "CMap.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)); // 矩阵的初始化,都为零
}

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_cData赋值
    m_iNodeCount++;
    return true;
}

void CMap::resetNode()
{
    for(int i = 0; i m_iCapacity || 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 || col < 0 || row > m_iCapacity || 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 j = 0; j < m_iCapacity; j++)
        {
            cout << m_pMatrix[i * m_iCapacity + j] << " ";
        }
        cout << endl;
    }
}

bool CMap::getValueFromMatrix(int row, int col, int &val)
{
    if(row < 0 || col < 0 || row > m_iCapacity || col > m_iCapacity)
    {
        return false;
    }
    val = m_pMatrix[row * m_iCapacity + col]; // 由于传入的是reference,所以val改变了,外面的value值也会改变

    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 curVec; // 把顶点的索引存入到数组中
    curVec.push_back(nodeIndex);
    breadthFirstTraverseImpl(curVec);
}

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

    for(int j = 0; j < preVec.size(); j++)
    {
        for(int i = 0; i < m_iCapacity; i++)
        {
            getValueFromMatrix(preVec[j], i, value);
            if(value == 1)
            {
                if(m_pNodeArray[i].m_bIsVisited)
                {
                    continue;
                }
                else
                {
                    cout << m_pNodeArray[i].m_cData << " ";
                    m_pNodeArray[i].m_bIsVisited = true;
                    curVec.push_back(i);
                }
            }
            else
            {
                continue;
            }
        }
    }
    if(curVec.empty())
    {
        return;
    }
    else
    {
        breadthFirstTraverseImpl(curVec);
    }
}
// main.cpp

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

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

    delete pNodeA; //因为在CMap中已经定义了Node的位置,所以可以删掉,释放这里的内存
    delete pNodeB;
    delete pNodeC;
    delete pNodeD;
    delete pNodeE;
    delete pNodeF;
    delete pNodeG;
    delete pNodeH;

    pMap->setValueToMatrixForUndirectedGraph(0,1); // 第三个参数有默认值为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);
    pMap->resetNode();
    cout << endl;

    pMap->breadthFirstTraverse(0);
    pMap->resetNode();

    return 0;
}

登录注册后参与评论