数据结构答案 第8章 图学习指导Word文档格式.docx

1、在无向图中，如果从一个顶点vi到另一个顶点vj（ij）有路径，则称顶点vi和vj是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子图称为连通分量。（12）强连通图、强连通分量对于有向图来说，若图中任意一对顶点vi 和vj（ij）均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量（13）生成树连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树（Spanning Tree）。3图的存储表示（1）邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵。（2）邻接表邻接表是图的一种顺序存储与链式存储结合

2、的存储方法。4图的遍历图的遍历是指从图的某一顶点出发，对图中的所有顶点访问，且仅访问一次的方法。常用的有深度优先搜索和广度优先搜索两种方法。5最小生成树连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树，生成树中权值之和为最小的生成树，称为最小生成树。6最短路径在网中，两个顶点之间所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径。8.2 典型习题分析【例1】设有两个无向图G（V，E），G（V，E），如果G是G生成子树，则下述叙述不正确的是（ ）。AG是G的子图 BG是G的连通分量CG是G的无环子图

3、DG是G极小连通子图，且VV分析：如果G是G生成子树，显然G是G的子图、G是G的无环子图、G是G的连通分量和G是G极小连通子图但是VV，故D不正确，答案为D。【例2】若一个有向图具有拓扑序列，则它的矩阵必为（ ）。A对称矩阵 B三角矩阵 C一般矩阵 DB或C拓扑排序存在当仅当有向无环图，若一个有向图的邻接矩阵是三角形矩阵，则该图一定无环；但一个无环图的有向图的邻接矩阵未必是三角形。因此，应该选择D。【例3】用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？解：一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002 =

4、1000000个。它有1000个非零元素（对于有向图）或2000个非零元素（对于无向图），因此是稀疏矩阵。【例4】用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？答：用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。【例5】Prim算法最小生成树的时间复杂度为_，因此它适合于_图；Kruskal算法最小生成树的时间复杂度为_，因此适合于_图，且图应该用_作为存储结构。因为Prim算法的时间复杂度只与顶点数n有关，故对稀疏图不太适合，而Kruskal算法只与边数e有关，故对稀疏图较适合，且用邻接表作为存储结构为宜。依次

5、填写为O（n2）、稠密图、O（eloge）、稀疏图、邻接矩阵。【例6】设有一有向图为G=（V，E）。其中，V= v1, v2, v3, v4, v5，E=, v4, v3v4, v2v1, v4v4, v5v5, v1，请画出该有向图并判断是否是强连通图。作该题的关键是弄清楚以下两点（1）边集E中表示一条以vi为弧尾，vj为弧头的有向弧。（2）强连通图是任意两顶点间都存在路径的有向图。该有向图是强连通图，表示如图8-1所示。 图8-1 强连通有向图【例7】画出有向图8-2所示有向图的邻接矩阵、邻接表、逆邻接表、十字链表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。图8-

6、2 有向图图8-2的邻接矩阵、邻接表、逆邻接表、十字链表，如图8-3、图8-4、图8-5、图8-6所示。 图8-3 邻接矩阵 图8-4邻接表图8-5逆邻接表图8-6 十字链表深度优先遍历序列为：ABCFED；广度优先遍历序列为ABDCEF。【例8】已知无向图G的邻接表如图8-7所示，请写出其从顶点V2开始的深度优先搜索的序列。图8-7 邻接表图搜索可从图中某个顶点发V出发，首先访问此顶点，然后任选一个V的未被访问的邻接点w出发，继续进行深度优先搜索，直到图中所有和v路径相通的顶点都被访问到；若此时图中还有顶点未被访问到，则另选一个未被访问的顶点作为起始点，重复上面的做法，直至图中所有的顶点都被

7、访问。根据图从顶点V2开始的深度优先搜索的序列是V2，V2的邻接点有四个，按深度有先法则和给定邻接表，只能访问V5。再从V5出发，第一个邻接点V2已经访问过，只能访问V3。再从V3出发，同样第一个邻接点V2已经访问，只能访问V1。再从V5出发，第一个邻接点V3和第二邻接点V2已经访问过，退回到V3。在V3，V1下一个V4没有访问过，即访问，这样五个顶点都被访问，他们的顺序是V2，V5，V3，V1，V4。这里需要说明的是如果没有邻接表，从顶点V2出发对这个无向图深度优先搜索的访问次序不唯一，但是有邻接表是唯一。深度优先搜索的访问次序V2，V5，V3，V1，V4。【例9】设计一个算法，删除无向图的

