图的深度和广度优先遍历

C语言

数据结构实验报告

题目：图的深度和广度优先遍历

班级： 计算084班 姓名：

段新强

学号：指导教师： 完成日期： 2010 年 5月 26日

C语言

青 岛 理 工 大 学

课程实验报告

C语言

2. 3.

输入顶点数目 num; i++,输入结点 L->vexs[i]直到 L->num;

3) 输出图 L 的各顶点； 4) 深度优先遍历图 g 中能访问的各个顶点 1. 2. 3.

输入起点的下标 qidian; 标志数组初始化 mark[v]=0; for(v=qidian;v<g.num+qidian;v++) //

{ v1=v%g.num; if(mark[v1]==0) DFS(g,v1,mark); //从第 v1 个点出发深度优先遍历图 g 中能访问 的各个顶点(算法描述里的流程图很详细) } 5) 广度优先周游图 g 中能访问的各个顶点。 1. 构造空队列； 2. 入队 a[0]; 3. a[0]出队，a[0]的邻接点入队，遍历 a[0]; 4. 队首出队，重复 3 直到队列为空； 5. 判断是否全遍历完了； 6. 输出广度优先遍历序列。

C语言

算 法 描 述 及 实 验 步 骤

开始

访问V0,置标志

求V0邻接点 点

N 有邻接点w

Y

结束

Y W访问过

N 求下一邻接点

w V0

DFS

C语言

开始

标志数组初始化

Vi=1

Vi访问过

N

DFS Y

Vi=Vi+1

Vi==Vexnums N Y 结束

调 试 过 程 及 实 验 结 果

总 这次实验完成得很快。不是因为程序比较简单，而是课件上有大部分的程 结 序，再到网上淘一份模板，凑凑就出来了。5

C语言

#include <stdio.h> 附 typedef int datatype; 录 #define maxsize 1024 # define n 100 typedef char VEXTYPE; typedef float ADJTYPE; typedef struct { VEXTYPE vexs[n]; ADJTYPE arcs[n][n]; int num ; }GRAPH;//邻接矩阵数据类型 typedef int DATATYPE; typedef struct { DATATYPE data[maxsize]; int front,rear; }SEQQUEUE;//队列数据类型 void GraphInit(GRAPH *L)//置空图 { L->num=0; } int GraphVexs(GRAPH *L)/

/求结点数 { return(L->num); } void GraphCreate(GRAPH *L)//创建图 { int i; GraphInit(L); printf("请输入顶点数目："); scanf("%d",&L->num); printf("请输入各顶点的信息(单个符号) :\n"); for(i=0;i<L->num;i++) { fflush(stdin); scanf("%c",&L->vexs[i]); } printf("图已经创建完毕！"); } void GraphOut(GRAPH { L)//图的输出

C语言

int i; printf("\n 图的顶点数目为：%d",L.num); printf("\n 图的各顶点的信息为：\n"); for(i=0;i<L.num;i++) printf("%c ",L.vexs[i]); } void DFS(GRAPH g,int qidian,int mark[])//从第 qidian 个点出发深度优先遍 历图 g 中能访问的各个顶点 { int v1; mark[qidian]=1; printf("%c ",g.vexs[qidian]); for(v1=0;v1<g.num;v1++) { if(g.arcs[qidian][v1]!=0&&mark[v1]==0) DFS(g,v1,mark); } } void GraphDFS(GRAPH g)//深度优先遍历图 g 中能访问的各个顶点 { int qidian,v,v1,mark[maxsize]; printf("\n 深度周游："); printf("\n 请输入起点的下标："); scanf("%d",&qidian); for(v=0;v<g.num;v++) { mark[v]=0; } for(v=qidian;v<g.num+qidian;v++) { v1=v%g.num; if(mark[v1]==0) DFS(g,v1,mark); } } void QueueInit(SEQQUEUE *sq)//建立空队列 { sq->front=0; sq->rear=0; } int QueueIsEmpty(SEQQUEUE sq)//判断队列是否为空 { if (sq.rear==sq.front) return(1);7

C语言

else

return(0);

} int QueueFront(SEQQUEUE sq,DATATYPE *e)//保存队头元素 { if (QueueIsEmpty(sq)) { printf("queue is empty!\n");return 0;} else { *e=sq.data[(sq.front)]; return 1;} } int QueueIn (SEQQUEUE *sq,DATATYPE x)//把元素 x 入队尾 { if(sq->front==(sq->rear+1)%maxsize) { printf("queue is full!\n"); return 0; } else { sq->data[sq->rear]=x; sq->rear=(sq->rear+1)%maxsize; return(1); } } int QueueOut(SEQQUEUE *sq)//删除队首元素 { if(QueueIsEmpty(*sq)) { printf("queue is empty!\n"); return 0; } else { sq->front=(sq->front+1)%maxsize; return 1; } } void BFS(GRAPH g,int v,int mark[])//从 v 出发广度优先周游图 g 中能访问的 各个顶点 { int v1,v2; SEQQUEUE q; QueueInit(&q); QueueIn(&q,v); mark[v]=1;8

C语言

printf("%c ",g.vexs[v]); while(QueueIsEmpty(q)==0) { QueueFront(q,&v1); QueueOut(&q); for(v2=0;v2<g.num;v2++) { if(g.arcs[v1][v2]!=0&&mark[v2]==0) { QueueIn(&q,v2); mark[v2]=1; printf("%c ",g.vexs[v2]); } } } } void GraphBFS(GRAPH g)//深度优先周游图 g 中能访问的各个顶点 { int qidian,v,v1,mark[maxsize]; printf("\n 广度周游："); printf("\n 请输入起点的下标："); scanf("%d",&qidian); for(v=0;v<g.num;v++) { mark[v]=0; } for(v=qidian;v<g.num+qidian;v++) { v1=v%g.num; if(mark[v1]==0) BFS(g,v1,mark); } } void main()//主函数 { GRAPH tu; GraphCreate(&tu); GraphOut(tu); GraphDFS(tu); GraphBFS(tu); printf("\n"); }