//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));/初始化邻接矩阵
}


bool CMap::addNode(Node* pNode)
{
    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_blsVisited = false;
    }
}
//为边设置权值
bool CMap::setValueToMatrixForDirectedGraph(int row,int col,int val)
{
    m_pMatrix[row*m_iCapacity+col] = val;
    return true;
}

bool CMap::setValueToMatrixForUndirectedGraph(int row,int col,int val)
{//无向图的邻接矩阵是对称的
    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)
{
    val = m_pMatrix[row*m_iCapacity+col];
    return true;
}

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

//深度优先搜索
void CMap::depthFirstTraverse(int nodeIndex)
{
    int value = 0;
    
    cout << m_pNodeArray[nodeIndex].m_cData << " ";
    m_pNodeArray[nodeIndex].m_blsVisited = true;
    
    //通过邻接矩阵判断是否与其他的顶点是否有连接
    for(int i = 0;i < m_iCapacity;i++)
    {
        getValFromMatrix(nodeIndex,i,value);
        if(value != 0)
        {
            if(pNodeArray[i].m_blsVisited)
            {
                continue;
            }
            else{
                depthFirstTraverse(i);
            }
        }
    }
}

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

//CMap.h

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

class CMap{
public:
    CMap(int capacity);//向图中加入顶点
    ~CMap();
    bool addNode(Node* pNode);//重置顶点
    void resetNode();
    bool setValueToMatrixForDirecteGraph(int row,int col,int val = 1);    //为有向图设置邻接矩阵
    bool setValueToMatrixForUndirecteGraph(int row,int col,int val = 1);//为无向图设置邻接矩阵
    
    void printMatrix();//打印邻接矩阵
    
    void depthFirstTraverse(int nodeIndex);//深度优先遍历
    void breadthFirstTraverse(int nodeIndex);// 广度优先遍历
   
private:
    bool getValueFromMatrix(int row,int ol,int &val);//从矩阵中获取权值
    void breadthFirtTraverseImp(vector<int> preVec);//广度优先遍历实现函数
    
private:
    int m_iCapacity;        //图中最多可以容纳的顶点数
    int m_iNodeCount;        //已经添加的顶点个数
    Node *m_pNodeArray;    //存放顶点数组
    int *m_pMatrix;        //存放邻接矩阵
};

#endif

//Node.cpp

#include "Node.h"

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

#ifndef NODE_H
#define NODE_H

class Node
{
   public:
       Node(char data = 0);
       char m_cData;//节点数据
       bool m_blsVisited;//节点访问标志
};
#endif

2. demo.cpp

1. demo.cpp

2. void CMap::breadthFirstTraverseImpl(vector<int> preVec)

2. void CMap::breadthFirstTraverseImpl(vector<int> preVec)

1. CMap::breadthFirstTraverse(int nodeIndex)

4. NODE_CPP

3. NODE_H

2. CMAP_H

1. CMAP_H

1、图的存储结构