#ifndef?NODE_H #define?NODE_H class?Node { public: Node?(char?data?=0);//構(gòu)造函數(shù) char?m_cData;//數(shù)據(jù) bool?m_bIsVisited;//當(dāng)前節(jié)點(diǎn)是否被訪問過 }; #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);//向圖中加入節(jié)點(diǎn) void?resetNode();//重置節(jié)點(diǎn) bool?setValueToMatrixForDirectedGraph(int?row,int?col,int?val=1);//向由向圖設(shè)置鄰接矩陣 bool?setValueToMatrixForUnDirectedGraph(int?row,int?col,int?val=1);//向無向圖設(shè)置鄰接矩陣 void?printMatrix();//打印鄰接矩陣 void?depthFitstTraverse(int?nodeIndex);//深度優(yōu)先遍歷 void?breadthFirstTraverse(int?nodeIndex);//廣度優(yōu)先遍歷 private: bool?getValueFormMatrix(int?row,int?col,int&val);//從矩陣中獲取權(quán)值 void?breadthFirstTraverseImp(vector<int>preVec);//廣度優(yōu)先遍歷實(shí)現(xiàn)函數(shù) private: int?m_iCapacity;//圖中最多可以容納的頂點(diǎn)數(shù) int?m_iNodeCount;//已經(jīng)添加的頂點(diǎn)（節(jié)點(diǎn)）個(gè)數(shù) Node?*m_pNodeArray;//用來存放頂點(diǎn)數(shù)組 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; //通過鄰接矩陣判斷是否與其他的頂點(diǎn)?有連接 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; /* 圖的存儲(chǔ)于圖的遍歷 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; }