数据结构之图.ppt

6 图
主要内容
图的基本概念
图的抽象数据类型
图的存储结构
图的周游
最短路径问题
最小支撑树
2
图
图是一种较线性表和树更为复杂的数据结构。
线性表: 线性结构
树: 层次结构
图: 结点之间的关系可以是任意的,即图中任意两个数据元素之间都可能相关。
A
B
C
D
E
图的基本概念
3
图
图 G 是由两个集合顶点集 V(G) 和边集 E(G) 组成的,记作G=( V(G),E(G) ),简称G=(V,E)。
A
B
C
D
E
A
B
C
D
E
A
B
C
D
E
V(vertex)是顶点的有穷非空集合
E(edge)是两个顶点之间的关系,即边的有穷集合
图的定义和基本术语
4
图
无向图: 边是顶点的无序对,即边没有方向性。
v1
v2
v3
v5
v4
V = { v1 , v2 , v3 , v4 , v5 }
E = { ( v1 ,v2 ) , ( v1 ,v4 ) , ( v2 ,v3 ) , ( v2 ,v5 ) , ( v3 ,v4 ) , ( v3 ,v5 ) }
( v1 , v2 )表示顶点 v1 和 v2 之间的边, ( v1 , v2 ) = ( v2 , v1 )。
无向图
5
图
有向图: 其边是顶点的有序对,即边有方向性。
v1
v2
v4
v3
V = { v1 , v2 , v3 , v4 }
E = { < v1 , v2 > , < v1 , v3 > , < v3 , v4 > , < v4 , v1 > }
通常边称为弧,< v1 , v2 >表示顶点 v1 到 v2 的弧。
称 v1 为弧尾,称 v2 为弧头。
< v1 , v2 > ≠< v2 , v1 >
有向图
6
图
有时对图的边或弧赋予相关的数值,这种与图的边或弧相关的数值叫做权。
A
B
C
D
E
5
3
8
2
1
4
9
7
这些权可以表示从一个顶点到另一个顶点的距离。
可以表示从一个顶点到另一个顶点的耗费。
带权图
7
图
性质: 若用 n 表示图中顶点数目,用 e 表示边或弧的数目,若在图中不存在顶点到自身的边或弧,则
对于无向图,0 ≤ e ≤ n(n-1)
1
2
对于有向图,0 ≤ e ≤ n(n-1)
证明:
0 ≤ e 显然成立
对有向图来说,每个顶点至多可发出 n-1 条弧,共 n 个顶点,故至多有 n(n-1) 条弧,即 e ≤ n(n-1) ;
对无向图来说,由于边无方向,则任一两个顶点 v1 和 v2,都有( v1 , v2 ) = ( v2 , v1 ) ,故至多有 n(n-1) 条边;
1
2
基本性质
8
图
有 n(n-1) 条边的无向图称为完全图。
1
2
v1
v2
v4
v3
有 n(n-1) 条弧的有向图称为有向完全图。
v1
v2
v3
有很少条边或弧的图称为稀疏图。
反之称为稠密图。
完全图、稀疏图、稠密图
9
图
假设有两个图 G=(V, E) 和 G’=(V’, E’) ,如果 V’ V,且 E’ E,则称 G’为 G 的子图。
v1
v2
v4
v3
求子图
v1
v1
v3
v1
v4
v3
v1
v2
v4
v3
v1
v2
v4
v3
子图
10
图