第 图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络
图的基本概念 图定义图是由顶点集合( vertex)及顶点间的关 系集合组成的一种数据结构: Graph=(V,E) 其中V={x|x∈某个数据对象} 是顶点的有穷非空集合; E={(x,y)|x,y∈} 或E={x,y>|x,y∈V&&Pamh(x,y)} 是顶点之间关系的有穷集合,也叫做边(edge 集合。Pamh(x,y)表示从x到y的一条单向通路, 它是有方向的
(vertex) ：
有向图与无向图在有向图中,顶点对<x,y>是 有序的。在无向图中,顶点对(x,y)是无序的。 完全图若有n个顶点的无向图有m(m-1)2条边 则此图为完全无向图。有n个顶点的有向图有 n(n-1)条边,则此图为完全有向图。 ③④4⑤( (a)G1 (b)G2 (C)G3 邻接顶点如果(a,y是E(G)中的一条边,则 称u与p互为邻接顶点
权某些图的边具有与它相关的数,称之为权。 这种带权图叫做网络。 子图设有两个图G=(V,E)和G“=(V,E)。 若卩gV且E≌E,则称图G是图G的子图。 ② (a)ge 子图 子图 子图 (b)63子图子图子图 顶点的度一个顶点v的度是与它相关联的边的 条数。记作TD()。在有向图中,顶点的度等于 该顶点的入度与出度之和
n顶点v的入度是以v为终点的有向边的条数,记 作ID(吵);顶点v的出度是以v为始点的有向边 的条数,记作OD(吵) 路径在图G=(V,E)中,若从顶点v出发,沿 些边经过一些顶点vp,V2…,Vm,到达顶点 "y则称顶点序列(vpV2…Vmv)为从顶点 v到顶点v的路径。它经过的边(pn)、(vp, 、(my)应是属于E的边。 路径长度 ◆非带权图的路径长度是指此路径上边的条数 ◆带权图的路径长度是指路径上各边的权之和