数据结构6图.ppt

《数据结构6图.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章图图的基本概念及基本术语图的存储结构图的遍历图的应用图属于非线性数据结构的一种。树结构中数据元素之间的关系：一对多的关系。图结构中数据元素之间的关系：多对多的关系。7/25/20211第6章图6.1、图的基本概念图是由结点集合(vertex)及结点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x

2、x某个数据对象}是结点的有穷非空集合；E={(x,y)

3、x,yV}是结点之间关系的有穷集合，也叫做边(edge)集合。1.图：7/25/20212第6章图有向图Graph＝(V,E)V:是结点的有穷非

4、空集合；E:有向边(弧)集合。弧是结点的有序对.例::表示ViVj无向图Graph＝(V,E)V:是结点的有穷非空集合；E:是结点的无向边(无序对)的集合例:(Vi,Vj)Vi与Vj相邻;(Vi,Vj)=(Vj,Vi)Vj:弧头Vi:弧尾ViVj7/25/20213第6章图ADTGraph数据对象V:一个集合，集合中所有元素具有相同的特性。数据关系R：R={VR}VR={

5、P（x，y）∧（x，y∈V）}基本操作：（1）CreateGraph（G）：创建图G。（2）DestoryGraph

6、（G）：销毁图G。（3）LocateVertex（G，v）：确定顶点v在图G中的位置。若图G中没有顶点v，则函数值为“空”。（4）GetVertex（G，i）：取出图G中的第i个顶点的值。若i大于图G中顶点数，则函数值为“空”。7/25/20214第6章图（5）FirstAdjVertex（G，v）：求图G中顶点v的第一个邻接点。若v无邻接点或图G中无顶点v，则函数值为“空”。（6）NextAdjVertex（G，v，w）：已知w是图G中顶点v的某个邻接点，求顶点v的下一个邻接点（紧跟在w后面）。若w是v的最后一个邻

7、接点，则函数值为“空”。（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的每个结点访问一次且仅访问一次。7/25/20215第6章图完全图:对有n个结点的图，无向图:任意两结点都有一条边，即边数为:n(n-

8、1)/2，则称其为无向完全图；邻接结点:无向图:若（vi,vj）E，则称结点vi和vj互为邻接点；或称vi和vj相邻接；或称边（vi,vj）关联于结点vi和vj；或称边（vi,vj）与结点vi和vj相关联。有向图：若E,则称结点vj是vi的邻接点。2.基本概念7/25/20216第6章图结点的度：一个结点v的度是与它相关联的边的条数记作TD(v)。无向图：即为该结点相连的边的个数。有向图：依附在某结点的弧的数目。结点的入度：以该结点为弧头的弧的数目。是以v为终点的有向边的条数,记作ID(v);结点的出度

9、：以该结点为弧尾的弧的数目。是以v为始点的有向边的条数,记作OD(v)。有向图：任意两结点都有两条方向相反的弧，即弧数为n(n-1)，则称其为有向完全图。7/25/20217第6章图TD(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(

10、e)=1ID(f)=1OD(f)=0TD(f)=17/25/20218第6章图子图：设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。0123(a)G10123G1的子图012G1的子图0123G1的子图01201201212(b)G2G2的子图G2的子图G2的子图7/25/20219第6章图路径:在图G＝(V,E)中,若存在一个结点序列vp1,vp2,…,vpm，使得(vi,vp1)、(vp1,vp2)、...、(vpm,vj)均属于E，则称结点vi到vj存在一条路径。若一条

11、路径上除了vi和vj可以相同外，其余结点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。7/25/202110第6章图图的连通在无向图G中，若两个结点vi和vj之间有路径存在，则称vi和vj是连通的。若G中任意两个结点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。强连通