数据结构课程设计——图的广度优先遍历.doc

学 号：

课 程 设 计

题 目
图的广度优先遍历
学 院
计算机科学与技术
专 业
计算机科学与技术
班 级

姓 名

指导教师

2011
年
6
月
25
日

图的广度优先遍历
一、 课程设计的目的
课程设计是对学生的一种全面的综合训练，是与课堂听讲、自学、练习、上机实习相辅相成的教学环节。课程设计的题目通常比平时练习与上机实习复杂得多，也更接近实际。其目的是使学生深化理解和灵活掌握教学内容，并学会如何把书上学到的知识用于解决实际问题，培养软件工作所需的问题分析、软件设计、算法设计和实际动手编程、调试的能力。
这个题目的课程设计是要掌握图的邻接矩阵的存储结构和图的广度优先遍历。

二、 问题分析和任务定义
1、 问题描述：
画出下图所示的无向图的邻接表，使得其中每个无项边结点中第一个顶点号小于第二个顶点号，且每个顶点的各邻接边的链接顺序，，为它所邻接到的顶点序号由小到大的顺序。列出广度优先搜索遍历该图所得顶点序列和边的序列。

1
2
5
3
6
4

2、 问题分析和任务定义
图的邻接表表示：在第i行的单链表中，各结点（称作边结点）分别存放与同一个顶点vi关联的各条边。各条边配有标识dest，指示该边的另一个顶点（终顶点） ；还配有指针link，指向同一链表中的下一条边地边结点（都与顶点vi相关联）。
图的遍历: 图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。

三、 存储结构设计
按无向图的邻接表存储

四、 主要程序设计
1.广度优先遍历的定义
在访问了起始点之后,首先依次访问起始点的各个邻接点,然后依次访问这些顶点中未被访问过的邻接点.依此类推,直到所有被访问到的顶点的邻接点都被访问过为止.
2. 广度优先搜索的过程
a算法基本思想：
首先访问图中某一指定的出发点Vi；
然后依次访问Vi的所有接点Vi1，Vi2…Vit；
再次访问Vi1，Vi2…，Vit的邻接点中未经访问过的顶点，依此类推，直到图中所有顶点均被访问为止。
b具体过程：
从广度优先搜索遍历方法可知，先被访问的顶点的邻接点也被访问，即假设顶点V在W之前被访问，那么顶点V的所有未经访问的邻接点也在顶点W的所有未经访问的邻接点之前被访问。这样可以在广度优先遍历的算法中设置一个队列结构，用以保存已访问过的顶点的序号，访问该顶点的所有未经访问的顶点。
广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样会出现回退的现象。因此它不是个递归的过程。为了实现逐层访问，算法中使用了一个队列以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为了避免重复访问，需要一个辅助函数visitvex[]给被访问过的顶点加标记。

五、 调试过程
1．在求图的第u个顶点，与其相邻的一系列顶点中，第w个顶点的下一个顶点时，若是求最后一个顶点的下一个顶点时，函数进入了死循环。原因是判断条件没有写好，造成了判断值恒为真，因此进入了死循环。修改后，函数正常运行。
2．广度优先遍历图的时候，是从指定的任一顶点开始遍历，当遇到该图为无向非连通图，并不能把该图遍历。
原因是没有写出一个循环体，去尝试遍历其他没有被遍历的顶点。加上这样一个循环体后，便可以遍历任意一种图了，并且还可以在此基础上算出图的两通分量。
3．在输入图信息的时候，若输入非法字符，程序会异常终止。例如程序要求输入一个整型，用户却输入了一个字母，这时候会出现异常。只是程序是否健壮性的一个体现。采用输入流的一些函数，便可以解决这一问题。还有其他一些类似的输入异常，都是采用类似的处理方法。
4．作为一个完整的程序，友好的界面是必须的。因次程序中适当地采用系统中的清屏命令，使得界面更加简洁，明了。
六、 经验与体会

七、 附源程序清单和运行结果
#include<stdio.h>
#define Maxvertex 20
#define maxqueuesize 20
#include<stdlib.h>
int visited[Maxvertex];
typedef struct node //边表结点
{ int adjvex; //邻接点域
char vertex;
struct node *next; //链域
}Edgenode;
typedef struct vnode //顶点表结点
{ char vertex; //顶点域
Edgenode *firstadj; //边表头指针
}Vertexnode;
typedef Vertexnode Adjlist[Maxvertex]; //Adjlist是邻接表类型
typedef struct
{ Adjlist adjlist; //邻接表
int n,e; //图中当前顶点数和边数
}ALGraph;

