文档介绍：DATA STRUCTURE
第九章图
数据结构
第九章图
图的基本概念
图的存储结构
图的遍历
拓扑排序和关键路径
最小代价生成树
最短路径
内容提要:
1 图的基本概念
2 图的存储结构
3 图的遍历
4 拓扑排序和关键路径
5 最小代价生成树
6 最短路径
图的基本概念
与线性表、树和集合不同,在图结构中,每个数据元素都可以与任何其它数据元素相关。图在许多方面都有所应用。。
第九章图
图的基本概念
图的存储结构
图的遍历
拓扑排序和关键路径
最小代价生成树
最短路径
n1 L1 n2 C2 n3 L2 n4
~
R1 C2 C3 R2
V1
n5
n1 L1 n2 C2 n3 L2 n4
R1 C2 C3 R2
n5
(b) 与(a)对应的图
(a) 电路示例
电路示例及对应的图
图(graph):是数据结构 G=(V,E),其中V(G)是G中结点的有限非空集合,结点的偶对称为边(edge);E(G)是G中边的集合。
图中的结点又称为顶点(vertex)。
有向图(directed graph):指图中代表边的偶对是有序的。
用<v1,v2>代表一条有向边(又称为弧arc),则v1称为弧尾(tail),v2称为弧头(head)。
无向图(undirected graph):指图中代表边的偶对是无序的。
在无向图中边(v1,v2 )和(v2,v1)是同一条边。
图的定义与术语
图的例子
1
0
2
3
4
1
0
2
3
4
(a)无向图G1
(b)有向图G2
图中
V(G1)=V(G2)={v0,v1,v2,v3,v4}
E(G1)={(v0,v1),(v0,v2),(v0,v4),(v1,v2),
(v2,v3),(v2,v4),(v3,v4)}
E(G2)={<v0,v1>,<v0,v2>,<v0,v4>,<v1,v2>,
<v2,v3>,<v2,v4>,<v3,v4>}
自回路:如果图中存在无向边(vi,vi)或有向边<vi,vi>,则称这样的边为自回路。
多重图:指图中两个顶点间允许有多条相同的边。
自回路和多重图的例子
1
0
2
3
1
0
2
3
(b)多重图
(a)自回路
邻接:如果(vi,vj)是无向图中的一条边,则称顶点vi和vj相邻接。
例如:顶点v1和v2是相邻接的。
完全图:顶点数目相同的图中边的数目最多的图称为完全图。
无向完全图有n(n-1)/2条边,有向完全图有n(n-1)条边。
例如:右图是一个完全图。有6条边。
完全图
0
1
2
3
如果<vi,vj>是有向图中的一条边,则称顶点vi邻接到vj;称顶点vj邻接自vi ,并称顶点vj和vi相关联。
子图:图G的一个是图G’=(V’,E’),其中V’(G’)V(G), E’(G’)E(G).
1
0
2
4
图G1的子图
1
0
2
3
4
图G2的子图
1
0
2
3
4
1
0
2
3
4
G1
G2
路径:在无向图G中,若从顶点vp到vq之间存在顶点序列vp, v1,v2,…,vn,vq,使得(vp,v1),(v1,v2),…,(vn , vq )都是图G中的边。对于有向图顶点序列vp,v1,v2,…,vn,vq,应使<vp,v1>, <v1,v2>,…,<vn , vq>都是图G中的边。
路径长度: 指路径上边的数目。
简单路径: 指路径上所有顶点各不相同,起点和终点除外。
回路: 起点和终点相同的简单路径。
1
0
2
3
4
1
0
2
3
4
G1
G2
v0,v1,v2,v3; v0,v1,v2,v3,v4,v2,v0; v0,v1,v2,v3,v4,v0都是路径,它们的路径长度分别为3,6,5。
其中v0,v1,v2,v3和v0,v1,v2,v3,v4,v0是简单路径, v0,v1,v2,v3,v4,v0又是回路。