图的遍历

1．需求分析

【实验目的】

很多涉及图上操作的算法都是以图的遍历操作为基础的，通过这个实验的算法设计，可以巩固所学的有关图的基本知识。

【基本要求】

以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

2．算法设计

1）为了实现上述程序功能，需要定义单链表的抽象数据类型：

定义边结点 ArcNode

数据成员 int adjvex;

struct ArcNode *nextarc;

定义顶点信息 VNode

数据成员 VertexType data;

ArcNode *firstarc;

定义无向图 typedef struct

数据成员 AdjList vertices;

int vexnum,arcnum;

定义链表 typedef struct LNode

数据成员 ElemType data;

struct LNode *next;

定义头结点 typedef struct QNode

数据成员 QElemType data;

struct QNode *next;

定义队列 typedef struct

数据成员 QueuePtr front;

QueuePtr rear;

2）本程序用到的主要函数：

InitQueue(LinkQueue &Q) //初始化队

EnQueue(LinkQueue &Q,QElemType e) //入队

DeQueue(LinkQueue &Q,QElemType &e) //出队

LocateVex(ALGraph G,char v) //确定v在G中的位置

CreateDG(ALGraph &G) //创建无向连通图的邻接表结构

FirstAdjvex(ALGraph G,int v) //返回G中顶点v的第一个邻接点

NextAdjVex(ALGraph G,int v,int w) //返回G中顶点v相对于w的下一个邻接点

BFSTraverse(ALGraph G) //进行深度优先遍历

DFS(ALGraph G,int v,int *visited)

DFSTraverse(ALGraph G) //进行广度优先遍历3．调试分析

刚开始输入的是abcdef可是遍历出来的是123456的数字，后来将入前的出输改写成G.vertices[w].data形式就可以了。

4．经验收获和体会

每次都要写这个，我都不知写什么好了呵呵，嗯总体来说还是那句话程序要自已编出来的才叫好。无论编得怎么样总会学到东西的，编写的同时也可以复习以前的知识这样很好。

5．测试数据及结果

6．附录

#include"iostream.h"

#include"stdlib.h"

typedef char VertexType;

typedef int QElemType;

typedef int ElemType;

typedef int Status;

#define MAX 20

#define ok 1

bool visit[MAX];

typedef struct ArcNode //定义边结点

{

int adjvex;

struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode //定义顶点信息

{

VertexType data;

ArcNode *firstarc;

}VNode,AdjList[MAX];

typedef struct //定义无向图

{

AdjList vertices;

int vexnum,arcnum;

}ALGraph;

typedef struct LNode //定义链表

{

ElemType data;

struct LNode *next;

}LNode,*LinkList;

typedef struct QNode //定义头结点

{

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct //定义队列

{

QueuePtr front;

QueuePtr rear;

}LinkQueue;

Status InitQueue(LinkQueue &Q) //初始化队

{

Q.front=new QNode;

if(!Q.front)exit(-

1);

Q.front->next=NULL;

Q.rear=Q.front;

return ok;

}

Status EnQueue(LinkQueue &Q,QElemType e) //入队

{

QueuePtr p;

p=new QNode;

if(!p)exit(-

1);

p->data=e;

p->next=NULL;

Q.rear->next=p;

Q.rear=p;

return ok;

}

Status DeQueue(LinkQueue &Q,QElemType &e) //出队

{

if(Q.front==Q.rear)return false;

QueuePtr p;

p=Q.front->next;

Q.front->next=p->next;

e=p->data;

if(Q.rear==p)Q.rear=Q.front;

delete p;

return ok;

}

int LocateVex(ALGraph G,char v) //确定v在G中的位置

{

for(int i=0;i<G.vexnum;i++)

if(G.vertices[i].data==v)

return i;

if(i==G.vexnum)

{

cout<<"你的输入有错请重新输入"<<endl;

return -1;

}

return 0;

}

void CreateDG(ALGraph &G) //创建无向连通图的邻接表结构

{

cout<<"请输入图的结点数:"<<endl;

cin>>G.vexnum;

cout<<"请输入图的边数:"<<endl;

cin>>G.arcnum;

for(int i=0;i<G.vexnum;i++) //构造表头向量

{

cout<<"请输入第"<<i+1<<"个结点的信息"<<endl;

cin>>G.vertices[i].data;

G.vertices[i].firstarc=NULL; //初始化头结点

} for(int k=0;k<G.arcnum;k++) //输入各边并构造邻接表

{

cout<<"请输入第"<<k+1<<"条边所对应的的两个结点"<<endl;

e: int s=LocateVex(G,v

1); //确定v1在G中的位置

int t=LocateVex(G,v

2); //确定v2在G中的位置

if(s<0||t<0)

goto e;

ArcNode *p=new ArcNode;

p->adjvex=t;

ArcNode *q=G.vertices[s].firstarc; //采用头插法插入链表

G.vertices[s].firstarc=p;

p->nextarc=q; //因为是无向图，每条边对应两个结点

s=LocateVex(G,v

2);

t=LocateVex(G,v

1);

p=new ArcNode;

p->adjvex=t;

q=G.vertices[s].firstarc;

G.vertices[s].firstarc=p;

p->nextarc=q;

}

}

void BFSTraverse(ALGraph G) //进行广度优先遍历

{

int v,w,u;

int visited[MAX];

LinkQueue Q;

for(v=0;v<G.vexnum;++v)

visited[v]=0;

InitQueue(Q);

for(v=0;v<G.vexnum;++v)

if(visited[v]==0)

{

visited[v]=1;

cout<<G.vertices[v].data<<" ";

EnQueue(Q,v);

while(!(Q.rear==Q.front))

{

DeQueue(Q,u);

for(w=G.vertices[u].data;

G.vertices[u].firstarc!=NULL;

w=G.vertices[u].firstarc->adjvex,

G.vertices[u].firstarc=G.vertices[u].firstarc->nextarc)

if(visited[w]==0)

{

visited[w]=1;

cout<<G.vertices[w].data<<" ";

EnQueue(Q,w);

}

}

}

}

void DFS(ALGraph G,int v,int *visited)

{

int w;

visited[v]=1;

cout<<G.vertices[v].data<<" ";

for(w=G.vertices[v].data;

G.vertices[v].firstarc!=NULL;

w=G.vertices[v].firstarc->adjvex,

G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc)

if(visited[w]==0)

DFS(G,w,visited);

}

void DFSTraverse(ALGraph G) //进行深度优先遍历

{

int v;

int visited[MAX];

for(v=0;v<G.vexnum;++v)

visited[v]=0;

for(v=0;v<G.vexnum;++v)

if(visited[v]==0)

DFS(G,v,visited);

}

int main()//主函数

{

ALGraph G;

CreateDG(G);

cout<<"深度优先遍历序列:";

DFSTraverse(G);

cout<<endl;

cout<<"广度优先遍历序列：";

BFSTraverse(G);

cout<<endl;

return 0;