数据结构图的遍历实验报告

实验项目名称： 图的遍历

一、实验目的

应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验内容

问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备

计算机，Code::Blocks。 四、实验原理

用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果

#define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include<> #include<> #include<> #include<>

typedef struct ArCell{ int adj;

}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct

{ infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph;

int LocateVex(MGraph *G,char* v) { int c = -1,i;

for(i=0;ivexnum;i++)

if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;}

MGraph * CreatUDN(MGraph *G)d:\ scanf(\ for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) G->arcs[i][j].adj=INFINITY;

printf(\请输入一条边依附的两个顶点和权值:\\n\ for(k=0;karcnum;k++)

{printf(\第%d条边:\\n\ printf(\起始结点:\ scanf(\ printf(\结束结点:\ scanf(\ dj=w;

G->arcs[j][i]=G->arcs[i][j]; }}

return G; }

int FirstAdjVex(MGraph *G,int v) {

int i;

if(v<=0 && vvexnum){ dj!=INFINITY) return i; }

return -1; }

void VisitFunc(MGraph *G,int v) {

printf(\ }

int NextAdjVex(MGraph *G,int v,int w) {

int k;

if(v>=0 && vvexnum && w>=0 && wvexnum)dj!=INFINITY) return k; }

return -1; }

int visited[MAX];

void DFS(MGraph *G,int v)//从第v个顶点出发递归地深度优先遍历图G {

int w;

visited[v]=1;

VisitFunc(G,v);//访问第v个结点

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w]){ DFS(G,w);

printf(\ }

void DFSTraverse(MGraph *G,char *s)//深度优先遍历 {int v,k;

for(v=0;vvexnum;v++) visited[v]=0; k=LocateVex(G,s);

if(k>=0&&kvexnum){ for(v=k;v>=0;v--){ if(!visited[v]) DFS(G,v);}

for(v=k+1;vvexnum;v++) if(!visited[v]) DFS(G,v); } }

typedef struct Qnode {

int vexnum;

struct Qnode *next; }QNode,*QueuePtr; typedef struct {

QueuePtr front; QueuePtr rear; }LinkQueue;

int InitQueue(LinkQueue *Q) {

Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q->front)exit(0); Q->front->next=NULL; return 1; }

void EnQueue(LinkQueue *Q,int a ) {

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(0); p->vexnum=a; p->next=NULL; Q->rear->next=p; Q->rear=p; }

int DeQueue(LinkQueue *Q,int *v) { QueuePtr p;

if(Q->front==Q->rear)

{printf(\结点不存在!\\n\ p=Q->front->next; *v=p->vexnum;

Q->front->next=p->next; if(Q->rear==p) Q->front=Q->rear; return *v; }

int QueueEmpty(LinkQueue *Q) {

if(Q->rear==Q->front) return 0; return 1; }

int Visited[MAX];

void BFSTraverse(MGraph *G,char *str)//广度优先遍历 {int w,u,v,k; LinkQueue Q,q;

for(v=0;vvexnum;v++) Visited[v]=0; InitQueue(&Q);InitQueue(&q); k=LocateVex(G,str); for(v=k;v>=0;v--) if(!Visited[v]) {

Visited[v]=1; VisitFunc(G,v);

EnQueue(&Q,v);//v入队 while(!QueueEmpty(&Q)) {

DeQueue(&Q,&u);//出队

for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!Visited[w]) {

Visited[w]=1;

VisitFunc(G,v); EnQueue(&Q,w); } } }

for(v=k+1;vvexnum;v++) if(!Visited[v]) {

Visited[v]=1; VisitFunc(G,v);

EnQueue(&Q,v);//v入队 while(!QueueEmpty(&Q)) {

DeQueue(&Q,&u);//出队

for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!Visited[w]) {

Visited[w]=1; VisitFunc(G,v); EnQueue(&Q,w); } } } }

void main() {

MGraph *G,b; char v[10]; G=CreatUDN(&b);

printf(\请输入起始结点名称:\ scanf(\

printf(\深度优先遍历:\\n\ DFSTraverse(G,v);

printf(\广度优先遍历:\\n\ BFSTraverse(G,v); getch(); }