资源描述
第 7 章 图一、基础知识题 7.1设无向图的顶点个数为n，则该图最多有多少条边？【解答】n(n-1)/27.2一个n个顶点的连通无向图，其边的个数至少为多少？【解答】n-1 7.3要连通具有n个顶点的有向图，至少需要多少条弧?【解答】n7.4 n个顶点的完全有向图含有弧的数目是多少?【解答】n(n-1)7.5一个有n个顶点的无向图，最少有多少个连通分量，最多有多少个连通分量。【解答】1, n7.6图的BFS生成树的树高要小于等于同图DFS生成树的树高，对吗？【解答】对7.7无向图G=(V,E)，其中：V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，写出对该图从顶点a出发进行深度优先遍历可能得到的全部顶点序列。【解答】abedfc, acfdeb, aebdfc, aedfcb7.8 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度是多少？【解答】O(n+e)7.9若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有多少棵树？【解答】n-e7.10 n个顶点的无向图的邻接矩阵至少有多少非零元素？【解答】07.11证明:具有n个顶点和多于n-1条边的无向连通图G一定不是树。【证明】具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。7.12证明对有向图顶点适当编号，使其邻接矩阵为下三角形且主对角线为全零的充要条件是该图是无环图。【证明】该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素（Aij=1）自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。（对该类有向无环图顶点编号，应按顶点出度的大小进行顺序编号。）7.13设G=(V，E)以邻接表存储，如图所示，试画出从顶点1出发所得到的深度优先和广度优先生成树。 习题7.13 的图【解答】深度优先生成树12345宽度优先生成树：123457.14 已知一个图的顶点集V和边集E分别为：V=0，1，2，3，4，5，6，7；E=，；若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照顶点序号从小到大的次序链接的，则按教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列。【解答】1-3-6-0-2-5-4-7-8 7.15一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。 习题7.15 的图 习题7.16 的图【解答】设顶点集合为1，2，3，4，5，6， 由下边的逻辑图可以看出，在1，2，3和4，5，6回路中，各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。121111131234567.16如图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：（1）该带权有向图的图形；（2）从顶点V1为起点的广度优先遍历的顶点序列及对应的生成树；（3）以顶点V1为起点的深度优先遍历生成树；（4）由顶点V1到顶点V3的最短路径。333625181029383042143265【解答】(1) (2)V1,V2,V4,V6,V3,V5124635(3) 顶点集合V(G)=V1,V2,V3,V4,V5,V6 边的集合 E(G)=,(4) V1到V3最短路径为67: (V1V4V3) 迭代 集合 S选择顶点 D D2 D3 D4 D5 D6初值 v1 33 29 251v1, v6v6 33 29 252 v1, v6, v4v433 67 29 71 3 v1, v6, v4, v2v233 67 71 4v1,v6, v4, v2,v3v3 67 71 5v1,v6,v4, v2,v3,v5v 717.17已知一有向网的邻接矩阵如下，如需在其中一个顶点建立娱乐中心，要求该顶点距其它各顶点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程。习题7.18的图 习题7.17 的图【解答】下面用FLOYD算法求出任意两顶点的最短路径（如图A（6）所示）。题目要求娱乐中心“距其它各结点的最长往返路程最短”，结点V1，V3，V5和V6最长往返路径最短都是9。按着“相同条件下总的往返路径越短越好”，选顶点V5，总的往返路径是34。A(0)= A(1)= A(2)= A(3)= A(4)= A(5)= A(6)= 7.18求出图中顶点1到其余各顶点的最短路径。【解答】本表中DIST中各列最下方的数字是顶点1到顶点的最短通路。 所选顶点S（已确定最短路径的顶点集合）T(尚未确定最短路径的顶点集合) DIST2345678初态12,3,4,5,6,7,83060105 1,52,3,4,6,7,82560101761,5,62,3,4,7,8 203360172521,5,6,23,4,7,82033602571,5,6,2,73,4,83128253541,5,6,2,7,43,831283531,5,6,2,7,4,35,8313581,5,6,2,7,4,3,8835顶点1到其它顶点的最短路径依次是20，31，28，10，17，25，35。按Dijkstra算法所选顶点依次是5，6，2，7，4，3，8。 7.19对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（vi）和vl (vi)的函数值，列出各条关键路径。【解答】顶点ABCDEFGHWVe(i)016342413392252Vl(i)02924373113392252活动a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16a17e(i)000016633424131313392222l(i)281803292431343731203613392240aCFHGW，长52。 关键路径是： 活动与顶点的对照表：a1 a2 a3 a4 a5 a6 a7 a8a9 a10 a11 a12 a13 a14 a15 a16 a177.20 利用弗洛伊德算法，写出如图所示相应的带权邻接矩阵的变化。3214596823110【解答】A0= A1= A2= A3= A4= 二、算法设计题7.21 设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。void CreatGraph (AdjList g)建立有n个顶点和m 条边的无向图的邻接表存储结构int n,m; scanf(%d%d,&n,&m);for(i=0,in;i+)输入顶点信息,建立顶点向量 scanf(&gi.vertex); gi.firstarc=null;for(k=0;kadjvex=j; p-next=gi.firstarc; gi.firstarc=p; 将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=i;p-next=gj.firstarc;gj.frstarc=p;for 算法CreatGraph结束7.22 已知有向图有n个顶点，请编写算法，根据用户输入的偶对建立该有向图的邻接表。void CreatAdjList(AdjList g)建立有向图的邻接表存储结构int n;scanf(%d,&n);for(i=0;iadjvex=j;p-next=gi.firstarc;gi.firstarc=p;scanf(&v1,&v2);while 7.23 给出以十字链表作存储结构，建立图的算法，输入(i，j，v)其中i，j为顶点号，v为权值。void CreatOrthList(OrthList g)建立有向图的十字链表存储结构int i,j,v; 假定权值为整型scanf(%d,&n);for(i=0,iheadvex=j;p-tailvex=i;p-weight=v;弧结点中权值域 p-headlink=gj.firstin; gj.firstin=p; p-tailink=gi.firstout; gi.firstout=p;scanf(%d%d%d,&i,&j,&v);while 算法结束算法讨论 本题已假定输入的i和j是顶点号,否则,顶点的信息要输入,且用顶点定位函数求出顶点在顶点向量中的下标。图建立时，若已知边数（如上面1和2题），可以用for循环；若不知边数，可用while循环（如本题），规定输入特殊数（如本题的零值）时结束运行。本题中数值设为整型，否则应以和数值类型相容的方式输入。7.24 设有向图G有n个点(用1，2，n表示)，e条边，写一算法根据G的邻接表生成G的反向邻接表，要求算法时间复杂性为O(n+e)。void InvertAdjList(AdjList gin,gout)将有向图的出度邻接表改为按入度建立的逆邻接表 for(i=0;in;i+)设有向图有n个顶点，建逆邻接表的顶点向量。 gini.vertex=gouti.vertex; gini.firstarc=null; for(i=0;iadjvex; s=(ArcNode *)malloc(sizeof(ArcNode);申请结点空间 s-adjvex=i; s-next=ginj.firstarc; ginj.firstarc=s; p=p-next;下一个邻接点。 while for 7.25 写出从图的邻接表表示转换成邻接矩阵表示的算法。void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)将图的邻接表表示转换为邻接矩阵表示for(i=0;in;i+) 设图有n个顶点，邻接矩阵初始化 for(j=0;jn;j+) gmij=0; for(i=0;iadjvex=1;p=p-next; for 算法结束7.26 试写出把图的邻接矩阵表示转换为邻接表表示的算法。void AdjMatrixToAdjList(AdjMatrix gm, AdjList gl)将图的邻接矩阵表示转换为邻接表表示for(i=0;in;i+) 邻接表表头向量初始化。 scanf(&gli.vertex); gli.firstarc=null; for(i=0;in;i+) for(j=0;jadjvex=j;顶点I的邻接点是jp-next=gli.firstarc; gli.firstarc=p; 链入顶点i的邻接点链表中if end7.27 试编写建立有n个顶点，m条边且以邻接多重表为存储结构表示的无向图的算法。void CreatMGraph(AdjMulist g)建立有n个顶点e条边的无向图的邻接多重表的存储结构int n,e;scanf(%d%d,&n,&e); for(i=0,in;i+) 建立顶点向量 scanf(&gi.vertex);gi.firstedge=null; for(k=0;kivex=i; p-jvex=j; p-ilink=gi.firstedge; p-jlink=gj.firstedge;gi.firstedge=p; gj.firstedge=p;for 算法结束7.28 已知某有向图（n个结点）的邻接表，求该图各结点的入度数。【题目分析】在有向图的邻接表存储结构中求顶点的入度，需要遍历整个邻接表。void Indegree(AdjList g)求以邻接表为存储结构的n个顶点有向图的各顶点入度for(i=0;in;j+)num=0;入度初始为0for(j=0;jadjvex=i) num+; p=p-next; printf(“顶点%d的入度为：%dn”,gi.vexdata,num); 设顶点数据为整型 7.29 已知无向图G=(V，E)，给出求图G的连通分量个数的算法。【题目分析】使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。void dfs (v)visitedv=1; printf (“%3d”,v); 输出连通分量的顶点。p=gv.firstarc;while(p!=null) if（visitedp-adjvex=0） dfs(p-adjvex); p=p-next;while dfs void Count() 求图中连通分量的个数 int k=0 ; static AdjList g ; 设无向图g有n个结点 for(i=0;iadjvex=j) if(pre=null)gi.firstarc=p-next; else pre-next=p-next; free(p);释放空间 else pre=p; p=p-next; 沿链表继续查找p=gj.firstarc; pre=null; 删顶点j 的边结点(j,i)while(p) if(p-adjvex=i) if(pre=null)gj.firstarc=p-next; else pre-next=p-next; free(p);释放空间 else pre=p; p=p-next; 沿链表继续查找 DeletEdge【算法讨论】 算法中假定给的i，j 均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。7.31 假设有向图以邻接表存储，试编写算法删除弧的算法。void DeleteArc（AdjList g,vertype vi,vj） 删除以邻接表存储的有向图g的一条弧，假定顶点vi和vj存在i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); 顶点定位 p=gi.firstarc; pre=null;while(p) if(p-adjvex=j) if(pre=null) gi.firstarc=p-next;else pre-next=p-next;free(p);释放结点空间 else pre=p; p=p-next;结束7.32 设计一个算法利用遍历图的方法判别一个有向图G中是否存在从顶点Vi到Vj的长度为k的简单路径，假设有向图采用邻接表存储结构。【题目分析】本题利用深度优先递归的搜索方法判断有向图G的顶点i到j是否存在长度为k的简单路径，先找到i的第一个邻接点m，再从m出发递归的求是否存在m到j的长度为k-1的简单路径。int existpathlen(AlGraph G,int i,int j,int k) /判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 if(i=j&k=0) return 1; /找到了一条路径,且长度符合要求 else if(k0) visitedi=1; for(p=G.verticesi.firstarc;p;p=p-next) m=p-adjvex; if(!visitedm) if(existpathlen(G,m,j,k-1) return 1; /剩余路径长度减一 visitedi=0; /本题允许曾经被访问过的结点出现在另一条路径中 return 0; /没找到 7.33 设有向图G采用邻接矩阵存储，编写算法求出G中顶点i到顶点j的不含回路的、长度为k的路径数。int GetPathNum(AdjMatrix GA,int i,int j,int k,int n) /求邻接矩阵方式存储的有向图G的顶点i到j之间长度为k的简单路径条数/n为顶点个数 if(i=j&k=0) return 1; /找到了一条路径,且长度符合要求 else if(k0) sum=0; /sum表示通过本结点的路径数 visitedi=1; for(k=0;k0 | p) p=gstop.firstarc; 第一个邻接点 while(p!=null & visitedp-adjvex=1) p=p-next; 下一个访问邻接点表 if(p=null) top-; 退栈 else i=p-adjvex; 取邻接点（编号） if(i=v) 找到从u到v的一条简单路径，输出 for(k=1;k=top;k+)printf( %3d,sk); printf( %3dn,v);if else visitedi=1; s+top=i; else深度优先遍历 else while AllSPdfs7.35 以邻接表作存储结构，编写拓扑排序的算法。7.36 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（ij）。【题目分析】从Vi深度优先遍历,若在未退出深度优先遍历时遍历到Vj，说明Vi间Vj存在路径int visitedn; 设有向图有n个顶点int Pathitoj(AdjList g,int Vi,int Vj) 判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径if(Vi=Vj) return 1; Vi到顶点Vj存在路径 elsevisitedVi=1; for(p=gVi.firstarc;p;p=p-next) k=p-adjvex; if(!visitedk & Pathitoj(g,k, Vj) return 1; for return 0; Vi到顶点Vj不存在路径else 结束 【算法讨论】若顶点vi和vj 不是编号，必须先用顶点定位函数,查出其在邻接表顶点向量中的下标。下面再对本题用非递归算法求解如下。 int Connectij (AdjList g , vertype Vi , Vj ) 判断n个顶点以邻接表表示的有向图g中，顶点 Vi 各Vj 是否有路径，有则返回1，否则返回0for(i=1;i0)k=stacktop-; p=gk.firstarc;while(p & visitedp-adjvex=1) p=p-next;查第k个链表中第一个未访问的弧结点 if(p=null) top-; else i=p-adjvex;if(i=j) return(1); 顶点Vi和Vj 间有路径else visitedi=1; stack+top=i;else whilereturn(0); 顶点Vi和Vj间无通路 7.37假设有向图G以十字链表形式存储，试写一个判断该有向图中是否有环路（回路）的算法。【题目分析】有几种方法判断有向图是否存在环路，这里使用拓扑排序法。对有向图的顶点进行拓扑排序，若拓扑排序成功，则无环路；否则，存在环路。题目已假定有向图用十字链表存储，为方便运算，在顶点结点中，再增加一个入度域indegree，存放顶点的入度。入度为零的顶点先输出。为节省空间，入度域还起栈的作用。值得注意的是，在邻接表中，顶点的邻接点非常清楚，顶点的单链表中的邻接点域都是顶点的邻接点。由于十字链表边（弧）结点个数与边（弧）个数相同（不象无向图边结点个数是边的二倍），因此，对某顶点v, 要判断其邻接点是headvex还是tailvex。int Topsor(OrthList g)判断十字链表为存储结构的有向图g是否有环，如是返回1，否则返回0int top=-1; 用作栈顶指针 for(i=0;iheadvex=i) p=p-headlink; else p=p-taillink; 找顶点i的邻接点while(p) forfor(i=1;i=n;i+) if(gi.indegree=0)gi.indegree=top;top=i;建入度为0顶点的栈m=0; m为计数器，记输出顶点个数while(top-1) i=top; top=gtop.indegree; m+; top指向下一入度为0的顶点 p=gi.firstout; while(p) 处理顶点i的各邻接点的入度 if(p-tailvex=i) k=p-headvex; else k=p-tailvex; 找顶点i的邻接点 gk.indegree-; 邻接点入度减1 if(gk.indegree=0) gk.indegree=top; top=k; 入度为0的顶点再入栈if(p-headvex=i) p=p-headlink; else p=p-taillink;找顶点i的下一邻接点 while(p) while(top0)if(mn) retun(1)有向图存在环路; else return(0); 有向图无环路算法结束7.38已知n个顶点的有向图，用邻接矩阵表示，编写函数，计算每对顶点之间的最短路径。本题用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) 求具有n个顶点的有向图每对顶点间的最短路径 AdjMatrix length; lengthij存放顶点vi到vj的最短路径长度。 for(i=1;i=n;i+) for(j=1;j=n;j+) lengthij=gij; 初始化。 for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(lengthik+lengthkjlengthij) lengthij=lengthik+lengthkj; 算法结束7.39设计算法求距离顶点V0的最短路径长度(以弧数为单位)为K的所有顶点，要求尽可能地节省时间。【题目分析】 本题应用宽度优先遍历求解。若以v0作生成树的根为第层，则距顶点v0最短路径长度为K的顶点均在第K+1层。可用队列存放顶点，将遍历访问顶点的操作改为入队操作。队列中设头尾指针f和r，用level表示层数。void bfs_K(graph g,int v0,K)输出无向连通图g中距顶点v0最短路径长度为K的顶点 int Q; Q为顶点队列，容量足够大 int f=0,r=0,t=0; f和r分别为队头和队尾指针，t指向当前层最后顶点 int level=0,flag=0;层数和访问成功标记 visitedv0=1; 设v0为根 Q+r=v0; t=r; level=1; v0入队 while(fr & level=K+1) v=Q+f; w=GraphFirstAdj(g,v); while(w!=0) w!=0 表示邻接点存在 if(visitedw=0) Q+r=w; visitedw=1;邻接点入队列 if(level=K+1) printf(距顶点v0最短路径为k的顶点%d ,w); flag=1; if w=GraphNextAdj(g ,v ,w); while(w!=0) if(f=t) level+；t=r; 当前层处理完，修改层数，t指向下一层最后一个顶点 while(fr & level=K+1) if(flag=0) printf( 图中无距v0顶点最短路径为%d的顶点。n,K);算法结束 算法讨论本题亦可采取另一个算法。由于在生成树中结点的层数等于其双亲层次数加1，故可设顶点和层次数个队列，其入队和出队操作同步，其核心语句段如下：QueueInit(Q1) ; QueueInit(Q2); Q1和Q2是顶点和顶点所在层次数的队列 visitedv0=1; 访问数组初始化，置v0被访问标记 level=1; flag=0; 是否有层次为K的顶点的标志 QueueIn(Q1,v0); QueueIn(Q2,level); 顶点和层数入队列 while(!empty(Q1) & level=K+1) v=QueueOut(Q1); level=QueueOut(Q2);顶点和层数出队 w=GraphFirstAdj(g,v0); while(w!=0) 邻接点存在 if(visitedw=0) if(level=K+1) printf(距离顶点v0最短路径长度为K的顶点是%dn,w); visitedw=1; flag=1; QueueIn(Q1 ,w); QueueIn(Q2,level+1); w=GraphNextAdj(g ,v ,w); while(w!=0) while(!empty(Q1) & level0)个顶点的无向连通图G， 可以邻接矩阵Anxn存储，由于邻接矩阵的对称性，只将其下三角顺序存储在数组S中。请编写对以数组S存储的图G进行宽度优先遍历的算法。【题目分析】 由宽度优先遍历的定义，首先访问任一顶点，然后访问该顶点的未曾访问的邻接点，如此下去，直至全部顶点访问完成。在邻接矩阵中，第i行非零元素都是第i个顶点的邻接点，而在压缩存储下，找某顶点的邻接点要遍历整个数组。矩阵元素的下标i和j和其在一维数组S中的序号k的关系：由 得 和j=k-i(i+1)/2在一维数组中，只有非零元素才是顶点。为简单计，当访问完一个顶点后，就将其在一维数组中的位序置零；由于是图的遍历，当全部顶点访问完后就直接结束算法。#define n 用户图的顶点数#define m n(n+1)/2int nodes=0, visitedn=0; 顶点计数和访问标志数组void index(int k,*i,*k) 由非零元素在一维数组S中的序号k计算其在邻接矩阵中的下标i和j *i= (-3+sqrt(9+8*k)/2; *j=k-(*i)*(*i+1)/2 void Tri_bfs(int v) 对下三角存储的无向连通图作宽度优先遍历，v是遍历的开始顶点nodes+; QueueInit(Q); QueueIn(Q,v); printf(v); visitedv=1; 初始化 while(!QueueEmpty(Q) & nodes=n) v=QueueOut(Q); for(k=0; km; k+) if(sk!=0) index(k,&i,&j); 求非零元素在邻接矩阵中的下标 if(i=v | j=v) 顶点i或j是顶点v if(i=v) 顶点i是顶点v if(visitedj=0) 顶点j是顶点v的邻接点，且尚未访问 nodes+; printf(j); visitedj=1; sk=0; QueueIn(Q,j); else 顶点j是顶点v if(visitedi=0) 顶点i是顶点v的邻接点，且尚未访问 nodes+; printf(i); visitedi=1; sk=0; QueueIn(Q,i); 算法结束算法讨论对于连通图，进入BFS一次就可访问完图的全部顶点；对于非连通图，进入BFS一次就可访问完图的一个连通分量。若要遍历全部顶点，在调用BFS的函数中加入语句：for(vi=0; vin;vi+) if(visitedvi=0) Tri_bfs(vi);
展开阅读全文