《课程名称 数据结构14》由会员分享，可在线阅读，更多相关《课程名称 数据结构14（6页珍藏版）》请在金锄头文库上搜索。
1、课程名称 数据结构 14 授课题目图 有向图授课日期2003 年 11 月 26 日授课班级生物医学工程授课时数4授课方式理论课授 课 重 点 、 难 点1.有向图及其表示方法：邻楼表，邻楼矩阵 2.图的遍历，与树的遍历及线性 3.掌握先深搜索与先广搜索授 课 内 容 、 教 具 与 时 间 分 配授 课 内 容 、 教 具 与 时 间 分 配第五章 图 5 1.1 有向图及其表示方法 (存储方法) (P127)图 5.1 有向图顶点的集合 V= 1,2,3,4,顶点表示对象弧的集合 E=（1，2） ， （1，3） ， （2，4） ， （3，2） ， （4，3） 对象之间的关系图 G = （V
2、，E）有序对、相邻： 一条弧： vw ， v 为弧的尾，w 为弧的头，是顶点 v 和 w 的有序对，w 和 v 是相邻 的。 ，故而称为有向图。路经：顶点序列路径长途： 弧的条数简单路径： 简单环路：标号有向图：图 5.2，顶点、弧附加信息无向图：若图中的边是顶点的无序对，则称此图为无向图。无向图中顶点间的联系不用表示。512 邻接矩阵 P127一、 邻接矩阵是有向图的一种表示方法（存储方法） ，是二维数组方法。二、 图 G =（V，E） ， V= 1，2，3 n用邻接矩阵表示有向图：aryi j行 列 有向图 标号有向图i j 1 a无 0 空格（布尔矩阵）0,1 元素 10对应图 5.1
3、对应图 5.2 三、 函数adjmatrix 建立图的邻接矩阵，返回图的顶点个数。 9 输入方法：v1 v2 weight = 1 1 0 = 1 2 10 = 0 0 0 输入结束四、 函数prmatrix打印邻接矩阵。5.1.3 邻接表一、 图的另一种表示方法(存储方法)，是链接方法二、 对图中的任一顶点，由此顶点出发的全部相邻顶点用一个向前链表表示，向前链表的前后次序不影响图顶点之间的相互联系。向前链表的表头结点，构成一个数组 list，表头结点有信息场和链场组成，信息场另作它用。图 5.3 p128。1 2 3两者等价1 3 2 三、 函数adjlist建立有向图邻接表，返回图的顶点个
4、数。四、 函数pradjlist打印邻接表。对 p.128 graph.h 的说明1. #include “llist.h“ p.392. adjmatrix(matrix) 建立有向图(或无向图)邻接矩阵，返回顶点个数。实参是 MAXMAX二维数组名。二维数组 matrixMAX 是邻接矩阵。输入图的顶点个数。 v1 v2 weight=1 1 0 对矩阵的每个元素赋值 INFIN (9999) 。 v1 v2 weight=1 2 10 用循环语句向矩阵输入数据，以下图为例： v1 v2 weight=1 3 9 10 v1 v2 weight=2 2 0 . v1 v2 weight=0
5、 0 0 9 输入完毕，循环结束。 3. prmatrix(mat,n) 打印邻接矩阵。实参是已生成的邻接矩阵二维数组的数组名，和图的顶点个数。printf(matij)=INFIN)? “t“:“%d“,matij) ；printf(“n“)；如果矩阵元素是 INFIN 不打印否则 打印矩阵元素值即 weight 4. adjlist(list) 建立有向图的邻接表，返回图的顶点个数。实参是大小为 MAX 的结构体数组变量。list是结构体数组变量。输入图的顶点个数。list 赋初值。数据场目前暂空，也可供某些操作存放一定的标志。顶点标号 以 p.127 图 5.1 为例，用循环语句输入数据
6、建立邻接表：数组下标 v1 v2=1 2 或 v1 v2=1 31 v1 v2=1 3 v1 v2=1 22 v1 v2=2 43 v1 v2=3 24 v1 v2=4 3v1 v2=0 0 输入完毕，循环结束。5. pradjlist(list，n) 打印邻接表数据场的值。实参是已生成的邻接表的表头结点所构成的数组的数组名，和图的顶点个数。以 p.127 图 5.1 为例。 6. 参考 p.30 ，补写 push(arg)和 pop()。参考 p.40 inser(arg) 和 delete()补写 engqueue(arg) 和 dequeue() 。NODE *front=NULL,*r
7、ear=NULL; enqueue(arg) int arg; NODE *ptr; ptr=getnode(NODE); ptr-info=arg; ptr-link=NULL; if(front=NULL) front=ptr; else rear-link=ptr; rear=ptr; dequeue() NODE *ptr; int var; if(front=NULL) return(-1); ptr=front; front=ptr-link; var=ptr-info; free(ptr); if(front=NULL) rear=NULL; return(var)5.2 有向图
8、的遍历图遍历的定义：p130图的遍历比树的遍历要复杂，从树根到树中的每个结点只有一条路径，而从图的起始点到达图中的每个顶点可能存在着多条路径。当顺着图中的一条路径访问过某一个顶点后，可能还会顺着另一条路径回到该顶点。5.2.1 先深搜索一、图的先深搜索是树的先根遍历的推广 举例图解二、先深搜索的步骤：1 输出打印顶点标号。 2. 标记已访问过的顶点，NEW OLD 。3 在向前链表中下移一个结点，用指针数组实现 ptr =ptr link 。4 判断向前链表是否结束，ptr !=NULL 。三、图解先深搜索的算法思想 以 p.130 图 5.4 有向图为例。四、对先深搜索 dfs1.c 的说明
9、1 生成邻接表。 2. 打印邻接表。3对指针数组 ptr 的每个元素赋值头结点链场。4对头结点数组每个元素的信息场赋值 NEW 。5for (v=1; v=n; v+)查看起始顶点 v，如果 listv.info=NEW从顶点 v 开始先深搜索，调用 dfs(v) 。6 函数 dfs(v)打印顶点 v 。顶点 v 的信息域改为 OLD 。如果顶点 v 的链域NULL，搜索下一个结点。5.2.2 先广搜索一、 图解先广搜索的算法思想。以 p.132 图 5.6 为例。二、 对 p.134 bfirst.c 的说明。1 生成邻接表。2 打印邻接表。3 头结点信息域赋值 NEW 。4 for (v=
10、1; v=n; v+)查看起始顶点 v，如果 listv.info=NEW，则调用 bfirst( )5 函数 bfirst(v1) 定义一个指针变量 ptr 。 打印顶点标号 v1 。 使 listv.info 从 NEW OLD 。 v1 入队。 while (v=dequeue()!= EOF) /* 出队成功不空 */ ptr=listv.linkwhile (ptr!=NULL) /* 没有到达邻接表的最后一个结点 */ 如果这个结点尚未访问过， 打印该结点，标号 NEW OLD，入队 在邻接表中移过一个结点，ptr=ptrlink授 课 内 容 、 教 具 与 时 间 分 配小 结
11、 、 复 习 、 思 考 题 、 参 考 书思考题：1将课本 p.131 图 5.4 用手工方法先深搜索。再运行 dfs1.c ，生成数据文件存 入 dfs1.r1 。比较两种方法所得的结果。 2.将课本 p.132 图 5.6(a) 用手工方法先深搜索。再运行 dfs1.c ，生成数据文件 存 dfs1.r2 。比较两种方法所得的结果。 3将课本 p.131 图 5.4 用手工方法先广搜索。再运行 bfirst1.c ，生成数据文件 存入 bfirst1.r1 。比较两种方法所得的结果。 4课本将 p.132 图 5.6(a) 用手工方法先广搜索。再运行 bfirst1.c ，生成数据文 件存入 bfirst1.r2 。比较两种方法所得的结果。
