《数据结构的第八讲》PPT课件.ppt

引言
现实世界存在许多不同类型的模拟系统。
例如：交通流量就是其中一个实例。
顶点表示街道的十字路口，同时边表示街道本身。
加权边可以用来表示车速限制或者车道数量。
模型可以使用系统来确定最佳路线和可能遭受交通堵塞的街道。
例如：航空公司的飞行系统。
每一个飞机场就是一个顶点，而从一个顶点到另一个顶点的航线就是一条边。
加权的边可以表示从一个机场到另一个机场飞行的费用，或者表示从一个机场到另一个机场的大概距离，这取决于模拟的内容。
由图模拟真实世界系统
1
精选ppt
第八讲 图和图的算法
2
精选ppt
主要内容
图的定义
图的存储表示
图的第一个应用：拓扑排序
图的搜索
最小生成树
查找最短路径
3
精选ppt
图的定义
4
精选ppt
图的定义
图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：
Graph＝( V, E )
其中：
V = { vi | vi  某个数据对象}
是顶点的有穷非空集合；
E = {(vi, vj) | vi, vj  V } 或
E = {<vi, vj> | vi, vj  V && Path (vi, vj)}
是顶点之间关系的有穷集合，也叫做边(edge)集合。
Path (vi, vj)表示从 vi 到 vj 的一条单向通路, 它是有方向的。
0
2
1
3
图是由一组顶点和一组边构成的
5
精选ppt
图的定义
无向图:
( vi , vj ) = ( vj , vi ) 同一条边.
有向图:
< vi , vj > ::=  < vj , vi > 不同边
vi
vj
tail
head
6
精选ppt
图的定义
vi
vj
vi 和 vj 是互为邻接顶点 ;
( vi , vj ) 依附于 vi 和 vj
vi
vj
vi 邻接到 vj ; vj 邻接自 vi ;
< vi , vj > 相关联于 vi and vj
子图 G’  G :
V( G’ )  V( G ) && E( G’ )  E( G )
0
1
2
3
子图
0
1
3
0
1
2
3
0
2
3
7
精选ppt
图的定义
路径（ path）：
图中顶点的序列，所有的顶点由边连接在一起。
在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 (vi vp1 vp2 ... vpm vj) 为从顶点vi 到顶点 vj 的路径。
它经过的边
(vi, vp1)、(vp1, vp2)、...、(vpm, vj)
应是属于E的边。
8
精选ppt
图的定义
路径的长度：
从路径中第一个顶点到最后一个顶点的边的数量。
讨论的图对象的限制 :
(1) 自身环 不讨论.
(2) 与两个特定顶点相关联的边不能多于一条，多重图也不讨论。
0
1
0
1
2
9
精选ppt
图的定义
简单路径：
若路径上各顶点 v1,v2,...,vm 均不互相重复, 则称这样的路径为简单路径。
回路：
若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环（loop）。
环的长度为 0。
在有向图中路径至少为 1以便于初始定点也是结束定点。
在有向图中，边可能是相同的，但是在无向图中，边必须是不同的。
10
精选ppt