数据结构MapleRelated.ppt
《数据结构MapleRelated.ppt》由会员分享,可在线阅读,更多相关《数据结构MapleRelated.ppt(45页珍藏版)》请在三一文库上搜索。
1、数据结构 -Maple Related- 牟克典 数学科学学院信息科学系 2012秋季 11/20/20121 第五讲 图和图算法(1) 图:基本概念和性质 图的基本操作 图的遍历 宽度优先 深度优先 图的表示 生成树 最小生成树 2012年11月21日 10:10-12:00 三教303 11/20/20122 图(graph) 图是一种数学结构,数学里有分支 “图论”,研究一种拓扑结构 这里把它看着一类复杂数据结构,用于表示具有各种复杂关系的数据集 合。图在实际中应用很广泛 本章介绍图的最基本知识,图的基本实现方法,以及图的若干最基本的 计算问题和重要算法 重点算法(这些算法是本章最重要的
2、内容): 图的深度优先搜索与广度优先搜索 最小生成树的 Prim 算法和 Kruskal 算法 求单源最短路径的 Dijkstra 算法 求所有顶点对之间最短路径的 Floyd 算法 拓扑排序 关键路径 11/20/20123 图:基本概念 图是二元组 G = ( V, E ),其中 V 是顶点的非空有穷集合(可有空图的概念,用处不大) E 是顶点偶对 (称为“边”) 的集合,E VV V 中的顶点也称为图 G 的顶点,E 中的边也称为图 G 的边 有向图:有向图中的边有方向,边是顶点的有序对 有序对用尖括号表示。 表示从 vi 到 vj 的有向边,vi 称为 边的始点,vj 是边的终点。 和
3、 表示两条不同 有向边 无向图:无向图中的边没有方向,是顶点的无序对 无序对用圆括号表示,(vi , vj) 和 (vj , vi) 表示同一条无向边 如果图 G 里有边 E 或者 (vi, vj) E 顶点 vj 称为 vi 的邻接顶点(对无向图,邻接点是双向的) 这种边称为与顶点 vi 相关联的边或 vi 的邻接边 与有序树类似,图中的邻接边也可以规定顺序 11/20/20124 图 图可用图形自然表示(圆圈表示顶点,线段或箭头表示边) v1 v2 v3 G1 v1 v4 v3 v3 G2 v1 v2v3 v7v6v5v4 G3 两个限制:1)不考虑顶点到自身的边,若 (vi ,vj) 或
4、 是 G 的 边,则要求 vi vj;2)顶点间没有重复出现的边,若 (vi ,vj) 或 是 G 的边,则它是这两个顶点间的唯一边(不存在多重边) 去掉这些限制得到稍微不同的数学研究对象。图论中也研究它们 11/20/20125 图:概念和性质 完全图:任意两个顶点之间都有边的图(有向图或无向图)。显然: n 个顶点的无向完全图有 n*(n-1)/2 条边 n 个顶点的有向完全图有 n*(n-1) 条边 注意图上的重要事实:|E| |V|2,或者 |E| O( |V|2 ) 度(顶点的度):与一个顶点关联的边的个数。 对于有向图,还分为出度和入度,分别表示以该顶点为始点或者终点 的边的个数
5、无论是有向图还是无向图,顶点数 n,边数 e 和度数满足下面关系: 其中 D(vi) 表示 vi 的度数 11/20/20126 路径和相关概念 路径:对图 G = (V, E),若存在顶点序列 vi0,vi1,vi(m),使 (vi0,vi1),(vi1,vi2), (vi(m-1), vi(m) 都在 E 中(对有向图 , , , 都在 E 中) 则说从顶点vi0到vi(m) 存在一条路径 称为从 vi0 到 vi(m) 的路径 路径长度:路径上边的条数 回路(环):起点和终点相同的路径 如果除起点和终点外的其他顶点均不相同,则称为简单回路 简单路径:内部不包含环路的路径, 即,路径上的顶
6、点除起点和终点可能相同外,其它顶点均不相同 简单回路也是简单路径 11/20/20127 子图、有根图 对图 G = (V,E) 和 G = (V,E),如果 V V 且 E E ,就称 G 是 G 的子图。特别的,G 是其自身的子图 下面是有向图G1的几个子图 G1 v1v 1 v1 v 2 v 2 v2 v2 v3 v1 v 2 v 3 有根图 q 如果有向图 G 中存在一个顶点 v,从 v 有路径可以到达图 G 中其 它所有顶点,则称 G 为一个有根图,v 称为图 G 的一个根 q 有根图中的根可能不唯一 11/20/20128 连通图 连通:如果无向图 G 中存在从 vi 到 vj 的
7、路径(显然它也是从 vj到 vi 的路 径),则称 vi 与 vj 连通(默认顶点 v 到自身连通) 无向图的连通性 连通图:如果无向图 G 中的任意两个不同顶点 vi 和 vj 之间都连通(都存在路径 ),则称 G 为连通图 极大连通子图是图中极大的连通子图(没有真包含它连通子图) 连通分量:无向图 G 的一个极大连通子图称为 G 的一个连通分量。若 G 不连通 ,其连通分量将多于一个,它们形成 G 的一个划分 有向图的连通性 强连通图:如果有向图 G 中任意两个不同顶点 vi 和 vj 之间都存在从 vi 到 vj 以 及从 vj 和 vi 的路径,则称 G 是一个强连通图 强连通分量:有
8、向图G的极大强连通子图称为它的强连通分量 有向图 G 的强连通分量形成其顶点的一个划分 11/20/20129 带权图和网络 若图 G 的每条边都被赋以一个权值,G 称为是带权图 权值可用于表示实际应用中与顶点关联有关的某种量 带权的连通无向图称为网络 下图为一个网络 网络是实际应用非常广泛的一类图结构 后面会介绍网络上的一些重要性质和算法、以及它们的应用 11/20/201210 图的基本操作 作为复杂的数据结构,图上可能定义许多操作。下面列举一些操作 创建空图,判断图 g 是否空图,把图 g 置为空图: createGraph ( ) isEmptyGraph ( g ) clearGra
9、ph ( g ) 图中顶点个数(order)和边个数(size) order( g ) size( g ) 图中所有顶点的集合,所有边的集合: vertices ( g )edges( g ) 图 g 中顶点 v 的入度和出度(结果用二元序列表示): vdeg ( g , v ) 在图 g 中增加一条边 或 (v1,v2): addEdge ( g , v1 , v2 ) 11/20/201211 图的基本操作 检查图 g 中是否存在边 或 (v1,v2): findEdge ( g , v1 , v2 ) 在图 g 中删除边 或 (v1,v2): deleteEdge ( g , v1 ,
10、v2 ) 找出图 g 中与顶点 v 相邻的顶点(集合或表): adjacentVertices ( g , v ) 在图 g 中删除一顶点和与之关联的所有边: deleteVertex ( g , v ) 图中的遍历操作。与树遍历的关键差异包括: 要防止走到已遍历过的部分 要考虑图的连通性问题(图可能不连通,遍历完一个连通分支后还不能 结束,需要去遍历其他分支) 11/20/201212 图的遍历 图的遍历 按某种方式系统访问图中所有顶点,且每个顶点仅访问一次的过程 也称为图的周游 遍历的基本部分是访问一个顶点所在的连通分支(对有向图,强 连通分支)的全部顶点。如果不是连通图,还需要访问其他连
11、通 分支 基本的图遍历方法同样是: 深度优先遍历(通过深度优先搜索的方式遍历) 广度优先遍历(通过广度优先搜索的方式遍历) 两种方式对有向图和无向图都适用 11/20/201213 深度优先遍历 深度优先遍历 (Depth-First Traversal) 的策略就是按照深度优先搜索( Depth-First Search)的方式遍历,做法是: 从指定顶点 v 出发,先访问 v 并将其标记为已访问 依次从 v 的未访问过的各邻接顶点 w 出发进行深度优先搜索(要取得 v 的邻接 顶点,可能排列一种顺序),直到图中与 v 连通的所有顶点都访问过(递归) 如果图中还有未访问顶点,则选一个未访问顶点
12、,由它出发重复上述过程,直到 图中所有顶点都已访问为止 对图进行深度优先遍历,按访问顶点的先后次序得到的顶点序列,称为该 图的深度优先搜索序列( Depth-First Search 序列),通常简称为 DFS 序列 由于遍历中邻接点通常有多个,对它们的不同(递归)访问顺序将得到不同的 DFS 序列(不唯一) 如果规定了图中个顶点的邻接点顺序,DFS 序列就确定了 11/20/201214 深度优先遍历 一个简单示例: V7V6 V3 V2 V5 V1 V8 V4 假定各顶点的邻接顶点从左到右排序,得到的 DFS 序列: 11/20/201215 深度优先遍历算法 这个示意算法说明了 DFS
13、的过程,基本部分是遍历一个连 通分支 DFTGraph := proc(g:Graph) while existUnvisited(g) do DFSComponent(g, nextUnvisited(g) od end: DFSComponent := proc(g, v) local adjs, va; visit(v); markVisited(v); adjs := adjacentVertices (g, v); for va in adjs do if unvisited(va) then DFSComponent(g, va) fi od end: 11/20/201216 广
14、度优先遍历 广度优先遍历 (Breadth-First Traversal) 的遍历方式是通过广度优先搜索 (Breadth-First Search),具体过程是: 从指定顶点 v 出发,先访问顶点 v 并将其标记为已访问 依次访问 v 的所有相邻顶点 v1, v2, , vm (可以为 v 的邻接顶点假定一种顺 序) ,然后依次访问与 v1, v2, , vm 邻接的所有未访问顶点(递归) 直到所有已访问顶点的相邻顶点都已访问为止 如果图中还有未访问顶点,则选择一个未访问顶点,由它出发进行广度优先搜索 ,直到所有顶点都已访问为止 通过广度优先遍历得到的顶点序列称为图中顶点的广度优先搜索序列
15、( Breadth-First Search 序列)或BFS序列 由于遍历中邻接点通常有多个,对它们的不同(递归)访问顺序将得到不同的 BFS 序列(不唯一) 如果规定了图中各顶点的邻接点顺序,BFS 序列就确定了 11/20/201217 广度优先遍历 简单示例: V7V6 V3 V2 V5 V1 V8 V4 假定各顶点的邻接顶点从左到右排序,得到的 BFS 序列: 11/20/201218 广度优先遍历 BFTGraph := proc(g:Graph) while existUnvisited(g) do BFSComponent(g, nextUnvisited(g) od end:
16、BFSComponent := proc(g, v) local vq, va, adjs; vq := queuenew(v); while not queueempty(vq) do v := queuedequeue(vq); visit(v); markVisited(v); adjs := adjacentVertices (g, v); for va in adjs do if unvisited(va) then queueenqueue(va) fi od od end: 11/20/201219 图的表示 图的结构比较复杂,任意两个顶点间都可能存在边 需要表示顶点及顶点间的边
17、,存储方法很多 应根据具体应用和需要做的操作,选择图的存储表示法 图的最基本表示方法是邻接矩阵表示法 表示图的邻接矩阵通常非常稀疏。很多图中边的个数与顶点个数成线 性关系,如中国铁路线路图 人们提出了其他表示方法,都可看着邻接矩阵的“压缩”版本 直接邻接矩阵存储空间可能浪费较大,人们考虑了各种变形,如: 邻接表表示法 邻接多重表表示法 图的十字链表,等 下面只介绍邻接表表示法 11/20/201220 图的表示:邻接矩阵 邻接矩阵是一个矩阵,其中表示了图中顶点间的邻接关系 设 G = (V,E) 为 n 个顶点的图,其邻接矩阵为如下 n 阶方阵 : 的权,图 G 的邻接矩阵定义为(用邻 接矩阵
18、元素记录边的权): = 或若 或 或若 vvvv vvvvw jiA jiji jijiij ,),( 0 ,),( , 不是图G的边 是图G的边 下面带权图的两个邻接矩阵分别为A3和A4,根据需要用 0 或表示无边 = 0100110 100248 02065 114603 08530 3 A = 1011 10248 265 11463 853 4 A 11/20/201223 在 Maple 里实现邻接矩阵 在 Maple 里用邻接矩阵方法实现图,内部表示可以用两个成分 : 一个 n 元素的一维 Array 存储顶点信息 一个 nn 的二维 Array 表示邻接矩阵 这种表示需要首先确定
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 MapleRelated
链接地址:https://www.31doc.com/p-3185600.html