C++图的遍历算法

#include
#define UNVISITED 0
#define VISITED 1

class AdjMatrixUndirGraph
{
public:
int vexNum, edgeNum; // 顶点个数和边数
int **Matrix; // 邻接矩阵
char *elems; // 顶点数据
bool *tag;

AdjMatrixUndirGraph(char es[], int vertexNum);
int FirstAdjVex(int v) ; // 返回顶点v的第一个邻接点
int NextAdjVex(int v1, int v2);// 返回顶点v1的相对于v2的下一个邻接点
void Display();
void BFS(int v);
void DFS(int v);
};
AdjMatrixUndirGraph::AdjMatrixUndirGraph(char es[], int vertexNum)
{
vexNum = vertexNum;
edgeNum = 0;
elems = new char[vexNum];
int u, v;
for(v = 0; v < vexNum; v++)
{
elems[v] = es[v];
}

tag = new bool[vexNum]; // 生成标志数组
for(v = 0; v < vexNum; v++)
{ // 初始化标志数组
tag[v] = UNVISITED;
}

Matrix = (int **)new int *[vexNum];// 生成邻接矩阵
for (v = 0; v < vexNum; v++)
{ // 生成邻接矩阵的行
Matrix[v] = new int[vexNum];
}

for (u = 0; u < vexNum; u++)
{
for (v = 0; v < vexNum; v++)
{ // 为邻接矩阵元素赋值
Matrix[u][v] = 0;
}
}
}
int AdjMatrixUndirGraph::FirstAdjVex(int v)
// 操作结果：返回顶点v的第1个邻接点
{
if (v < 0 || v >= vexNum)
{
cout<<"v不合法!";
return -1;
}
for (int cur = 0; cur < vexNum; cur++)
{ // 查找邻接点
if (Matrix[v][cur] != 0) return cur;
}
return -1; // 返回-1表示无邻接点
}

int AdjMatrixUndirGraph::NextAdjVex(int v1, int v2)
// 操作结果：返回顶点v1的相对于v2的下1个邻接点
{
if (v1 < 0 || v1 >= vexNum)
{
cout<<"v1不合法!";
return -1;
}
if (v2 < 0 || v2 >= vexNum)
{
cout<<"v1不合法!";
return -1;
}
if (v1 == v2)
{
cout<<"v1不能等于v2!";
return -1;
}
for (int cur = v2 + 1; cur < vexNum; cur++)
{ // 查找邻接点
if (Matrix[v1][cur] != 0) return cur;
}
return -1; // 返回-1表示无邻接点
}

void AdjMatrixUndirGraph::Display()
{
int i,j;
for(i=0;i{
for(j=0;jcout<cout<}
}
void AdjMatrixUndirGraph::BFS(int v)
{
tag[v]=VISITED; // 作访问标志
cout<char queue[50]; // 定义队列
int front=0,rear=0;
queue[rear++]=v; // v入队
while(front!=rear)
{ // 队列q非空, 进行循环
int u, w; // 临时顶点
u=queue[front];
front++; // 出队
for (w = FirstAdjVex(u); w >= 0; w = NextAdjVex(u, w))
{
if(tag[w]==UNVISITED)
{
tag[w]=VISITED;
cout<queue[rear++]=w;
}

}
}
for(int i = 0; i < vexNum; i++)
{
tag[i] = UNVISITED;
}
}
void AdjMatrixUndirGraph::DFS(int v)
{
tag[v]=VISITED;
cout<for(int w=FirstAdjVex(v);w>=0;w=NextAdjVex(v,w))
{
if(tag[w]==UNVISITED)
{
AdjMatrixUndirGraph::DFS(w);
}
}
}
void main()
{

char vexs[] = {'A', 'B', 'C', 'D','E','F','G','H','I','J'};
int n,t,i,x,y;
cout<<"请输入无向图的顶点个数：";
cin>>n;
AdjMatrixUndirGraph g(vexs, n);

cout<<"请输入边的总条数";
cin>>t;
cout<<"请依次输入边，如0 1表示a和b之间有边："<for (i = 1; i <=t; i++)
{
cin>>x>>y;
g.Matrix[x][y]= g.Matrix[y][x]= 1;
}
cout << "原无向图:" << endl;
g.Display();
cout << endl;

cout << "广度遍历序列为:" << endl;
g.BFS(0);
cout<cout << "深度遍历序列为:" << endl;
g.DFS(0);
}