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