数据结构图的建立和遍历

1 课程名称 课程名称 数据结构 开课实验室 开课实验室 计算中心 204 室 20112011 年年 1010 月月 日日 年级 专业 班年级 专业 班学号学号姓名姓名成绩成绩 实验项目名称实验项目名称图的建立和遍历指导教师指导教师 教师教师 评语评语 教师签名 教师签名 年年 月月 日日 1 1 实验内容和目的实验内容和目的 目的 目的 撑握图的建立和遍历 熟悉图的建立和输出 还有两种遍历 深度和广度优先 遍历 内容 内容 编出图的程序 能够体图的性质 内容和算法 二 二 上机实验环境上机实验环境 计算中心 204 操作系统 Microsoft Visual C 软件平台 Microsoft Visual C 三 上机操作方法 步骤三 上机操作方法 步骤 打开计算机进入 WindowsXP 在桌面建立自己的工作目录 进入 Microsoft Visual C 6 0 文件 新建 文件 C Source File 位置 命名 输入源程序 编译 组建 运行 四 设计分析 四 设计分析 图是一种复杂的非线性结构 图结构在人工智能 计算机科学等领域有着广泛的运用 学好它就得了解结点之间的关系是线性关系 除开始结点和终端结点外 每个结点只有一 个直接前趋和直接后继 在图结构中 对结点的前趋和后继个数都不加限制的 即结点之 间的关系是任意的 include include 2 define maxnode 30 define null 0 define m 20 typedef struct st arc int adjvex int weight struct st arc nextarc arcnode typedef struct int vertex struct st arc firstarc vernode typedef vernode adjlist maxnode int queue maxnode void dfs adjlist g int k int visited 从顶点 K 出发深度优先搜索 arcnode p int w visited k 1 printf d g k vertex p g k firstarc while p null 3 w p adjvex if visited w 0 dfs g w visited p p nextarc void bfs adjlist g int k int visited 从顶点 K 出发广度优先搜索 int front 0 rear 1 w arcnode p visited k 1 访问初始顶点 printf d k queue rear k 初始顶点入队列 while front rear front front 1 m w queue front 按访问次序依次出队列 p g w firstarc while p null if visited p adjvex 0 visited p adjvex 1 printf d p adjvex rear rear 1 m queue rear p adjvex 4 p p nextarc void trave bfs adjlist g int n 数组 visited 标志图中的顶点是否已被访问 int i visited maxnode for i 1 i n i visited i 0 for i 1 i n i if visited i 0 bfs g i visited void trave dfs adjlist g int n 数组 visited 标志图中的顶点是否已被访问 int i visited maxnode for i 1 i n i visited i 0 for i 1 i n i if visited i 0 dfs g i visited 5 void print adjlist g int n arcnode q int i printf 输出的是所建立无向图的邻接表结构 n for i 1 i g i vertex q g i firstarc while q null printf d q adjvex printf d q weight q q nextarc printf Null printf n void main arcnode p q adjlist g 6 int i j n k w e printf 请输入建立的无向图所包含的顶点总个数和总边数 用逗号隔开 scanf d d for k 1 k n k getchar printf t 输入每个顶点的信息 必须输入整数值 k scanf d g k firstarc null 对顺序存储部分初始化 for k 1 kadjvex j q weight w q nextarc g i firstarc g i firstarc q p arcnode malloc sizeof arcnode p adjvex i p weight w p nextarc g j firstarc g j firstarc p print g n 7 printf n printf 输出深度优先搜索遍历 trave dfs g n printf n printf 输出广度优先搜索遍历 trave bfs g n printf n 五