PowerPoint Presentation - 华中师范大学.ppt

2017-4-10 1第第7 7章章图图本章主题: 本章主题: 图的基本概念、图的存储结构和图的常用算法教学目的: 教学目的: 教学重点: 教学重点: 图的各种存储方式及其运算教学难点: 教学难点: 图结构存储方式的选择,几种经典图算法的实现本章内容本章内容: :图的基本概念图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径 2017-4-10 2 本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习,读者应该: 1) 了解图的定义和术语 2) 掌握图的各种存储结构 3) 掌握图的深度优先搜索和广度优先搜索遍历算法 4) 理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法本章学习导读本章学习导读 2017-4-10 3 图(Graph )是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构,用来描述元素之间“多对多”的关系。在线性结构中,结点之间的关系是线性关系,除开始结点和终端结点外,每个结点只有一个直接前趋和直接后继。在树形结构中,结点之间的关系实质上是层次关系,同层上的每个结点可以和下一层的零个或多个结点(即孩子)相关,但只能和上一层的一个结点(即双亲)相关(根结点除外)。在图结构中,对结点(图中常称为顶点)的前趋和后继个数不加限制的,即结点之间的关系是任意的。由此,图的应用极为广泛,特别是近年来的迅速发展,已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。 2017-4-10 4 7 7. 1 .1 . 1 .1 图的定义图的定义图图是由一个顶点集是由一个顶点集 V V 和一个弧集和一个弧集 R R构成的数据结构。构成的数据结构。 Graph = (V, R ) Graph = (V, R ) V V = { = { x x | | x x ??某个数据对象某个数据对象} } , ,是顶点的有穷非空集合; 是顶点的有穷非空集合; R R————边的有限集合边的有限集合 R R = {( = {( x x, , y y ) | ) | x x, , y y ?? V V } } 无向图无向图或或 R R = {< = {< x x, , y> y> | | x x, , y y ??V V && && Path Path ( (x x, , y y )} )}有向图有向图是顶点之间关系的有穷集合,也叫做是顶点之间关系的有穷集合,也叫做边边( ( edge) edge) 集合集合。。 Path Path ( (x x, , y y) )表示从表示从 x x 到到 y y 的一条单向通路的一条单向通路, , 它是有方向的。它是有方向的。 x x弧尾, 弧尾, y y弧头弧头。。 7 .1 图及其基本运算图及其基本运算 2017-4-10 5 有向图与无向图有向图与无向图有向图中:边用有向图中:边用< <x, y> x, y> 表示,且表示,且 x x与与y y是有序的。是有序的。 a. a. 有向图中的边称为有向图中的边称为““弧弧”” b. x b. x ————弧尾或弧尾或初始点初始点 y y————弧头或终端点弧头或终端点无向图:边用无向图:边用( ( x, y) x, y) 表示,且顶表示,且顶 x x与与y y是无序的。是无序的。完全图完全图在具有在具有 n n 个顶点的有向图中,最大弧数为个顶点的有向图中,最大弧数为 n n( (n n -1) -1) 在具有在具有 n n 个顶点的无向图中,最大边数为个顶点的无向图中,最大边数为 n n( (n n -1)/2 -1)/2 顶点的度顶点的度无向图:与该顶点相关的边的数目无向图:与该顶点相关的边的数目有向图: 有向图: 入度入度 ID( ID( v v ) ) : :以该顶点为头的弧的数目以该顶点为头的弧的数目出度出度 OD( OD( v v ) ) : :以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目在有向图中在有向图中, , 顶点的度等于该顶点的入度与出度之和顶点的度等于该顶点的入度与出度之和。。 2017-4-10 6 (a) G1 (b) G2 (c) G3 (d) G4 5 2 3 4 1 1 2 3 4 6 7 5 2 2 2 2 3 6 4 5 2 1图图 7-1 7-1 无向图和有向图无向图和有向图 2017-4-10 7 在图 7-1 中,图(a) 为无向图,其中 G1 的顶点集合和边集合分别为: V(G1)={1 ,2,3,4,5,