1、 课课 程程 设设 计计 题题 目目 图的广度优先遍历图的广度优先遍历 学学 院院 计算机科学与技术计算机科学与技术 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 计算机计算机 0901 班班 姓姓 名名 指导教师指导教师 2011 年 6 月 30 日 2 课程设计任务书课程设计任务书 题题 目目: : 图的广度优先遍历 初始条件：初始条件： （1）采用邻接表作为存储结构； （2）指定任一顶点作为出发点进行广度优先遍历； （3）测试用例见严蔚敏数据结构习题集(C 语言版)p47 题 7.3 图 要求完成的主要任务要求完成的主要任务: : （包括课程设计工作量及其技术要求， 以及说
2、明书撰写等具体要求） 课程设计报告按学校规定格式用 A4 纸打印（书写） ，并应包含如下内容： 1. 问题描述 简述题目要解决的问题是什么。 2. 设计 存储结构设计、主要算法设计（用类 C/C+语言或用框图描述） 、测试用例设计； 3. 调试报告 调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。 4. 经验和体会（包括对算法改进的设想） 5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这 些测试数据和运行输出。 说明：说明： 1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为 0 分。 2. 凡凡拷贝拷贝往年往年任务书任务
3、书或课程设计充数或课程设计充数者者，成绩成绩一律一律无效无效，以，以 0 0 分记分记。 时间安排：时间安排： 1、第 19 周完成。 2、6 月 30 日下午-7 月 1 日在实验中心检查程序、交课程设计报告、源程序（U 盘） 。 指导教师签名：指导教师签名： 年年 月月 日日 系主任（或责任教师）签名：系主任（或责任教师）签名： 年年 月月 日日 3 图的广度优先遍历图的广度优先遍历 1 1、 课程设计的目的课程设计的目的 课程设计是对学生的一种全面的综合训练，是与课堂听讲、自学、练习、上机实习相 辅相成的教学环节。 课程设计的题目通常比平时练习与上机实习复杂得多， 也更接近实际。 其目的
4、是使学生深化理解和灵活掌握教学内容，并学会如何把书上学到的知识用于解决实 际问题，培养软件工作所需的问题分析、软件设计、算法设计和实际动手编程、调试的能 力。 这个题目的课程设计是要掌握图的邻接矩阵的存储结构和图的广度优先遍历。 2 2、 问题分析和任务定义问题分析和任务定义 2.1 问题描述： 画出下图所示的无向图的邻接表，使得其中每个无项边结点中第一个顶点号小于第二 个顶点号，且每个顶点的各邻接边的链接顺序， ，为它所邻接到的顶点序号由小到大的顺 序。列出广度优先搜索遍历该图所得顶点序列和边的序列。 2.2 问题分析和任务定义 图的邻接表表示：在第 i 行的单链表中，各结点（称作边结点）分别存放与同一个顶 点 vi 关联的各条边。各条边配有标识 dest，指示该边的另一个顶点（终顶点） ；还配有 1 5 2 4 6 3 4 指针 link，指向同一链表中的下一条边地边结点（都与顶点 v