typedef struct
{
int * data;
int front;
int rear;
}queue;
int initqueue(queue &q)
{
q.data=(int *)malloc(maxqueuesize*sizeof(int));
q.front=q.rear=0;
return 1;
}
int isempty(queue &q)
{ if(q.front==q.rear)

return 1; return 0; }

int isfull(queue &q)
{ if(q.rear==maxqueuesize-1)
return 1;return 0;
}
int enqueue(queue &q,int e)
{ if(isfull(q)) return 0;
q.data[q.rear++]=e;
return 1; }

int dequeue(queue &q)
{ int t;
if(isempty(q)) return 0; // 出队
t=q.data[q.front++];
return t;
}
void creatalgraph(ALGraph &G)
{ int i,j,k;
Edgenode *s;
printf("输入顶点数和边数(n e):");
scanf("%3d%3d",&G.n,&G.e);
for(i=0;i<G.n;i++) //建立顶点表
{ printf("输入第%d个顶点:",i); getchar();
G.adjlist[i].vertex=getchar(); //读入顶点信息
G.adjlist[i].firstadj=NULL; } //边表置为空表
for(k=0;k<G.e;k++) //建立边表
{ printf("输入边的顶点对序号(i j):");
scanf("%d %d",&i,&j); //读入边(Vi,Vj)的顶点对序号
s=(Edgenode *)malloc(sizeof(Edgenode)); //生成边表结点
s->adjvex=j; //邻接点序号为j
s->next=G.adjlist[i].firstadj;
G.adjlist[i].firstadj=s; //将新结点*s插入顶点vi的边表头部
s=(Edgenode *)malloc(sizeof(Edgenode));
s->adjvex=i; //邻接点序号为
s->next=G.adjlist[j].firstadj;
G.adjlist[j].firstadj=s; //将新结点*s插入顶点vj的边表头部
}}

int Locatevex(ALGraph &G, char v1)
{ int i;
for(i=0;i<G.n;i++)
{ if(G.adjlist[i].vertex==v1)
return i; }
return 0; }

void show(ALGraph &G)
{ int i;
Edgenode *p;
printf("图的邻接表表示如下:\n");
for(i=0;i<G.n;i++)
{ printf("[%d,%c]=>",i,G.adjlist[i].vertex);
p=G.adjlist[i].firstadj;
while(p!=NULL)
{ printf("%d->",p->adjvex);
p=p->next; }
printf("^\n");
}}
void visit(ALGraph &G, int i)
{ printf("%3c",G.adjlist[i].vertex); }

void BFS(ALGraph &G,int k)
{ int i,m;
queue Q; Edgenode*p;
initqueue(Q); //初始化队列
for(int j=0;j<G.n;j++) visited[j]=0;
visit(G,k); visited[k]=1;
enqueue(Q,k); //将访问过的结点的序号入队
while(!isempty(Q)) { //队非空时出队
i=dequeue(Q);
p=G.adjlist[i].firstadj; //取vi的边表头指针
while(p) { //依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adjvex]) //若vj未访问过
{ m=p->adjvex;
visit(G,m); visited[m]=1; //访问vj
enqueue(Q,p->adjvex); //将访问过的vj入队
}
p=p->next; //找vi的下一邻接点
}}}

void menu()
{ printf("**************************************\n");
printf(" 图的邻接表表示\n");
printf(" 1.创建图\n");
printf(" 2.图的广度优先搜索\n");
printf(" 3.显示\n");
printf(" 4.退出\n");
printf("*************************************\n");
}

void main()
{ int k,i,j;char x,y;
ALGraph G;
menu();
while(1)
{ printf("\ninput your choice:(1~5)");
scanf("%3d",&k);
switch(k)
{ case 1:
creatalgraph(G); break;
case 2:
printf("input an node start BFS:");
getchar();
scanf("%c",&y); j=Locatevex(G,y);
BFS(G,j); break;
case 3:
show(G); break;
case 4:
exit(0); break;
default:
printf("error"); break;
} } }

本科生课程设计成绩评定表
班级：　姓名：　 学号
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10

2
设计分析合理性
10

3
设计方案正确性、可行性、创造性
20

4
设计结果正确性
40

5
设计报告的规范性
10

6
设计验收
10

总得分/等级

评语：

注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格

　　　　　　　　　　　　　　　　　　　　指导教师签名：
　　　　　　　　　　　　　　　　　　 2011年　月　日