数据结构MapleRelated.pptVIP

数据结构-Maple Related- 牟克典 数学科学学院信息科学系 2012秋季 4/10/2017 1 第五讲 图和图算法(1) 图：基本概念和性质 图的基本操作 图的遍历 宽度优先 深度优先 图的表示 生成树 最小生成树 2012年11月21日 10:10-12:00 三教303 4/10/2017 2 图（graph） 图是一种数学结构，数学里有分支 “图论”，研究一种拓扑结构 这里把它看着一类复杂数据结构，用于表示具有各种复杂关系的数据集合。图在实际中应用很广泛 本章介绍图的最基本知识，图的基本实现方法，以及图的若干最基本的计算问题和重要算法 重点算法（这些算法是本章最重要的内容）： 图的深度优先搜索与广度优先搜索 最小生成树的 Prim 算法和 Kruskal 算法 求单源最短路径的 Dijkstra 算法 求所有顶点对之间最短路径的 Floyd 算法 拓扑排序 关键路径 4/10/2017 3 图：基本概念 图是二元组 G = ( V, E )，其中 V 是顶点的非空有穷集合（可有空图的概念，用处不大） E 是顶点偶对 (称为“边”) 的集合，E ? V×V V 中的顶点也称为图 G 的顶点，E 中的边也称为图 G 的边 有向图：有向图中的边有方向，边是顶点的有序对 有序对用尖括号表示。vi,vj 表示从 vi 到 vj 的有向边，vi 称为边的始点，vj 是边的终点。vi, vj 和 vj, vi 表示两条不同有向边 无向图：无向图中的边没有方向，是顶点的无序对 无序对用圆括号表示，(vi , vj) 和 (vj , vi) 表示同一条无向边 如果图 G 里有边 vi,vj ? E 或者 (vi, vj) ? E 顶点 vj 称为 vi 的邻接顶点（对无向图，邻接点是双向的） 这种边称为与顶点 vi 相关联的边或 vi 的邻接边 与有序树类似，图中的邻接边也可以规定顺序 4/10/2017 4 图 图可用图形自然表示（圆圈表示顶点，线段或箭头表示边） 两个限制：1）不考虑顶点到自身的边，若 (vi ,vj) 或 vi ,vj 是 G 的边，则要求 vi ≠vj；2）顶点间没有重复出现的边，若 (vi ,vj) 或 vi ,vj 是 G 的边，则它是这两个顶点间的唯一边（不存在多重边） 去掉这些限制得到稍微不同的数学研究对象。图论中也研究它们 4/10/2017 5 图：概念和性质 完全图：任意两个顶点之间都有边的图（有向图或无向图）。显然： n 个顶点的无向完全图有 n*(n-1)/2 条边 n 个顶点的有向完全图有 n*(n-1) 条边 注意图上的重要事实：|E| ≤ |V|2，或者 |E| ＝ O( |V|2 ) 度（顶点的度）：与一个顶点关联的边的个数。 对于有向图，还分为出度和入度，分别表示以该顶点为始点或者终点的边的个数 无论是有向图还是无向图，顶点数 n，边数 e 和度数满足下面关系: 其中 D(vi) 表示 vi 的度数 4/10/2017 6 路径和相关概念 路径：对图 G = (V, E)，若存在顶点序列 vi0,vi1,…,vi(m)，使 (vi0,vi1)，(vi1,vi2),…, (vi(m-1), vi(m)) 都在 E 中（对有向图 vi0,vi1, vi1,vi2, …, vi(m-1), vi(m) 都在 E 中) 则说从顶点vi0到vi(m) 存在一条路径 vi0,vi1,…,vi(m) 称为从 vi0 到 vi(m) 的路径 路径长度：路径上边的条数 回路（环）：起点和终点相同的路径 如果除起点和终点外的其他顶点均不相同，则称为简单回路 简单路径：内部不包含环路的路径， 即，路径上的顶点除起点和终点可能相同外，其它顶点均不相同 简单回路也是简单路径 4/10/2017 7 子图、有根图 对图 G = (V，E) 和 G’ = (V’，E’)，如果 V’ ? V 且 E’ ? E，就称 G’ 是 G 的子图。特别的，G 是其自身的子图 下面是有向图G1的几个子图 有根图 如果有向图 G 中存在一个顶点 v，从 v 有路径可以到达图 G 中其它所有顶点，则称 G 为一个有根图，v 称为图 G 的一个根 有根图中的根可能不唯一 4/10/2017 8 连通图 连通：如果无向图 G 中存在从 vi 到 vj 的路径（显然它也是从 vj到 vi 的路径)，则称 vi 与 vj 连通（默认顶点 v 到自身连通） 无向图的连通性 连通图：如果无向图 G 中的任意两个不同顶点 vi 和 vj 之间都连通（都存在路径），则称 G 为连通图 极大连通子图是图中极大的连通子图（没有真包含它连通子图） 连通分量：无向图 G 的一个极大连通子图称为 G 的一个连通分量。若 G 不连通，其