数据结构_数据结构7.ppt

(双) 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>的意义或信息。图的结构定义:由于“弧”是有方向的,因此称由顶点集和弧集构成的图为有向图。 AB E C D例如:G1 = (V1, VR1)其中V1={A, B, C, D, E}VR1={<A,B>, <A,E>, <B,C>, <C,D>, <D,B>, <D,A>, <E,C> }若<v, w>?VR 必有<w, v>?VR, 则称(v,w) 为顶点v 和顶点 w 之间存在一条边。 B CA D F E由顶点集和边集构成的图称作无向图。例如: 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) }名词和术语网、子图完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林ABECFAEABBC设图G=(V,{VR}) 和图G?=(V?,{VR?}),且 V??V, VR??VR,则称 G?为 G 的子图。1597211132弧或边带权的图分别称作有向网或无向网。假设图中有 n 个顶点,e 条边,则含有 e=n(n-1)/2 条边的无向图称作完全图;含有 e=n(n-1) 条弧的有向图称作有向完全图;若边或弧的个数 e<nlogn,则称作稀疏图,否则称作稠密图。假若顶点v 和顶点w 之间存在一条边,则称顶点v 和w 互为邻接点,ACDFE例如:TD(B) = 3TD(A) = 2边(v,w) 和顶点v 和w 相关联。和顶点v 关联的边的数目定义为顶点的度。B顶点的出度: 以顶点v为弧尾的弧的数目;ABECF对有向图来说,顶点的入度: 以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B) = 2OD(B) = 1TD(B) = 3