第7章-图

第7章图1第７章图本章知识点：图的基本概念图的存储结构图的遍历方法图的生成树，最小生成树算法图的顶点之间的最短路径有向无环图的拓扑排序与关键路径第7章图在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据可能和下一层中多个元素相关，但只能和上一层中一个元素相关；在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。图是一种较线性表和树更为复杂的数据结构第7章图•基本术语–有向图：因为图中的“弧”是有方向的，所以称由顶点集V和弧集VR构成的图为有向图。–无向图：如果v,wVR必有w,vVR，则用无序对(v,w)代替这两个有序对，表示v和w之间的一条边，此时的图称为无向图。7.1图的定义和术语第7章图有向图G1=(V1,{A1})其中：V1={v1,v2,v3,v4}A1={v1,v2,v1,v3,v3,v4,v4,v1}无向图G2=(V2,{E2})其中：V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}3无向图G24512v1v2v4v3有向图G1例如：第7章图–若n个顶点的无向图中有n(n-1)/2条边，则称无向完全图。–若n个顶点的有向图中有n(n-1)条边，则称有向完全图。–若图中有很少的边或弧，则称该图为稀疏图，反之称该图为稠密图。–与图中的边或弧相关的数称为权，带权的图称为网。–假设有两个图G=V,{E}和G’=V’,{E’}，如果V’V且E’E，则称G’为G的子图。beadcbadc第7章图–对于无向图G=(V,{E})，如果边(v,v’)E，•则称顶点v和v’互为邻接点，•边(v,v’)依附于顶点v和v’，或者说(v,v’)和顶点v和v’相关联。•顶点v的度是和v相联的边的数目，记为TD(v)。3无向图G24512第7章图–对于有向图G=(V,{A})，如果弧v,v’A，•则称顶点v邻接到顶点v’，顶点v’邻接自顶点v。•以顶点v为头的弧的数目称为顶点v的入度，记为ID(v)；•以v为尾的弧的数目称为v的出度，记为OD(v)；•顶点v的度数为TD(v)=ID(v)+OD(v)。如果图G有n个顶点和e条边或弧，则有下列等式成立：niivTDe1)(213无向图G24512第7章图–无向图G=(V,{E})中顶点v和顶点v’之间的路径为一个顶点序列(v=vi,0，vi,1，…，vi,m=v’)，•其中(vi,j-1，vi,j)E，1jm。–有向图G=(V,{A})中顶点v和顶点v’之间的路径为一个顶点序列(v=vi,0，vi,1，…，vi,m=v’)，•其中vi,j-1，vi,jA，1jm。第7章图–在无向图G中，如果两个顶点之间有一条路径，则称这两个顶点是连通的。–如果对于图中任意两个顶点之间都是连通的，则称该图为连通图，否则称为非连通图。–无向图中的极大连通子图称为连通分量。–连通图只有一个连通分量，就是它本身，而非连通图有多个连通分量。–在有向图G中，如果任意两对顶点之间都有路径相通，则称强连通图。有向图中的极大强连通子图称为有向图的强连通分量。beadcbeadc第7章图–路径上边或弧的数目称路径长度。–第一个顶点和最后一个顶点相同的路径称回路或环。–序列中顶点不重复出现的路径称简单路径。–除了第一个顶点和最后一个顶点相同之外，其余顶点不重复出现的回路，称为简单回路或简单环。第7章图–一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。注意：有n-1条边的图不一定是生成树。–只有一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树。–一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵互不相交的有向树的弧。fabecdfdacbebeadcbadce第7章图例213213有向完备图无向完备图356例245136图与子图例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：4第7章图例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1第7章图连通图例245136强连通图356例非连通图连通分量例245136第7章图7.2图的存储结构•数组（邻接矩阵）表示法用两个数组分别存储元素（顶点）的信息（一维数组）和数据元素之间的关系（边或弧）（二维数组）的信息。例如：下面给出三个图及其对应的邻接矩阵。0110000000011000A=v3v4v1v2，其它0E(G)v,v或)v,(v若1,],[jijijiA第7章图v3v4v5v1v20101010101010111010001100A=∞963∞9∞45∞64∞∞735∞∞8∞∞78∞A=V1V2V3V4V59635487第7章图#defineMaxVertexNuml00/*最大顶点数，应由用户定义*/typedefcharVertexType；/*顶点类型应,由用户定义*/typedefintEdgeType；/*边上的权值类型应由用户定义*/typedefstruct{VextexTypevexs[MaxVertexNum]/*顶点表*/EdgeTypeedges[MaxVertexNum][MaxVertexNum];/*邻接矩阵，可看作边表*/intn，e；/*图中当前的顶点数和边数*/}MGragh；•图的数组存储表示第7章图建立带权无向图邻接矩阵的算法•voidCreate_MGraph(MGraph*G1)•//{/*建立无向网的邻接矩阵表示*/inti,j,k,w;scanf(“%d,%d”，&G1-n,&G1-e)；/*输入顶点数和边数*/for(i=0;iG1-n；i++)/*读人顶点信息，建立顶点表*/G1-vexs[i]=getchar()；for(i=0；iG1-n；i++)for(j=0；jG1-n；j++)G1-edges[i][j]=0；/*邻接矩阵初始化*/for(k=0；kG1-e；k++){/*读入e条边，建立邻接矩阵*/scanf(“％d％d％d”，&i，&j，&w)；/*输入边(vi,vj)上的权w*/G1-edges[i-1][j-1]=w；G1-edges[j-1][i-1]=w；}}/*Create_MGraph*/v3v4v5v1v2第7章图•邻接矩阵的特点①无向图(网)的关系矩阵一定是对称矩阵，可以采用压缩存储方式只存入矩阵的下三角（或上三角）元素。②无向图(网)的关系矩阵的第i行(或第i列)非零元素个数为第i个顶点的度D(vi)。③有向图的关系矩阵的第i行非零元素个数为第i个顶点的出度OD(vi)，第i列非零元素个数为第i个顶点的入度ID(vi)。④在图的邻接矩阵中很容易确定图中任意两个顶点间是否有边或弧相连。⑤除了两个数组之外，还需要保存图的类型（有向图、无向图、有向网、无向网）、顶点数、弧或边的个数。第7章图•邻接表:–对图中每个顶点建立一个单链表，–第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。–表中每个结点有三个域组成•其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，•链域(nextarc)指示下一条边或弧的结点；•数据域(info)存储和边或弧相关的信息。–每个链表上附设一个表头结点。–在表头结点中除了设有链域(firstarc)指向链表中第一个结点之外，还设有存储顶点vi的名字或其它有关信息的数据域(data)。边顶点adjvexnextarcinfodatafirstarc•邻接表一种链式存储结构第7章图例G1bdac例aecbdG21234acdbvexdatafirstarc3241^^^^adjvexnext1234acdbvexdatafirstarc4212^^^adjvexnext5e435^15323^第7章图注意：①如果无向图有n个顶点e条边，则它的邻接表需要n个头结点和2e个表结点。见P164中图G2②无向图的邻接表中，顶点vi的度恰为第i个单链表中的结点数；③有向图的邻接表中，顶点vi的出度恰为第i个单链表中的结点数。④在有向图的邻接表中求某个顶点的入度需要遍历整个邻接表。有时为了便于确定顶点的入度或以顶点vi为头的弧，可以建立该图的逆邻接表。⑤在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的时间复杂度为O(n+e)，否则为O(ne)。第7章图typedefstructnode{/*边表结点*/intadjvex；/*邻接点域*/intinfo;structnode*nextedge；/*链域*//*若要表示边上的权，则应增加一个数据域info*/}EdgeNode;typedefstructvnode{/*顶点表结点*/VertexTypevertex；/*顶点域*/EdgeNode*firstedge；/*边表头指针*/}VertexNode；图的邻接表存储结构可形式地说明如下：第7章图typedefVertexNodeAdjList[MaxVertexNum]；/*AdjList是邻接表类型*/typedefstruct{VertexNodeadjlist[MaxVertexNum];//AdjListadjlist；/*邻接表*/intn，e；//图中当前顶点数和边数*/intkind;/*图的种类标志*/}ALGraph；/*对于简单的应用，无须定义此类型，可直接使用AdjList类型。*/第7章图•voidCreateALGraPh(ALGrahp*G1){/*建立无向图的邻接表表示*/inti，j，k；EdgeNode*s；scanf(％d％d，&G1-n，&G1-e)；/*读入顶点数和边数*/for(i=0；iG1-n；i++){/*建立顶点表*/G1-adjlist[i].vertex=getchar()；/*读入顶点信息*/G1-adjlist[i].firstedge=NULL；/*边表置为空表*/}接下页类似于邻接矩阵，可以得到建立无向图的邻接表算法如下：第7章图for(k=0；kG1-e；k++){/*建立边表*/scanf(％d％d，&i,&j)；读入边(vi，vj)的顶点对序号*/s=(EdgeNode*)malloc(sizeof(EdgeNode))；/*生成边表结点*/s-adjvex=j;/*邻接点序号为j*/s-next=G1-adjlist[i].firstedge；G1-adjlist[i].firstedge=s；/*将新结点*s插入顶点vi的边表头部*/s=(EdgeNode*)malloc(sizeof(EdgeNode))；s-adjvex=i;/*邻接点序号为i*/s-nextedge=G1-adjlist[j].firstedge；G1-adjlistk[j].firstedge=s；/*将新结点*s插入顶点vj的边表头部*/}/*endfor*/}/*endCreateALGraph*/第7章图1.已知如图所示的有向图，请给出该图的:顶点123456入度出度1).每个顶点的入/出度；2).邻接矩阵；3).邻接表；第7章图7.3图的遍历•图的遍历–从图中某个顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。。•特点：–在访问了某个顶点之后，可能沿着某条路径搜索又回到该顶点上。–例如，因为右上图中存在回路，所以