#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;
}
1 回答
- 1 回答
- 0 關注
- 1319 瀏覽
添加回答
舉報
0/150
提交
取消