数据结构课件数据结构课件图.ppt

:ADTgraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。数据关系R:R={VR}VR={<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧,谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P:…….}//ADTgraph顶点——图中的数据元素。弧——若<v,w>∈VR,则<v,w>表示从v到w的一条弧。称v为弧尾或初始点,称w为弧头或终端点,此时的图称为有向图。边——若<v,w>∈VR必有<w,v>∈VR,则以无序对(v,w)代替这两个有序对,表示v和w的一条边。此时的图称为无向图。例:1234(a)有向图G1(b)无向图G214235G1的定义:G1=(V1,{A1})其中:V1={v1,v2,v3,v4}A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2的定义:G2=(V2,{E2})其中:V2={V1,V2,V3,V4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}设n表示图中结点数;e表示边或弧的数目。则:(1)在无向图中,e的取值范围是0~n(n-1)/2;14235例:证:e的最大值=(n-1)+(n-2)+…+1+0=n(n-1)/2在无向图中,如有n(n-1)/2条边,则称为完全图。例:14235(2)在有向图中,e的取值范围是0~n(n-1);例:1234证:e的最大值=(n-1)+(n-1)+…+(n-1)=n(n-1)在有向图中,如有n(n-1)条弧,则称为有向完全图。例:1234有很少条边或弧的图称为稀疏图,反之称为稠密图。权——图的边或弧具有与它相关的数。网——带权的图。例:12345779子图——假设有两个图G=(V,{E})和G`=(V`,{E`}),如果且,则称G`为G的子图。例:图P的子图:1131231234……1234P例:14235判定哪些为它的子图:18231425142351235123514235邻接点——在无向图G=(V,{E})中,如果边(v,v`)∈E,则称顶点v和v`互为邻接点,即v和v`相邻接。边(v,v`)依附于顶点v和v`,或者说边(v,v`)和顶点v和v`相关联。顶点的度——指和该顶点相关联的边的数目,记为:TD(V)。例:14235顶点v1与v2相邻接。顶点v1与v2互为邻接点。边(v1,v2)依附于顶点v1和v2。顶点v1的度为2。顶点v3的度为3。邻接到/自——在有向图G=(V,{A})中,如果弧<v,v`>∈A,则称顶点v邻接到顶点v`,顶点v`邻接自顶点v。弧<v,v`>和顶点v和v`相关联。顶点的入度——以该顶点为头的弧的数目,记为:ID(V)。例:顶点的出度——以该顶点为尾的弧的数目,记为:OD(V)。顶点的度——TD(v)=ID(v)+OD(v)1234弧<v1,v3>和顶点v1和v3相关联。顶点v1邻接到顶点v3。顶点v1邻接到顶点v2。顶点v3邻接自顶点v1。顶点v1的入度为1。顶点v1的出度为2。顶点v1的度为3。