数据结构(C语言描述)图.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构(C语言描述)图.ppt》由会员分享,可在线阅读,更多相关《数据结构(C语言描述)图.ppt(28页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、图 图(Graph)是一种较线性表和树更为复杂的非线性结构。在线性结构中,结点之间的关系是线性关系,除开始结点和终端结点外,每个结点只有一个直接前趋和直接后继。在树形结构中,结点之间的关系实质上是层次关系,同层上的每个结点可以和下一层的零个或多个结点(即孩子)相关,但只能和上一层的一个结点(即双亲)相关(根结点除外)。然而在图结构中,对结点(图中常称为顶点)的前趋和后继个数都是不加限制的,即结点之间的关系是任意的。图中任意两个结点之间都可能相关。由此,图的应用极为广泛,特别是近年来的迅速发展,已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。基本定义和术语 若图
2、G中的每条边都是有方向的,则称G为有向图有向图(Digraph)。在有向图中,一条有向边是由两个顶点组成的有序对,有序对通常用尖括号表示。例如,vi,vj表示一条有向边,vi是边的始点(起点),vj是边的终点。因此,vi,vj和vj,vi是两条不同的有向边。有向边也称为弧(Arc),边的始点称为弧尾(Tail),终点称为弧头(Head)。图图G由两个集合V和E组成,记为G(V,E),其中v是顶点的有穷非空集合,E是V中顶点偶对(称为边)的有穷集。通常,也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集,若E(G)为空,则图G只有顶点而没有边,称为空图。若(vi,vj)是一条无
3、向边,则称顶点vi和vj互为邻接点邻接点(Adjacent),或称vi和vj相邻接;称(vi,vj)关联(Incident)于顶点vi和vj,或称(vi,vj)与顶点vi和vj相关联相关联。如图7-1中G2,与顶点vl相邻接的顶点是v2,v3和v4,而关联于顶点v2的边是(vl,v2),(v2,v3)和(v2,v4)。若vi,vj是一条有向边,则称顶点vi邻接到vj,顶点vj邻接于顶点vi,并称边vi,vj关联于vi和vj或称vi,vj与顶点vi和vj相关联。如图7-1中Gl,关联于顶点v2的边是v1,v2,v2,vl和v2,v3。无向图中顶点v的度度(Degree)是关联于该顶点的边的数目,
4、记为D(v)。若G为有向图,则把以顶点v为终点的边的数目,称为v的人度人度(1ndegree),记为ID(v);把以顶点v为始点的边的数目,称为v的出度出度(outdegree),记为OD(v);顶点v的度则定义为该顶点的入度和出度之和,即D(v)ID(v)十OD(v)。在无向图G中,若存在一个顶点序列vp,vi1,vi2,vin,vq,使得(vp,vil),(vi1,vi2),(vin,vq)均属于E(G),则称顶点vp到vq存在一条路径路径(Path)。若G是有向图,则路径也是有向的,它由E(G)中的有向边vp,vil,vil,vi2,vin,vq组成。路径长度路径长度定义为该路径上边的数
5、目。若一条路径上除了vp和vq可以相同外;其余顶点均不相同,则称此路径为一条简单路径简单路径。起点和终点相同(vpvq)的简单路径称为简单回路简单回路或简单简单环环(Cycle)。例如,在图G2中顶点序列vl,v2,v3,v4是一条从顶点vl到顶点v4的长度为3的简单路径;顶点序列vl,v2,v4,vl,v3是一条从顶点vl到顶点v3的长度为4的路径,但不是简单路径;顶点序列vl,v2,v4,vl是一个长度为3的简单环。在有向图Gl中,顶点序列vl,v2,vl是一个长度为2的有向简单环。在一个有向图中,若存在一个顶点v,从该顶点有路径可以到达图中其它所有顶点,则称此有向图为有根图有根图,v称作
6、图的根根。在无向图G中,若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径),则称vi和vj是连通连通的。若V(G)中任意两个不同的顶点vi和vj都连通(即有路径),则称G为连通图连通图(Connected Graph)。例如,图G2和G3是连通图。无向图G的极大连通子图称为G的连通分量连通分量(connected Component)。显然,任何连通图的连通分量只有一个,即是其自身,而非连通的无向图有多个连通分量。例如,图7-4中的G4是非连通图,它有两个连通分量Hl和H2。在有向图G中,若对于V(G)中任意两个不同的顶点vi和vj,都存在从vi到vj以及从vj到vi的路径,则称G是
7、强连通图强连通图。有向图G的极大强连通子图称为G的强连通分量强连通分量。显然,强连通图只有一个强连通分量,即是其自身。非强连通的有向图有多个强连通分量。例如图7-1中的Gl不是强连通图,因为v3到v2没有路径,但它有两个强连通分量,若将图的每条边都赋上一个权,则称这种带权图为网网络络(Network)。通常权是具有某种意义的数.它们可以表示两个顶点之间的距离,耗费等 图的存储结构 邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:用邻接矩阵表示法表示图,除了存储用于表示顶点间相邻关系的邻接矩阵外,
8、通常还需要用一个顺序表来存储顶点信息。其形式说明如下:#define n 6 /*图的顶点数*/#define e 8 /*图的边(弧)数*/typedef char vextype;/*顶点的数据类型*/typedef float adjtype;/*权值类型*/typedef structvextype vexsn;adjtype arcsnn;graph;若图中顶点信息是0至n-1的编号,则仅需令权值为1,存储一个邻接矩阵就可以表示图。若是网络,则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对称的,故可采用压缩存储的方法,仅存储下三角阵(不包括对角线上的元素)中的元素即可。
9、显然,邻接矩阵表示法的空间复杂度S(n)O(n2)。CREATGRAPH(ga)*建立无向网络*Graph*ga;int i,j,k;float w;for(i0;in;i+)ga-vexsigetchar();*读入顶点信息,建立顶点表*for(i0;in;i+)for(j0;jn;j+)ga-arcsij0;*邻接矩阵初始化*for(k0;ke;k+)*读入e条边*(scanf(”ddf”,&I,&j,&w);*读入边(vi,vj)上的权w*ga-arcsijw;ga-arcsjiw;*CREATGRAPH*该算法的执行时间是O(n+n2+e),其中O(n2)的时问耗费在邻接矩阵的初始化操
10、作上。因为en2,所以,算法的时间复杂度是O(n2)。邻接表 这种表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi,该方法把所有邻接于vi的顶点vj链成一个单链表,这个单链表就称为顶点vi的邻接表(Adjacency List)。邻接表中每个表结点均有两个域,其一是邻接点域(Adjvex),用以存放与vi相邻接的顶点vj的序号;其二是链域(Next),用来将邻接表的所有表结点链在一起。并且为每个顶点vi的邻接表设置一个具有两个域的表头结点:一个是顶点域(vertex),用来存放顶点vi的信息;另一个是指针域(Link),用于存入指向vi的邻接表中第一个表结点的头指针。为了便于随机访问任
11、一顶点的邻接表,将所有邻接表的表头结点顺序存储在一个向量中,这样,图G就可以由这个表头向量来表示。建立有向图的邻接表与此类似,只是更加简单,每读入一个顶点对序号i,j时,仅需生成十个邻接点序号为j的边表结点,将其插入到vi的出边表头部即可。若建立网络的邻接表,则需在边表的每个结点中增加一个存储边上权的数据域。值得注意的是,一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一,这是因为邻接表表示中,各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。邻接矩阵和邻接表是图的两种最常用的存储结构,它们各有所长。下面从空间及执行某些常用操作的时间这两方面来作一比较。在邻接表(或逆邻接表)表示中,
12、每个边表对应于邻接矩阵的一行(或一列),边表中结点个数等于一行(或一列)中非零元素的个数。对于一个具有n个顶点e条边的图G,若G是无向图,则它的邻接表表示中有n个顶点表结点和2e个边表结点;若G是有向图,则它的邻接表表示或逆邻接表表示中均有n个顶点表结点和e个边表结点。因此邻接表或逆邻接表表示的空间复杂度为S(n,e)O(n+e)。若图中边的数目远远小于n2(即en2),此类图称作稀疏图(Sparse Graph),这时用邻接表表示比用邻接矩阵表示节省存储空间;若e接近于n2(准确地说,无向图e接近于n(n-1)2,有向图e接近于n(n-1),此类图称作稠密图(Dense Graph),考虑到
13、邻接表中要附加链域,则应取邻接矩阵表示法为宜。在无向图中求顶点的度,邻接矩阵及邻接表两种存储结构都很容易做到:邻接矩阵中第i行(或第i列)上非零元素的个数即为顶点vi的度;在邻接表表示中,顶点vi的度则是第i个边表中的结点个数。在有向图中求顶点的度。采用邻接矩阵表示比邻接表表示更方便:邻接矩阵中的第i行上非零元素的个数是顶点vi的出度OD(vi),第i列上非零元素的个数是顶点vi的入度ID(vi),顶点vi的度即是二者之和;在邻接表表示中,第i个边表(即出边表)上的结点个数是顶点vi的出度,求vi的入度较困难,需遍历各顶点的边表。若有向图采用逆邻接表表示,则与邻接表表示相反,求顶点的入度容易,
14、而求顶点出度较难。在邻接矩阵表示中,很容易判定(vi,vj)或vi,vj是否是图的一条边,只要判定矩阵中的第i行第j列上的那个元素是否为零即可;但是在邻接表表示中,需扫描第i个边表,最坏情况下要耗费O(n)时间。在邻接矩阵中求边的数目e,必须检测整个矩阵,所耗费的时间是0(n2),与e的大小无关;而在邻接表表示中,只要对每个边表的结点个数计数即可求得e,所耗费的时间是0(e+n)。因此,当en2时,采用邻接表表示更节省时间。图的遍历 和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图,则从图中任一顶点出发顺着边可以访问到该图的所有顶点。然
15、而,图的遍历比树的遍历复杂得多,这是因为图中的任一顶点都可能和其余顶点相邻接,故在访问了某个顶点之后,可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点,必须记住每个顶点是否被访问过。为此,可设置一个布尔向量visitedn,它的初值为false,一旦访问了顶点vi,便将visitedi-1置为TRUE。深度优先搜索(Depth-First-Search)遍历类似于树的前序遍历。假设给定图G的初态是所有顶点均未访问过,在G中任选一顶点vi为初始出发点,则深度优先搜索可定义如下:首先,访问出发点vi,并将其标记为已访问过,然后,依次从vi出发搜索vi的每一个邻接点vj,若vj未曾访问过,
16、则以vj为新的出发点继续进行深度优先搜索。显然上述搜索法是递归定义的,它的特点是尽可能先对纵深方向进行搜索,故称之为深度优先搜索。例如,设x是刚访问过的顶点,按深度优先搜索方法,下一步将选择一条从x出发的未检测过的边(x,y)。若发现顶点y已被访问过,则重新选择另一条从x出发的未检测过的边。若发现顶点y未曾访问过,则沿此边从x到达y,访问y并将其标记为已访问过,然后从y开始搜索,直到搜索完从y出发的所有路径,才回溯到顶点x,然后再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时,若x不是初始出发点,则回溯到在x之前被访问过的顶点;若x是初始出发点,则整个搜索过程
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言 描述
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内