自考数据结构02142-第五章

第五章图•5.1图的基本概念•5.2图的存储结构•5.3图的遍历•5.4图的应用一、图的定义图G——是由集合V和E组成，记成G=（V，E）其中：V—顶点集（非空）；E—边集（可空）。边是顶点的有序对或无序对。（边反映了两顶点之间的关系）●有向图：边是顶点的有序对的图。（图中每条边都用箭头指明了方向）●无向图：边是顶点的无序对的图。5.1图的基本概念例：V(G1)={1，2，3，4}E(G1)={(1,2)，(1,3)，(1,4)，(2,3)，(2,4)，(3,4)}①②③④（图G1）（无向图）V(G2)={1，2，3，4，5，6，7}E(G2)={(1,2)，(1,3)，(2,4)，(2,5)，(3,6)，(3,7)}①②③④⑤⑥⑦（图G2）V(G3)={1，2，3}E(G3)={1,2，2,1，2,3}①②③（图G3）（有向图）注：1）边集可空；2）边集中不允许出现相同的边。二、图的基本术语●顶点(Vertex)——图中的数据元素；●Vi,Vj——有向图中,顶点Vi到顶点Vj的边,也称弧；弧头（终端点）：箭头端；弧尾（初始点）：无箭头端；●完全图——无向完全图：边数=n*(n-1)/2的无向图；有向完全图：边数=n*(n-1)的有向图；(顶点数n)●权——图的边附带的数值（可表示从一个顶点到另一顶点的距离、代价等）●子图——图G和G′,若有V(G′)V(G)和E(G′)E(G),则称G′为图G的子图。①②③④①（图G1）①②③（图G2）②③④（图G3）●邻接——若(Vi,Vj)∈E(G)，则称Vi和Vj互为邻接点;●关联——若(Vi,Vj)∈E(G)，则称边(Vi,Vj)关联于顶点Vi和Vj;注：1）邻接是指顶点之间的关系，而关联是指边与顶点间的关系。2）若弧Vi,Vj∈E(G)，则称Vj是Vi的邻接点●度—无向图：顶点Vi的度为与Vi相关联的边的个数；D(Vi)有向图出度:顶点Vi的出度为以Vi为尾的出边数；OD(Vi)入度:顶点Vi的入度为以Vi为头的入边数；ID(Vi)度:有向图的度=入度+出度；D(Vi)D(Vi)=OD(Vi)+ID(Vi)注：图中边数e与顶点的度的关系e=21∑ni=1D（Vi）（一边带二度，两度组成一边）●路径——图中，顶点Vp至顶点Vq的路径是顶点序列{Vp,Vi1,Vi2,…,Vin,Vq}且对无向图，边(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)∈VR(G);对有向图，弧Vp,Vi1,Vi1,Vi2,…,Vin,Vq∈VR(G);●路径长度——路径上边或弧的数目；●简单路径——序列中顶点不重复出现的路径；●回路—第一个和最后一个顶点相同的路径，也称环；●简单回路—除第一个和最后一个外，其余各顶点均不相同的回路；注：回路中可以有多个圈，而简单回路只能有一个圈。●连通——无向图中，若从顶点Vi到Vj顶点有路径，则称Vi和Vj是连通的。●连通图和连通分量针对无向图而言定义例无向图连通图连通分量图中每对顶点间都连通;Vi～Vj图中极大的连通子图（再扩大一点就不连通）①①②③②③④④⑤⑥⑦(G1)(G2)①⑤（G3不是连通②③⑥图，但它有两④⑦个连通分量）(G3)⑧有向图强连通图强连通分量图中任意一对顶点Vi和Vj都有顶点Vi到顶点Vj的路径，也有从vj到vi的路径，两个顶点间双向连通。有向图的极大强连通子图。①②③①①②④②④③③(G4)图G4的两个强连通分量生成树——含有该连通图的全部顶点的一个极小连通子图若连通图G的顶点个数为n，则G的生成树的边数为n-1。G的子图G’边数大于n-1,则G’中一定有环。G的子图G’边数小于n-1,则G’中一定不连通。生成森林——在非连通图中，每个连通分量都可得到一个极小连通子图，也就是生成树。这些生成树就组成了一个非连通图的生成森林。图的基本运算•建立图GreateGraph(G,V,E)•取顶点信息Getvex(G,u)•取边信息Getarc(G,u,v)•查询第一个邻接点FirstVex(G,u)•查询下一个邻接点NextVex(G,u,v)•插入顶点InsertVex(G,v)•删除顶点DeleteVex(G,v)•插入边InsertArc(G,v,w)•删除边DeleteArc(G,v,w)•遍历图Travers(G,tag)5.2.1邻接矩阵表示法5.2图的存储结构1、图的邻接矩阵——表示图的各顶点之间关系的矩阵。▲定义——设G=(V,E)是n个顶点的图，则G的邻接矩阵为下列n阶方阵：A[i][j]=1若(Vi,Vj)或Vi,Vj∈E(G)0否则G1=0111101011011010（图G1）①②③④①②③（图G2）010101000G2=▲例：▲结论：（1）无向图的邻接矩阵是对称的；（∵(Vi,Vj)∈E(G)，则(Vj,Vi)∈E(G)）（2）从邻接矩阵容易判断任意两顶点间是否有边相联；容易求出各顶点的度；无向图：顶点Vi的度D(Vi)=矩阵中第i行的1总和有向图：OD(Vi)=矩阵中第i行的1总和ID(Vi)=矩阵中第i列的1总和2、带权图(网)的邻接矩阵A[i][j]=wij若(Vi,Vj)或Vi,Vj∈E(G)∞Vi、Vj间无边或弧（Wij为边或弧的权）3、邻接矩阵的类型定义constintvnum=20;constintMAX_INT=32767;Typedefstructgp{VertexTypevexs[vnum];//顶点信息WeightTypearcs[vnum][vnum];//带权邻接矩阵intvexnum,arcnum;//顶点数，边数}WGraph;•将矩阵A的每个元素都初始化为最大值。•然后读入边和权值（i，j，wij），将A的相应元素设为wij。算法如下：4、建立无向带权邻接矩阵：VoidCreatGraph(Graph*g){inti,j,n,e,w;charch;scanf(“%d%d”,&n,&e);g-vexnum=n;g-arcnum=e;for(i=0;ig-vexnum;i++){scanf(“%c”,&ch);g-vexs[i]=ch;}for(i=0;ig-vexnum;i++)for(j=0;jg-vexnum;j++)g-arcs[i][j]=MAX_INT;for(k=0;kg-arcnum;k++){scanf(“%d%d%d”,&i,&j,&w);g-arcs[i][j]=w;g-arcs[j][i]=w;}}1.定义：对图G中每个顶点都建立一个单链表，第i个单链表（称边表）链接图中与顶点Vi相邻接的所有顶点。结点形式：邻接点域（顶点域）：存放与顶点Vi相邻接顶点Vj的序号j；链域：指向Vi的下一个邻接点；▲每个链表均设一表头结点（以向量存储，称顶点表）表头结点：vertexfirstarcV[i]—第i个链表的表头结点；V[i].vertex—存放顶点Vi的信息；V[i].firstarc—指向Vi的邻接链表的第一个结点。5.2.2邻接表表示法adjvexnextarc3.结论：1）n个顶点、e条边的无向图，则其邻接表的表头结点数为n，链表结点总数为2e；2）对于无向图，第i个链表的结点数为顶点Vi的度；对于有向图，第i个链表的结点数为顶点Vi的出度；3）在边稀疏时，邻接表比邻接矩阵省单元；4）邻接表表示在检测边数方面比邻接矩阵表示效率要高。2.例：（P136图5-10中G2的邻接表）（P137图5-11中G1的邻接表）V1V2V3V4V50123413∧02∧413∧41∧21∧2表头向量adjlistV1V2V3V4V5◆例：①②③V1V2V3∧012表头向量adjlist∧10∧24.邻接表的类型定义：#definevnum20Typedefstructarcnode{intadjvex;//下一条边的顶点编号WeightTypeweight;//带权图的权值域structarcnode*nextarc；//指向下一条边的指针}ArcNode;Typedefstructvexnode{intvertex;//顶点编号ArcNode*firstarc;//指向第一条边的指针}AdjList[vnum];Typedefstructgp{AdjListadjlist;intvexnum,arcnum;//顶点和边的个数}Graph;•对于无向图，第i个链表的结点数为顶点Vi的度；•对于有向图，第i个链表的结点数只为顶点Vi的出度；若要求入度，必须遍历整个邻接表。在单链表中，其邻接点域的值为i的结点个数是顶点Vi的入度。•对于有向图，有时候就要建立一个逆邻接表。即对每个顶点Vi建立一个以Vi为弧头的邻接点的链表。这样，逆邻接表第i个单链表中的结点个数就是Vi的入度。5.计算图的度例：图5-2中G1的邻接表和逆邻接表见P137图5-11结点形式：6.带权图邻接表adjvexweightnextarc权值域：用于存储边的权值画出图5-1a无向带权图的邻接表。图5-8a有向带权图的邻接表、逆邻接表。建立有向图的邻接表的方法：将邻接表表头数组初始化;第i个表头的vertex域初始化为i；first域初始化为NULL;读入顶点对i,j,产生一个表结点；将j放入到该结点的adjvex域；将该结点链到邻接表的表头数组的第i个元素的first域上。建立有向图的邻接表算法见P1385.3图的遍历▲遍历的含义及方法：●图的遍历——从图G中某一顶点v出发，顺序访问各顶点一次。●方法：深度优先搜索法广度优先搜索法为克服顶点的重复访问，设立辅助数组visited[n]。1顶点i已被访问过0顶点i未被访问过visited[i]=遍历方法5.3.1深度优先搜索法（DFS）一、过程从图G(V,E)中任一顶点Vi开始，首先访问Vi，然后访问Vi的任一未访问过的邻接点Vj，再以Vj为新的出发点继续进行深度优先搜索，直到所有顶点都被访问过。二、例：三、算法：▲分析：a、为克服顶点的重复访问，设立一标志向量visited[n];b、图可用邻接矩阵或邻接表表示；从V1出发,DFS:V1，V2，V4，V5，V3，V6V4V1V2V3V5V6注意：•搜索到达某个顶点时(图中仍有顶点未被访问)，如果这个顶点的所有邻接点都被访问过，那么搜索就要回到前一个被访问过的顶点，再从该顶点的下一未被访问的邻接点开始深度优先搜索。；•深度搜索的顶点的访问序列不是唯一的。连通图的深度优先搜索的算法:Dfs(Graphg,intv){访问v；visited[v]=1;//visited[v]初值都为0，顶点v已被访问，就置为1找出g中v的第一个邻接点w；while(w存在){ifw未被访问Dfs(g,w);w=g中v的下一个邻接点；}}▲深度优先搜索法算法：▲对图按深度优先遍历的递归算法（邻接表）：intvisited[N]=0;/*对访问标记visited数组初始化*/Dfs(Graphg,intv){//从第v个顶点出发递归地深度优先遍历图g，图以邻接表作为存储结构ArcNode*p;printf(“%d”,v);/*访问起始顶点v*/visited[v]=1;/*置“已访问”标记*/p=g.adjlist[v].firstarc;/*取顶点表中v的边表头指针*/while(p!=NULL)/*依次搜索v的邻接点*/{if(!visited[p-adjvex])/*v的一个邻接点未被访问*/Dfs(g,p-adjvex);/*沿此邻接点出发继续DFS*/p=p-nextarc;/*取v的下一个邻接点*/}}V0V1V2V3V4V5V6V7V0V1V2V3V4V5V6V70123456712∧03∧405∧61∧71∧72∧62∧53∧4表头向量adjlist从V0出发,深度优先搜索:V0，V1，▲深度优先搜索法算法：▲对图按深度优先遍历的递归算法（邻接矩阵）：intvisited[N]=0;/*对访问标记visited数组初