东南大学计算机学院方效林.ppt
《东南大学计算机学院方效林.ppt》由会员分享,可在线阅读,更多相关《东南大学计算机学院方效林.ppt(58页珍藏版)》请在三一文库上搜索。
1、东南大学计算机学院 方效林,本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件,第七章 图,本章主要内容,图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径,2,图的基本概念,定义 图是由顶点及顶点之间的关系集合组成的数据结构Graph = ( V, E ) V是顶点的有穷非空集,V=x | x某个对象 E是顶点之间关系,称为边(edge)的有穷非穷集,E=(x,y) | x,yV,3,图的基本概念,有向图与无向图 有向图中,顶点对(x,y)是有序的 无向图中,顶点对(x,y)是无序的 完全图 n个顶点的无向图有n(n-1)/2条边,该图为完全图 n个顶点的有向图有
2、n(n-1)条边,该图为完全有向图,4,2,1,3,0,2,1,4,0,完全无向图,8,6,7,3,6,5,无向图(自由树),1,2,0,有向图,完全有向图,图的基本概念,邻接顶点 (u, v)是E中的一条边,则称u与v互为邻接顶点 子图 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称G是G 的子图 权:边附带的权重,称这样的图称为带权图,5,2,1,3,0,1,3,0,2,1,3,2,1,3,0,子图,图的基本概念,顶点v的度 与v为端点的边条数,记作D(v) 入度:有向图中,以v为终点的边的条数,记作ID(v) 出度:有向图中,以v为始点的边的条数,记作OD(
3、v) 有向图中v的度为入度与出度的和 路径 图 G(V, E) 中, 从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm,到达顶点vj。则称顶点序列 (vi vp1 vp2 . vpm vj)为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应是属于E的边。,6,图的基本概念,路径长度 非带权图的路径长度是指此路径上边的条数 带权图的路径长度是指路径上各边的权之和 简单路径 路径上各顶点 v1,v2,.,vm 均不互相重复 回路 路径上第一个顶点 v1 与最后一个顶点vm 重合,7,图的基本概念,连通图与连通
4、分量 无向图中, 从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。 若图中任意一对顶点都是连通的, 则此图是连通图 非连通图的极大连通子图叫连通分量,8,2,1,3,0,4,连通图,5,2,1,3,0,4,非连通图(有2个连通分量),5,图的基本概念,强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图 非强连通图的极大强连通子图叫做强连通分量 生成树 一个连通图的生成树是其极小连通子图,在 n 个顶点的情形下,有n-1条边。,9,图的存储表示,邻接矩阵 一个有 n 个顶点的图G = ( V, E ), 图
5、的邻接矩阵是一个二维数组 A.edgenn,10,有向图的邻接矩阵可能不对称,无向图的邻接矩阵是对称的,图的存储表示,邻接矩阵 网络(带权图)的邻接矩阵,11,图的存储表示,邻接表 无向图的邻接表,12,data,link,dest,link,dest,link,dest保存的是邻接顶点的下标,顶点数组,链接结点,图的存储表示,邻接表 有向图的邻接表和逆邻接表,13,data,link,dest,link,data,link,dest,link,dest,link,邻接表(出边表),逆邻接表(入边表),图的存储表示,网络(带权图)的邻接表,14,邻接表(出边表),图的遍历,从给定顶点出发,沿某
6、些边遍历图中所有顶点一次且仅一次 使用辅助数组visited 标识顶点是否被访问过 visited 初始为0 访问过后标识为1,15,图的遍历,遍历方式 深度优先遍历 DFS (Depth First Search) 广度优先遍历 BFS (Breadth First Search),16,图的遍历,遍历方式 深度优先遍历 DFS (Depth First Search) 从顶点v1出发,访问任一未被访问的邻接顶点v2; 再从顶点v2出发,访问任一未被访问的邻接顶点v3; 再从顶点v3出发, ,如此进行下去,直到所有邻接顶点都被访问过为止 退回一步到刚被访问的顶点,看是否有未被访问的邻接顶点。
7、 若有,则继续访问 否则,再退回一步 直到所有顶点都被访问,17,图的遍历,遍历方式 深度优先遍历 DFS (Depth First Search),18,深度优先搜索过程,深度优先生成树,1,2,3,4,5,6,7,8,9,图的遍历,遍历方式 广度优先遍历 BFS (Breadth First Search) 从起始顶点v出发,依次访问v的未被访问的邻接顶点w1, w2, , wm 顺序访问w1, w2, , wm的所有未被访问的邻接顶点,以此类推,直到所有顶点都被访问,19,图的遍历,遍历方式 广度优先遍历 BFS (Breadth First Search),20,广度优先搜索过程,广度
8、优先生成树,1,2,5,7,3,6,4,8,9,21,作业: n个顶点无向图,邻接矩阵形式存储在矩阵EdgeNN, 用visited记录是否访问过,初始时visitedN=0 写出深度优先遍历程序: DFS(0, Edge) 写出广度优先遍历程序: BFS(0, Edge) ,图的遍历,遍历方式 深度优先遍历 DFS (Depth First Search) 回溯算法 广度优先遍历 BFS (Breadth First Search) 分层算法,22,图的连通性,当无向图不连通时,从顶点v出发,遍历方法只能遍历v所在连通分量上的所有顶点,23,非连通无向图,一种遍历生成森林,图的连通性,强连通
9、有向图 不同出发点得到生成树不同,24,非强连通图,图的连通性,非强连通有向图 遍历可能生成的不是树,而是森林,25,生成森林,生成树,非强连通图 D,E不能到达A,B,C 但A,B,C可到达D,E,最小生成树,在连通带权图上构造一棵生成树,使得该树上边权值的总和最小 连通带权图 生成树(n个顶点,n-1条边,无回路) 边的权值总和最小,26,最小生成树,克鲁斯卡尔 (Kruskal) 算法 初始时所有顶点自成一连通分量 在图上选权值最小的边emin,判断emin两端点是否属于不同连通分量ci,cj 若是,将ci,cj用emin连接成同一个连通分量 否则,舍弃emin 重复上一过程,直到所有顶
10、点在同一连通分量,27,最小生成树,克鲁斯卡尔 (Kruskal) 算法,28,最小生成树,克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 可使用并查集技术加快判断速度,29,10 (0,5),12 (2,3),14 (1,6),16 (1,2),18 (3,6),22 (3,4),24 (4,6),25 (4,5),初始时,最小生成树,克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 可使用并查集技术加快判断速度,30,10 (0,5),12 (2,3),14 (1,6),16 (1,2),18 (3,6),2
11、2 (3,4),24 (4,6),25 (4,5),取边(0,5),最小生成树,克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 可使用并查集技术加快判断速度,31,10 (0,5),12 (2,3),14 (1,6),16 (1,2),18 (3,6),22 (3,4),24 (4,6),25 (4,5),取边(2,3),最小生成树,克鲁斯卡尔 (Kruskal) 算法 经常需要判断权值最小的边的两端是否属于不同连通分量 可使用并查集技术加快判断速度,32,10 (0,5),12 (2,3),14 (1,6),16 (1,2),18 (3,6),22
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 东南 大学计算机 院方
链接地址:https://www.31doc.com/p-3095766.html