第八章 图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络
图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络
图的基本概念 图定义图是由顶点集合 vertex)及顶点间的关 系集合组成的一种数据结构 Graph=(V,E) 其中V={x|x∈某个数据对象} 是顶点的有穷非空集合; E={(x,y)|x,y∈V} 或E={<x,y>|x,y∈V&&Path(x,y)} 是顶点之间关系的有穷集合,也叫做边(edge) 集合。Pamh(x,y)表示从x到y的一条单向通路, 它是有方向的
图的基本概念 图定义 图是由顶点集合(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 的一条单向通路, 它是有方向的
有向图与无向图在有向图中,顶点对<x,y>是 有序的。在无向图中,顶点对(x,y)是无序的。 完全图着有n个顶点的无向图有n(n-1)2条边 则此图为完全无向图。有n个顶点的有向图有 n(n-1)条边,则此图为完全有向图。 3)④4(5( (a)G1 (C)G3 (d)G4 邻接顶点如果(u,)是E(G)中的一条边,则 称u与v互为邻接顶点
有向图与无向图 在有向图中，顶点对<x, y>是 有序的。在无向图中，顶点对(x, y)是无序的。 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有n 个顶点的有向图有 n(n-1) 条边, 则此图为完全有向图。 邻接顶点 如果 (u, v) 是 E(G) 中的一条边，则 称 u 与 v 互为邻接顶点
权某些图的边具有与它相关的数,称之为权。 这种带权图叫做网络。 0子图设有两个图G=(VE)和G=(V,E") 若vcV且EcE,则称图G是图G的子图 3①3 (a)G1 子图 子图 子图 b)63子图子图子图 顶点的度一个顶点v的度是与它相关联的边的 条数。记作TD()。在有向图中,顶点的度等于 该顶点的入度与出度之和
权 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络。 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。 若 V’ V 且 E‘E, 则称 图G’是 图G 的子图。 顶点的度 一个顶点v的度是与它相关联的边的 条数。记作TD(v)。在有向图中, 顶点的度等于 该顶点的入度与出度之和
顶点ν的入度是以v为终点的有向边的条数,记 作ID(吵);顶点v的出度是以v为始点的有向边 的条数,记作OD( 路径在图G=(V,E)中,着从顶点v出发,沿 些边经过一些顶点vn,V23…,Vm,到达页点 则称顶点序列(vv1V2…my)为从顶点 "到顶点v的路径。它经过的边(Cv)、(m, p)…、(vm")应是属于E的边。 路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和
顶点 v 的入度是以 v 为终点的有向边的条数, 记 作 ID(v); 顶点 v 的出度是以 v 为始点的有向边 的条数, 记作 OD(v)。 路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿 一些边经过一些顶点 vp1 , vp2 , …, vpm，到达顶点 vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点 vi 到顶点 vj 的路径。它经过的边(vi , vp1 )、(vp1 , vp2 )、...、(vpm, vj )应是属于E的边。 路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和