146-1,图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络,第八章 图,146-2,图的基本概念,图定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合； E = (x, y) | x, y V 或 E = | x, y 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的边。,146-6,路径长度 非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。 简单路径 若路径上各顶点 v1, v2, ., vm 均不 互相重复, 则称这样的路径为简单路径。 回路 若路径上
