《数据结构第八章图ppt课件》由会员分享，可在线阅读，更多相关《数据结构第八章图ppt课件（75页珍藏版）》请在金锄头文库上搜索。
1、合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去数数 据据 结结 构构（第八章第八章 图图） Data Structures胡学钢胡学钢 张张 晶晶计算机与信息学院计算机与信息学院 20092009年年2 2月月1合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去第八章第八章 图图 (Graph) 第八章第八章 图（图（Graph) 8.1 基本概念和运算 8.2
2、 图的存储 8.3 图的遍历 8.4 最小生成树 8.5 有向无环图的应用 8.6 最短路径2合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 8.1 基本概念和运算 o图图 由顶点集由顶点集V和连接顶点的弧集和连接顶点的弧集E所组成的结构，所组成的结构， 记作记作 G = ( V, E )。 其中弧的形式为其中弧的形式为， 表示从顶点表示从顶点Vi到到Vj之间有一条弧，图形表示为：之间有一条弧，图形表示为： Vi Vj 有向图有向图例例：如右图中的：如右图中的G1就是一个有向
3、图：就是一个有向图： 其中：其中： 顶点集合顶点集合 V=1，2，3，4 弧集弧集 E= , , , , 2134图图G1 有向图示例有向图示例3合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 8.1 基本概念和运算 如果顶点间的关系是相互的，如果顶点间的关系是相互的，即弧的两端没有方向，则图为即弧的两端没有方向，则图为无向图。无向图。其中的弧称为其中的弧称为边。边。边的边的形式形式为为(Vi,Vj)，图形表示为：图形表示为： Vi Vj例例：如右图中的：如右图中的G2就是一
4、个无向图：就是一个无向图： 其中：其中： 顶点集合顶点集合 V=1，2，3，4 边集边集 E= （1,2）,（1,3）,（1,4） （2,4）,（3,4） 2134图图G2 无向图示例无向图示例4合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算 若若G中每条边（弧）对应一个数值中每条边（弧）对应一个数值表示关系的程度，则称图表示关系的程度，则称图G为为网络网络。 例例： 图图G3 就是一个网络就是一个网络 对图对图G = ( V, E )，若存在，若存在G
5、1=(V1，E1)， 满足满足V1V，E1E。则。则G1是是G的的子图。子图。 例如：例如：右图右图G4 就是就是G2 的子图。的子图。 213465837图G3 网络示例2134图图G4 子图示例子图示例2134图图G2 无向图示例无向图示例5合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算顶点间关系顶点间关系： 如果如果 E 则称则称 Vi，Vj相邻接相邻接， Vi邻接到邻接到Vj，Vj邻接自邻接自Vi。 例如，右例如，右 图中，图中， V1邻接到邻接
6、到V2，V4邻接自邻接自V3 若若( Vi,Vj )E则称则称Vi，Vj相邻接相邻接 顶点的顶点的度度 顶点的邻接点的数目。顶点的邻接点的数目。 有向图中：有向图中：入度入度，出度出度。 度入度出度度入度出度。2134图图G1 有向图示例有向图示例6合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算路径路径 若若 顶点序列顶点序列Vi1，Vi2，Vik， 满足满足E或或 者者(Vil，Vi(l+1)E）（）（l=1,2,k-1），）， 则该顶点序列则该顶点序
7、列Vi1，Vi2，Vik 构成一条路径构成一条路径。 例例: 图图G1中，中，1,2,4,1,3,4是一条路径是一条路径简单路径简单路径 中间经过的顶点不重复的路径。中间经过的顶点不重复的路径。 例例:图图G1中，中，( 1,2,4 ) ( 1,3,4 ) ( 1,3,4,1 ) 都是简单路径。都是简单路径。回路回路 首尾相同的路径。首尾相同的路径。 例如，例如， ( 1,3,4,1 )简单回路简单回路 简单路径简单路径 + 回路回路2134图图G1 有向图示例有向图示例7合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披
8、上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算 若若无向图无向图中任意两点间都存在路径中任意两点间都存在路径 则称为则称为连通图。连通图。 否则，称为否则，称为不连通图（非连通图）不连通图（非连通图）。 非连通图包含若干非连通图包含若干连通分量连通分量 极大连通子图。极大连通子图。 若若有向图有向图中的任意两点间可以中的任意两点间可以互相到达互相到达 则称为则称为强连通图。强连通图。12534连通图示例6712534非连通图示例三个连通分量6712534强连通图示例8合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，
9、要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算若若无向图无向图中任意两点间都有一条边中任意两点间都有一条边 则称为则称为无向完全图。无向完全图。 （共有（共有n (n-1) / 2条边）条边）若若有向图有向图中每个顶点到其余各点均有一条弧中每个顶点到其余各点均有一条弧 则称为则称为有向完全图。有向完全图。 （共有（共有n (n-1) 条边）条边） 125345阶无向完全图21344阶有向图示例阶有向图示例9合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇
10、敢地冲出去8.1 基本概念和运算若无向图满足：若无向图满足：连通并且无回路连通并且无回路 则称为则称为树。树。 树的定义有如下几个树的定义有如下几个等价的描述等价的描述： 有最少边数的连通图。有最少边数的连通图。 有有n-1条边的连通图。条边的连通图。 连通的无环图。连通的无环图。有向树有向树 如果在有向图中，如果在有向图中， 有一个顶点的入度为有一个顶点的入度为0，其余顶点的入度为，其余顶点的入度为1， 则称此图为有向树。则称此图为有向树。 并称其中入度为并称其中入度为0的顶点为的顶点为有向根有向根。 右下图就是一个有向树，其中顶点右下图就是一个有向树，其中顶点1就是有向根。就是有向根。67
11、12534树的示例6712534有向树示例10合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算图的运算：图的运算： 基本运算基本运算： 初始化图初始化图 插入顶点插入顶点 插入边（弧）插入边（弧） 修改权值修改权值 删除顶点删除顶点 删除边（弧）删除边（弧） 求指定顶点的邻接点求指定顶点的邻接点 常用运算常用运算： 遍历遍历11合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的
12、衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.1 基本概念和运算 邻接点的求解方法：邻接点的求解方法： 具体实现依赖于图的存储结构，具体实现依赖于图的存储结构， 可以考虑用两个运算来实现求解：可以考虑用两个运算来实现求解： int firstadj(G,v); 返回顶点返回顶点v的第一个邻接点号。的第一个邻接点号。 若不存在时，返回若不存在时，返回0（或定义为（或定义为-1）。）。 int nextadj(G,v,w); 返回顶点返回顶点v的邻接点中处于邻接点的邻接点中处于邻接点w之后的邻接点号。之后的邻接点号。 若不存在时，返回若不存在时，返回0（或定义为（或定义为-1）。）。12合肥工业大学合肥
13、工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.2 图的存储图的存储图的存储 图结构在计算机中的存储形式图结构在计算机中的存储形式1. 邻接矩阵邻接矩阵 （1）不带权值 假设图中有n个顶点。则采用nn的矩阵A来表示， 1 E 其中 Aij 0 否则例例：13240 1 1 00 0 0 10 0 0 11 0 0 0行的方向：发出的弧列的方向 ：进入的弧对应关系13合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸
14、湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.2 图的存储 （2） 网络的表示方法 wij E Aij 0 或 否则例例： 4 3 54 23 65 2 6 12430 1 1 11 0 0 11 0 0 11 1 1 0无向图的邻接矩阵对称 14236352414合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.2 图的存储2. 邻接表表示法邻接表表示法 将邻接点构成链表将邻接点构成链表 例例：12341243data firstadj2341414123对应关系15合肥工业
15、大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.2 图的存储o逆邻接链表逆邻接链表 将将“邻接自邻接自”的顶点连成链表的顶点连成链表 1234data firstadj411343213212344412data firstadj对应关系代表弧16合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去8.3 图的遍历图的遍历图的遍历访问图中所有顶点一次且仅且一次。访问图中
16、所有顶点一次且仅且一次。 深度优先搜索遍历深度优先搜索遍历 图的两种遍历算法图的两种遍历算法 广度优先搜索遍历广度优先搜索遍历8.3.1 深度优先搜索遍历（深度优先搜索遍历（Depth First Search) 这一问题求解包括几个部分。这一问题求解包括几个部分。 1. 基本算法基本算法 从顶点从顶点v0出发深度优先搜索遍历图出发深度优先搜索遍历图G的的dfs (v0)描述如下：描述如下： (1) 访问访问v0； (2) 依次从依次从v0的未被访问过的邻接点出发深度遍历。的未被访问过的邻接点出发深度遍历。 17合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去dfs(8)dfs(9)dfs(4)dfs(3)8.3.1 深度优先搜索遍历深度优先搜索遍历下面以下图为例来讨论下面以下图为例来讨论dfs算法的执行过程：调用算法的执行过程：调用dfs(1) 此箭头表示是从遍历运算dfs(1)中调用dfs(2)，即从顶点1直接转到2 此虚箭头表示是在dfs(3)执行完毕后返回到遍历
