数据结构ds-08(图13).pdf

第八章 图 1 第八章 图  图的基本概念  图的存储表示  图的遍历与连通性  最小生成树  最短路径  活动网络(了解) 146-2 图的基本概念  图定义 图是由顶点集合(vertex)及顶点间的 关系集合组成的一种数据结构： Graph ＝( V, E ) 其中 V = { x | x 某个数据对象} 是顶点的有穷非空集合； E = {(x, y ) | x, y  V } 或 E = {x, y | x, y  V Path (x, y )} 是顶点之间关系的有穷集合，也叫做边(edge) 集合。Path (x, y )表示从x 到y 的一条单向通 路, 它是有方向的。 146-3  有向图与无向图 在有向图中，顶点对 x, y 是有序的。在无向图中，顶点对(x, y)是无序的。  完全图 若有 n 个顶点的无向图有 n(n-1)/2 条 边, 则此图为完全无向图。有 n 个顶点的有向 图有n(n-1) 条边, 则此图为完全有向图。 0 0 0 0 1 1 2 1 2 1 3 3 4 5 6 2 2 146-4  邻接顶点 如果 (u, v) 是 E(G) 中的一条边， 则称 u 与 v 互为邻接顶点。  子图 设有两个图G＝(V, E) 和G＝(V, E )。 若V  V 且E E, 则称图G是图G的子图。 0 0 0 0 子图 1 2 1 1 2 2 3 3 3 3  权 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络。 146-5  顶点的度 一个顶点v的度是与它相关联的边 的条数。记作TD(v) 。在有向图中, 顶点的度 等于该顶点的入度与出度之和。  顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向 边的条数, 记作 OD(v) 。  路径 在图 G＝(V, E) 中, 若从顶点 v 出发, 沿 i 一些边经过一些顶点 v , v , …, v ，到达顶 p 1 p 2 pm 点v 。则称顶点序列(v v v ... v