文档介绍：线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继。
(a1, …, ai-1, ai, …, an)
总结
2011-11-1 week 9
在树形结构中,数据元素之间有着层次关系,每一层上的数据元素可能和下一层中多个元素相关,只能和上一层中一个元素相关。
1
七桥问题
B
D
A
C
2
网络路由问题
B
D
A
C
3
一笔画问题
4
第7章图(Graph)
5
图的定义和术语
图的存储结构(***)
图的遍历(***)
图的连通性问题
有向无环图及其应用
拓扑排序
关键路径
最小生成树(***)
主要内容
最短路径
7
图的定义和术语
图是由一个顶点集 V 和一个弧集 R构成的数据结构。
Graph = (V , R )
其中,VR={<v,w>| v,w∈V 且 P(v,w)}
<v,w>表示从 v 到 w 的一条弧,并称 v 为弧尾,w 为弧头。
谓词 P(v,w) 定义了弧<v,w>的意义或信息。
图的结构定义:
8
如果“弧”是有方向的,称由顶点集和弧集构成的图为有向图(Digraph)。
例如:
G1 = (V1, VR1)
其中
V1={A, B, C, D, E}
VR1={<A,B>, <A,E>,
<B,C>, <C,D>, <D,B>,
<D,A>, <E,C> }
A
B
C
D
E
顶点(Vertex):图中的数据元素。
若<v,w> ∈VR,则<v,w>表示从v到w的一条弧(Arc),v为弧尾(初始点),w为弧头(终端点)
9
若<v, w>VR 必有<w, v>VR,
即VR是对称的,则以无序对(v,w)代替这两个有序对,表示v 和 w 之间的一条边。
B C
A D
F E
由顶点集和边集构成的图称作无向图Undigraph。
例如: G2=(V2,VR2)
V2={A, B, C, D, E, F}
VR2={(A,B), (A,E),
(B,E), (C,D), (D,F),
(B,F), (C,F) }
10