数据结构6图VIP免费

24/12/29第6章图1图的基本概念及基本术语图的存储结构图的遍历图的应用图属于非线性数据结构的一种。图属于非线性数据结构的一种。树结构中数据元素之间的关系：树结构中数据元素之间的关系：一对多一对多的关系。的关系。图结构中数据元素之间的关系：图结构中数据元素之间的关系：多对多多对多的关系。的关系。24/12/29第6章图26.16.1、图的基本概念、图的基本概念图是由结点集合图是由结点集合(vertex)及结点间的关系及结点间的关系集合组成的一种数据结构集合组成的一种数据结构：GraphGraph＝＝((VV,,EE))其中其中VV={={xx||xx某个数据对象某个数据对象}}是结点的有穷是结点的有穷非空集合；非空集合；EE={(={(xx,,yy)|)|xx,,yyVV}}是结点之间关系的有穷是结点之间关系的有穷集合，也叫做边集合，也叫做边(edge)(edge)集合。集合。1.1.图：图：24/12/29第6章图3有向图有向图GraphGraph＝＝((VV,,EE))VV::是结点的有穷非空集合；是结点的有穷非空集合；EE::有向边边((弧))集合。集合。弧是结点的有序对.例::表示ViVj无向图无向图GraphGraph＝＝((VV,,EE))VV::是结点的有穷非空集合；是结点的有穷非空集合；EE::是结点的是结点的无向边边((无序对无序对))的集合的集合例例:(:(Vi,Vj))Vi与Vj相邻;((Vi,Vj)=()=(Vj,Vi))Vj:弧头Vi:弧尾ViVj24/12/29第6章图4ADTGraph数据对象V:一个集合，集合中所有元素具有相同的特性。数据关系R：R={VR}VR={|P（x，y）∧（x，y∈V）}基本操作：（1）CreateGraph（G）：创建图G。（2）DestoryGraph（G）：销毁图G。（3）LocateVertex（G，v）：确定顶点v在图G中的位置。若图G中没有顶点v，则函数值为“空”。（4）GetVertex（G，i）：取出图G中的第i个顶点的值。若i大于图G中顶点数，则函数值为“空”。24/12/29第6章图5（5）FirstAdjVertex（G，v）：求图G中顶点v的第一个邻接点。若v无邻接点或图G中无顶点v，则函数值为“空”。（6）NextAdjVertex（G，v，w）：已知w是图G中顶点v的某个邻接点，求顶点v的下一个邻接点（紧跟在w后面）。若w是v的最后一个邻接点，则函数值为“空”。（7）InsertVertex（G，u）：在图G中增加一个顶点u。（8）DeleteVertex（G，v）：删除图G的顶点v及与顶点v相关联的弧。（9）InsertArc（G，v，w）：在图G中增加一条从顶点v到顶点w的弧。（10）DeleteArc（G，v，w）：删除图G中从顶点v到顶点w的弧。（11）TraverseGraph（G）：按照某种次序，对图G的每个结点访问一次且仅访问一次。24/12/29第6章图6完全图完全图::对有n个结点的图，无向图:任意两结点都有一条边，即边数为:n(n-1)/2，则称其为无向完全图；邻接结点邻接结点::无向图:若（vi,vj）E，则称结点vi和vj互为邻接点；或称vi和vj相邻接；或称边（vi,vj）关联于结点vi和vj；或称边（vi,vj）与结点vi和vj相关联。有向图：若E,则称结点vj是vi的邻接点。2.基本概念24/12/29第6章图7结点的度：结点的度：一个结点一个结点vv的度是与它相关联的边的条数的度是与它相关联的边的条数记作记作TD(TD(vv))。。无向图：即为该结点相连的边的个数。有向图：依附在某结点的弧的数目。结点的入度：以该结点为弧头的弧的数目。是以是以vv为终点的有向边的条数为终点的有向边的条数,,记作记作ID(ID(vv));;结点的出度：以该结点为弧尾的弧的数目。是以是以vv为始点的有向边的条数为始点的有向边的条数,,记作记作OD(OD(vv))。。有向图：任意两结点都有两条方向相反的弧，即弧数为n(n-1)，则称其为有向完全图。24/12/29第6章图8TD(TD(vv)=ID(v)+OD(v))=ID(v)+OD(v)162543abcdefTD(1)=3TD(2)=3TD(3)=3TD(4)=2TD(5)=2TD(6)=1ID(a)=1OD(a)=2TD(a)=3ID(b)=1OD(b)=2TD(b)=3ID(c)=2OD(c)=0TD(c)=2ID(d)=1OD(d)=1TD(d)=2ID(e)=0OD(e)=1TD(e)=1ID(f)=1OD(f)=0TD(f)=1子图：子图：设有两个图设有两个图GG＝＝((VV,,EE))和和G‘G‘＝＝((VV’,’,EE‘)‘)。。若若VV’’VV且且EE‘‘EE,,则称图则称图G’G’是图是图GG的子图。的子图。0123(a)G10123G1的子图012G1的子图0123G1的子图01201201212(b)G2G2的...