8、邻接矩阵中给定顶点。要在邻接矩阵中删除某顶点i主要操作有以下三步：（1）图的边数要减去与顶点i相关联的边的数目；（2）在邻接矩阵中删除第i行与i列,即把第i+行到第n行依次前移，第i+列到第n列依次前移。（3）图中顶点的个数-1。算法如下：void Delvi（MGraph *G,int i） / 在图G中删除顶点iint num,j,k;if（iG-vexnum） printf（error）; exit（0）;else num=0;for（j=1;jvexnum;j+） / 计算与i相关的边数 if（G-arcsij） num+;if（G-arcsji）arcnum-=num; / 减去与i

9、相关的边数for（j=i+1;j+） for（k=1;karcsj-1k=G-arcsjk; / 从i+1行到最后一行元素都 向前移动一行j+） / 从i+1列到最后一列元素都 向前移动一列vexnum-1;arcskj-1=G-arcskj;vexnum-; / 顶点数减去1【例10】已知某有向图用邻接表表示，设计一个算法，求出给定两顶点间的简单路径。因为在遍历的过程中每个顶点仅被访问一次，所以从顶点u到顶点v遍历的过程中走过的路径就是一条简单路径。我们只需在遍历算法中稍作修改，就可实现该算法。为了记录路径中访问过的顶点，只需设一数组存储走过的顶点即可。求入度的思想：计算出邻接表中结点i的结

10、点数即可。int visitedMAX_VERTEX_NUM;int found;void DFSpath（ALGraph *G,int u,int v） int i;for（i=1;iagu.firstarc;p;p=p-nextarc） / 取第一个边if （v=p-adjvex） / 路径找到，输出pathu=v; found=1; Print（u,v）; return;else if（!visitedp-adjvex） / 取下一条边pathu=p-adjvex; DFS（G,p-adjvex,v）; / 递归 / DFSvoid Print（int u,int v） / 指印路径 i

11、nt m;printf（%d-,u）;for（m=pathu;m!=v;m=pathm）,m）;%dn,v）;8.3 单元练习8解答一判断题答案题目12345678910答案二填空题答案（1） 邻接表 （2） 深度优先搜（3） 2n（4） 弧（5） 顶点（6） 出度（7） O（n2）（8） O（n+e）（9） 邻接表（10） 邻接矩（11） 有向（12） n（n-1）/2（13） 出度 （14） 入度 （15） n-1 条边。（16） n+e 个结点。（17） 遍历 （18） 对称（19） 权 （20） Prim三选择题答案CBAD11121314151617181920四应用题答案（1）邻接

12、矩阵 1 2 3 4 5邻接表（2） 答：从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5（答案不唯一）从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3（答案不唯一）（3）答： 深度优先搜索：a b d c e （答案不唯一） 广度优先搜索： a b e d c （答案不唯一） （4） 最小生成树： 8 11 8 10 3 4 3 4 13 7 7（5） 答：完全无向图应具有的边数为：n*（n-1）1/2=4*（4-1）/2=6，所以还要增加2条边（如下图）。（6） 顶点入度出度（7）答：邻接矩阵为： 起点为a，可以直接由原始图画出最小生成树（8）答：邻接矩阵

13、最小生成树五程序题填空题答案（1） ERROR （2） ERROR （3） 0 （4） - 或=G.arcnum-1 （5） OK 六算法题答案（1）分析：本题思想是逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1，则相应的邻接表的第i个单链表上增加一个j结点。【函数代码】void trans（int edgesnn,Adjlist adj） int i,j; edgenode *p; for （i=0;n; adji.data=i; adji.link=NULL; for （j=0; if（edgesij=1） p=（edgenode *） malloc （sizeof（edgenode

14、）; p-adjvex=j;next=adji.link; adji.link=p; （2） 分析：计算出邻接表中第i个单链表的结点数即可。int outdegree（adjlist adj,int v） int degree=0; edgenode *p; p=adjv.link; while （p!=NULL） degree+; p=p-next; return degree;void printout（adjlist adj,int n） int i,degree; printf（The Outdegree are:n for（i=0; degree=outdegree（adj,i）;

15、printf（%d,%d）,i,degree）; 分析：int indegree（adjlist adj,int n,int v） int i,j,degree=0; for （i=0; p=adji.link; while （p! if （p-adjvex=v） degree+; return degree;void printin（adjlist adj,int n）The Indegree are: degree=Indegree（adj,n,i）; 求最大度的算法void maxoutdegree（adjlist adj,int n） int maxdegree=0,maxv=0,degree,i; degree=outdegree（adj,i）; if （degreemaxdegree） maxdegree=degree; maxv=i; printf（maxoutdegree %d,maxvertex=%d,maxdegree,maxv）;（3）求度为0的顶点数的算法int outzero（adjlist adj,int n） int num=0,i; if （outdegree（adj,i）=0） num+; return num;