实验四 图的遍历与应用(广度优先遍历)

C语言 版本的数据结构 实验

实验四 图的遍历与应用

一、 实验目的

1．掌握图的含义；

2． 掌握用邻接矩阵和邻接表的方法描述图的存储结构；

3． 理解并掌握深度优先遍历和广度优先遍历的存储结构。

二、 实验要求

1． 认真阅读和掌握本实验的参考程序。

2． 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。

3． 保存程序的运行结果，并结合程序进行分析。

三、 实验内容

以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。

广度优先遍历：

具体实验的详细代码：

#define MaxVerNum 100 /* 最大顶点数为*/

#define MAXSIZE 100

typedef enum {False,True} boolean;

#include "stdio.h"

#include "stdlib.h"

typedef int DataType;

boolean visited[MaxVerNum];

typedef struct /*定義一個隊列*/

{

DataType data[MAXSIZE];

int front,rear;

}SeqQueue,*PSeqQueue;

PSeqQueue Init_SeqQueue() /*隊列初始化*/

{

PSeqQueue Q;

Q=(PSeqQueue)malloc(sizeof(SeqQueue));

if(Q)

{

Q->front=0;

C语言 版本的数据结构 实验

Q->rear=0;

}

return Q;

}

int In_SeqQueue(PSeqQueue Q,DataType x) /*入隊操作*/

{

if((Q->rear+1)%MAXSIZE==Q->front)

{

printf("隊滿");

return -1;

}

else

{

Q->rear=(Q->rear+1)%MAXSIZE;

Q->data[Q->rear]=x;

return 1;

}

}

int Empty_SeqQueue(PSeqQueue Q) /*判斷隊空*/

{

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

return (1);

else

return (0);

}

int Out_SeqQueue(PSeqQueue Q,DataType *x) /*出對操作*/

{

if(Empty_SeqQueue(Q))

{

printf("隊空");

return -1;

}

else

{

Q->front=(Q->front+1)%MAXSIZE;

*x=Q->data[Q->front];

return 1;

}

}

typedef struct node /* 表结点*/

{

int adjvex;/* 邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/

char Info; /*与边(或弧)相关的信息*/

C语言 版本的数据结构 实验

struct node * next; /* 指向下一个邻接点的指针域*/

} EdgeNode;

typedef struct vnode /* 顶点结点*/

{

char vertex; /* 顶点域*/

EdgeNode * firstedge; /* 边表头指针*/

} VertexNode;

typedef struct

{

VertexNode adjlist[MaxVerNum]; /* 邻接表*/

int n,e; /* 顶点数和边数*/

} ALGraph; /* ALGraph是以邻接表方式存储的图类型*/

void Visit(DataType w)

{

printf ("%d",w);

}

//建立一个无向图的邻接表存储的算法如下：

void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/

{

int i,j,k;

/*int N,E;*/

EdgeNode *p;

printf("请输入顶点数和边数：");

scanf("%d %d",&G->n,&G->e);

printf("n=%d,e=%d\n\n",G->n,G->e);

getchar();

for(i=0;i<G->n;i++) /* 建立有n个顶点的顶点表*/

{

printf("请输入第%d个顶点字符信息(共%d个)：",i+1,G->n);

scanf("%c",&(G->adjlist[i].vertex)); /* 读入顶点信息*/

getchar();

G->adjlist[i].firstedge=NULL; /* 顶点的边表头指针设为空*/

}

for(k=0;k<2*G->e;k++) /* 建立边表*/

{

printf("请输入边<Vi,Vj>对应的顶点序号(共%d个)：",2*G->e);

scanf("%d %d",&i,&j);/* 读入边<Vi,Vj>的顶点对应序号*/

p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生成新边表结点p

p->adjvex=j; /* 邻接点序号为j */

p->next=G->adjlist[i].firstedge;/* 将结点p插入到顶点Vi的链表头部*/

G->adjlist[i].firstedge=p;

}

C语言 版本的数据结构 实验

printf("\n图已成功创建!对应的邻接表如下：\n");

for(i=0;i<G->n;i++)

{

p=G->adjlist[i].firstedge;

printf("%c->",G->adjlist[i].vertex);

while(p!=NULL)

{

printf("[ %c ]",G->adjlist[p->adjvex].vertex);

p=p->next;

}

printf("\n");

}

printf("\n");

} /*CreateALGraph*/

int FirstAdjVertex(ALGraph *g,int v)//找图g中与顶点v相邻的第一个顶点

{

if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex;

else return 0;

}

int NextAdjVertex(ALGraph *g ,int vi,int vj )//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点

{

EdgeNode *p;

p=g->adjlist[vi].firstedge;

while( p!=NULL && p->adjvex!=vj) p=p->next;

if(p!=NULL && p->next!=NULL) return p->next->adjvex;

else return 0;

}

void BFS(ALGraph *G,int v)

{

/*從v出發按廣度優先遍歷圖G；使用輔助隊列Q和訪問標誌數組visited*/

EdgeNode *p;

int u,w;

PSeqQueue Q; /*定義一個隊列*/

Q=Init_SeqQueue(); /*置空的隊列Q*/

Visit(v); /*訪問v，注意Visit函數和visited數組的區別*/ visited[v]=True; /*把訪問標誌置True*/

In_SeqQueue(Q,v); /*v入隊列*/

while(!Empty_SeqQueue(Q))

{

Out_SeqQueue(Q,&u); /*出隊列*/

C语言 版本的数据结构 实验

for(p=G->adjlist[u].firstedge;p;p=p->next)

{

w=p->adjvex;

if(!visited[w])

{

Visit(w);

visited[w]=True;

In_SeqQueue(Q,w); /*u的尚未訪問的鄰接頂點w入隊列Q*/ }

}

}

} /*BFS*/

void BFStraverse(ALGraph G)

{

int v;

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

visited[v]=False;

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

if(!visited[v])BFS(&G,v);

}

void main()

{

int v;

ALGraph G;

Crea …… 此处隐藏：1708字，全部文档内容请下载后查看。喜欢就下载吧 ……