頭疼??？遍歷只能打印第一個(gè)字母！求好心人給看下
#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)是否被訪問(wèn)過(guò)
};
#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);//向無(wú)向圖設(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;//用來(lái)存放頂點(diǎn)數(shù)組
int *m_PMatrix;//用來(lái)存放鄰接矩陣
};
#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;
//通過(guò)鄰接矩陣判斷是否與其他的頂點(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;
}
2018-01-10
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;
}
找到了 ?這個(gè)函數(shù)?