课程名称数据结构.docVIP

课程名称 数据结构14 授课题目图 有向图授课日期2003 年 11 月 26 日授课班级生物医学工程授课时数4授课方式理论课 授 课 重 点 、 难 点  有向图及其表示方法：邻楼表，邻楼矩阵 图的遍历，与树的遍历及线性 掌握先深有哪些信誉好的足球投注网站与先广有哪些信誉好的足球投注网站  授课内容 、 教具与时间分配   授课内容 、 教具与时间分配 第五章 图 5 1.1 有向图及其表示方法 (存储方法) (P127) 图5.1 有向图 顶点的集合 V= {1,2,3,4},顶点表示对象 弧的集合 E={（1，2），（1，3），（2，4），（3，2），（4，3）} 对象之间的关系 图 G = （V，E） 有序对、相邻： 一条弧： v→w ， v为弧的尾，w为弧的头， 是顶点v和w 的有序对，w和v是相邻 的。①→②≠②→① ，故而称为有向图。 路经：顶点序列 路径长途： 弧的条数 简单路径： 简单环路： 标号有向图：图5.2，顶点、弧附加信息 无向图：若图中的边是顶点的无序对，则称此图为无向图。无向图中顶点间的联系不用→表示。 5．1．2 邻接矩阵 P127 邻接矩阵是有向图的一种表示方法（存储方法），是二维数组方法。 图 G =（V，E） ， V= {1，2，3 …… n} 用邻接矩阵表示有向图： ary〔i〕〔j〕 行 列 有向图 标号有向图 i → j 1 a 无 0 空格 （布尔矩阵） 0,1 元素 10 对应图5.1 对应图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 建立有向图邻接表，返回图的顶点个数。 函数pradjlist 打印邻接表。 对 p.128 graph.h 的说明 1. #include llist.h p.39 2. adjmatrix(matrix) 建立有向图(或无向图)邻接矩阵，返回顶点个数。实参是 MAX×MAX 二维数组名。 二维数组 matrix[][MAX] 是邻接矩阵。 输入图的顶点个数。 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 ① ② ......