#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<vector> #include"Node.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 depthFitstTraverse(int nodeIndex);//深度优先遍历 void breadthFirstTraverse(int nodeIndex);//广度优先遍历 private: bool getValueFormMatrix(int row,int col,int&val);//从矩阵中获取权值 void breadthFirstTraverseImp(vector<int>preVec);//广度优先遍历实现函数 private: int m_iCapacity;//图中最多可以容纳的顶点数 int m_iNodeCount;//已经添加的顶点(节点)个数 Node *m_pNodeArray;//用来存放顶点数组 int *m_PMatrix;//用来存放邻接矩阵 }; #endif #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)); // 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; } } void CMap::depthFitstTraverse(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++) { getValueFormMatrix(nodeIndex,i,value); if(value!=0) { if (m_pNodeArray[i].m_bIsVisited) { continue; } else { depthFitstTraverse(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); breadthFirstTraverseImp(curVec); } void CMap::breadthFirstTraverseImp(vector<int>preVec) { int value=0; vector<int> curVec; for (int j=0;j<(int)preVec.size();j++) { for (int i=0;i<m_iCapacity;i++) { getValueFormMatrix(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::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::setValueToMatrixForDirectedGraph(int row,int col,int val) { if(row<0||row>=m_iCapacity) { return false; } if(col<0||row>=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||row>=m_iCapacity) { return false; } m_PMatrix[row*m_iCapacity+col]=val; m_PMatrix[col*m_iCapacity+row]=val; return true; } bool CMap::getValueFormMatrix(int row,int col,int&val) { if(row<0||row>=m_iCapacity) { return false; } if(col<0||row>=m_iCapacity) { return false; } val=m_PMatrix[row*m_iCapacity+row]; return true; } #include "CMap.h" #include <iostream> using namespace std; /* 图的存储于图的遍历 A / \ B D / \ / \ C F G -- H \ / E */ int main(void) { 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->depthFitstTraverse(0); //pMap->depthFitstTraverse(5); //pMap->depthFitstTraverse(6); cout<<endl; pMap->resetNode(); pMap->breadthFirstTraverse(0); system("pause"); return 0; }