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

数据结构DataStructure主讲人:——:图是顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:其中G表示一个图,V表示图中的顶点的集合,E是图G中顶点之间边的集合。,元素个数可以为零,称空表;在树中,结点个数可以为零,称为空树;在图中,顶点个数不能为零,但可以没有边。线性表每个数据元素只有一个直接前驱和一个直接后继。树型结构每个数据元素只有一个直接前驱,但可能有多个直接后继。图型结构每个数据元素可能有多个直接前驱和多个直接后继。{数据对象V:V具有相同特性的数据元素的集合,称为顶点集。数据关系R:R={VR}VR={<v,w>|v,w∈V,<v,w>表示从v到w的弧,谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P:CreatGraph(&G);DestroyGraph(&G);LocateVex(G,u);……}ABCDEABCDEFG1=(V1,VR1)V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}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)}弧,弧头和弧尾:若<v,w>∈VR,则<v,w>表示从顶点v到顶点w的一条弧。称顶点v为弧尾,称顶点w为弧头。:在图中,若用箭头标明了边是有方向的,则称这样的图为有向图,否则称为无向图。(a)无向图(b)有向图边(x,y)弧<x,y>完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图;在有向图中,如果任意两个顶点之间都存在方向相反的两条弧,则称该图为有向完全图。稀疏图:称边数很少的图为稀疏图。稠密图:称边数很多的图为稠密图。