数据结构书本习题答案(续).pdf

《数据结构书本习题答案(续).pdf》由会员分享，可在线阅读，更多相关《数据结构书本习题答案(续).pdf（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.5 对 n 个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题?(1)图中有多少条边?(2)任意两个顶点 i 和 j 是否有边相连?(3)任意一个顶点的度是多少?答：答：对于 n 个顶点的无向图和有向图，用邻接矩阵表示时：(1)设 m 为矩阵中非零元素的个数无向图的边数=m/2有向图的边数=m(2)无论是有向图还是无向图，在矩阵中第 i 行,第 j 列的元素若为非零值，则该两顶点有边相连。(3)对于无向图，任一顶点 i 的度为第 i 行中非零元素的个数。对于有向图，任一顶点 i 的入度为第 i 列中非零元素的个数，出度为第 i 行中非零元素的个数，度为入度出度之和。当

2、用邻接表表示时：(1)对于无向图，图中的边数=边表中结点总数的一半。对于有向图，图中的边数=边表中结点总数。(2)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的 adjvex 域有另一顶点位置的结点，则表示有边相连。对于有向图，则表示有出边相连。(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)7.6 n 个顶点的连通图至少有几条边?强连通图呢?答：答：n 个顶点的连通图至少有 n-1 条边，强连通图至少有 2(n-1)条边。

3、7.7 DFS 和 BFS 遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?答：DFS 遍历采用栈来暂存顶点。BFS 采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用 BFS 遍历。787.9 按顺序输入顶点对：(1，2)，(1，6)，(2，6)，(1，4)，(6，4)，(1，3)，(3，4),(6，5)，(4，5)，(1,5),(3,5),根据第 7.2.2 节中算法 CreatALGraph 画出相应的邻接表。并写出在该邻接表上，从顶点 4 开始搜索所得的 DFS 和 BFS 序列，及 DFS 和 BFS 生成树。答答：相应的邻接表如下：1

4、1 5 3 4 6 222 6 133 5 4 144 5 36 155 3 1 4 666 5 4 2 1根据上面的邻接表画出的图见下图:从顶点 4 开始搜索所得的 DFS 序列是：453162从顶点 4 开始搜索所得的 BFS 序列是：453612相应的生成树见上图。7.10 什么样的图其最小生成树是唯一的?用 PRIM 和 Kruskal求最小生成树的时间各为多少?它们分别适合于哪类图?答：当候选轻边集中的轻边数始终等于1 条时，其最小生成树是唯一的。用Prim 和 Kruskal 求最小生成树的时间复杂度分别为 O(n2)和 O(elge),前者适合于稠密图，后者适合于稀疏图.7.11

5、 对图 7.26（下图）所示的连通图，请分别用 Prim 和 Kruskal 算法构造其最小生成树。答：答：7.13 试写出图 7.28(下图)所示有向图的所有拓扑序列，并指出就用 7.6 节给出的 NonPreFirstTopSort 算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增有序的。答答：上图中所有拓扑序列如下：v0v1v5v2v3v6v4*v0v1v5v2v6v3v4 v0v1v5v6v2v3v4 v1v0v5v6v2v3v4 v1v0v5v2v3v6v4 v1v0v5v2v6v3v4 v1v5v0v2v3v6v4 v1v5v0v2v6v3v4 v1v5v0v6v2v3

6、v4 v5v1v0v2v3v6v4 v5v1v0v2v6v3v4 v5v1v0v6v2v3v4 v5v0v1v2v3v6v4 v5v0v1v2v6v3v4 v5v0v1v6v2v3v4 v0v5v6v1v2v3v4 v1v5v6v0v2v3v4 v5v6v1v0v2v3v4 v5v6v0v1v2v3v4 v5v0v6v1v2v3v4 v5v1v6v0v2v3v4用 NonPreFirstTopSort 算法求得的是 v0v1v5v2v3v6v4 也就是上面带*号的那个。7.14 什么样的 DAG 的拓扑序列是唯一的?答：答：确定了排序的源点，DAG 图中无前趋顶点只有一个且从该点到终点只有一条

7、路径时，它的拓扑序列才是唯一的。7.15 请以 V0 为源点，给出用 DFS 搜索图 7.28(下图)得到的逆拓扑序列。答：逆拓扑序列是：V4 V2 V1 V0 V1 V6 V57.16 试在无向图的邻接矩阵和邻接链表上实现如下算法：(1)往图中插入一个顶点(2)往图中插入一条边(3)删去图中某顶点(4)删去图中某条边解：(一)用邻接矩阵表示#define MaxVertexNum l00/最大顶点数，应由用户定义typedef char VertexType；/顶点类型应由用户定义typedef int EdgeType；/边上的权值类型应由用户定义typedef structVextexT

8、ype vexsMaxVertexNum/顶点表EdeType edgesMaxVertexNumMaxVertexNum;/邻接矩阵，可看作边表int n，e；/图中当前的顶点数和边数MGragh；(1)往图中插入一个顶点void AddVertexMGraph(MGraph*G,VertexType x)/往无向图的邻接矩阵中插入顶点if(G-n=MaxVertexNum)Error(顶点数太多)；G-vexsG-n=x;/将新顶点输入顶点表G-n+；/顶点数加 1(2)往图中插入一条边void AddedgeMGraph(MGraph*G,VertexType x,VertexType

9、y)/往无向图的邻接矩阵中插入边(x,y)int i,j,k;i=-1;j=-1;for(k=0;kn;k+)/查找 X，Y 的编号 if(g-vexsk=x)i=k;if(g-vexsk=y)j=k;if(i=-1|j=-1)Error(结点不存在);else/插入边(x,y)g-vexij=1;g-vexji=1;G-e+;/边数加 1(3)删去图中某顶点void DeleteVertexMGraph(MGraph*G,VertexType x)/无向图的邻接矩阵中删除顶点xint i,k,j;i=-1;for(k=0;kn;k+)/查找 X 的编号if(g-vexsk=x)i=k;if(

10、i=-1)Error(结点不存在);else/删除顶点以及边k=0;/求出与 x 结点相关联的边数kfor(j=0;jn;j+)if(g-vexsij=0)k+;G-e=G-e-k;/设置新的边数for(k=i+1;kn;k+)/在邻接矩阵中删除第 i 行for(j=0;jn;j+)g-vexsk-1j=g-vexskj;for(k=i+1;kn;k+)/在邻接矩阵中删除第 i 列for(j=0;jn;j+)g-vexsjk-1=g-vexsjk;G-n-;/总结点数-1(4)删去图中某条边void DeleteedgeMGraph(MGraph*G,VertexType x,VertexTy

11、pe y)/无向图的邻接矩阵中删除边(x,y)int i,j,k;i=-1;j=-1;for(k=0;kn;k+)/查找 X，Y 的编号 if(g-vexsk=x)i=k;if(g-vexsk=y)j=k;if(i=-1|j=-1)Error(结点不存在);else if(g-vexsij!=1)/删除边(x,y)g-vexij=0;g-vexji=0;G-e-;/边数加 1(二)用邻接表表示typedef struct node/边表结点int adjvex；/邻接点域struct node*next；/链域/若要表示边上的权，则应增加一个数据域EdgeNode;typedef struct

12、 vnode/顶点表结点VertexType vertex；/顶点域EdgeNode*firstedge；/边表头指针VertexNode；typedef VertexNode AdjListMaxVertexNum；/AdjList 是邻接表类型typedef structAdjList adjlist；/邻接表int n，e；图中当前顶点数和边数ALGraph；/对于简单的应用，无须定义此类型，可直接使用AdjList 类型。(1)往图中插入一个顶点void AddVertexALGraPh(ALGrahp*G,VertexType x)/往无向图的邻接表表示中插入一个顶点if(G-n=M

13、axVertexNum)Error(顶点数太多)；G-adjlistG-n.vertex=x;/将新顶点输入顶点表G-adjlistG-n.firstedge=NULL;/边表置为空表G-n+；/顶点数加 1(2)往图中插入一条边void AddedgeALGraPh(ALGrahp*G,VertexType x,VertexType y)/往无向图的邻接表中插入边(x,y)int i,j,k;EdgeNode*s；i=-1;j=-1;for(k=0;kn;k+)/查找 X，Y 的编号 if(G-adjlistk.vertex=x)i=k;if(G-adjlistk.vertex=y)j=k;

14、if(i=-1|j=-1)Error(结点不存在);else s=G-adjlisti.firstedge;while(s)&(s-adjvex!=j)/查看邻接表中有无(x,y)s=s-next;if(!s)/当邻接表中无边(x,y),插入边(x,y)s=(EdgeNode*)malloc(sizeof(EdgeNode)；/生成边表结点s-adjvex=j;/邻接点序号为 js-next=G-adjlisti.firstedge；G-adjlisti.firstedge=s；/将新结点*s 插入顶点 x 的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode)；s

15、-adjvex=i;/邻接点序号为 is-next=G-adjlistj.firstedge；G-adjlistj.firstedge=s；/将新结点*s 插入顶点 x 的边表头部G-e+;/边数加 1(3)删去图中某顶点void DeleteVertexALGraPh(ALGrahp*G,VertexType x)/无向图的邻接表中删除顶点xint i,k,j;EdgeNode*s,*p,*q；i=-1;for(k=0;kn;k+)/查找 X 的编号if(G-adjlistk.vertex=x)i=k;if(i=-1)Error(结点不存在);else/删除与 x 相关联的边s=G-adjl

16、isti.firstedge;while(s)p=G-adjlists-adjvex.firstedge;/删除与 i 相关联的其他结点边表中表结点if(p)&(p-adjvex=i)/是第一个边表结点，修改头指针G-adjlists-adjvex.firstedge=p-next;free(p);else/不是第一个 边表结点，查找并删除while(p)&(p-next)&(p-next-adjvex=i)p=p-next;q=p-next;p-next=q-next;free(q);q=s;s=s-next;free(q);/在 i 结点的边表中删除表结点G-e-;/调整顶点表for(j=

17、i;jn-1;j+)G-adjlistj.firstedge=G-adjlistj+1.firstedge;G-adjlistj.vertex=G-adjlistj+1.vertex;G-n-;(4)删去图中某条边void DeleteedgeALGraPh(ALGraph*G,VertexType x,VertexType y)/往无向图的邻接表中删除边(x,y)int i,j,k;EdgeNode*s,*p；i=-1;j=-1;for(k=0;kn;k+)/查找 X，Y 的编号 if(G-adjlistk.vertex=x)i=k;if(G-adjlistk.vertex=y)j=k;if

18、(i=-1|j=-1)Error(结点不存在);else s=G-adjlisti.firstedge;/在 i 的边表中删除值为 j 的边表结点if(s)&(s-adjvex=j)G-adjlisti.firstedge=s-next;free(s);elsewhile(s)&(s-next)&(s-next-adjvex!=j)s=s-next;if(!s-next)Error(无此边);elsep=s-next;s=p-next;free(p);s=G-adjlistj.firstedge;/在 j 的边表中删除值为 i 的边表结点if(s)&(s-adjvex=i)G-adjlistj

19、.firstedge=s-next;free(s);elsewhile(s)&(s-next)&(s-next-adjvex!=j)s=s-next;p=s-next;s=p-next;free(p);G-e-;7.17 下面的伪代码是一个广度优先搜索算法，试以图7.29（下图）中的 v0 为源点执行该算法，请回答下述问题：(1)对图中顶点 vn+1，它需入队多少次？它被重复访问多少次?(2)若要避免重复访问同一个顶点的错误，应如何修改此算法?void BFS(ALGraph*G,int k)/以下省略局部变量的说明，visited 各分量初值为假InitQueue(&Q);/置空队列EnQu

20、eue(&Q,k);/k入队while(!QueueEmpty(&Q)i=DeQueue(&Q);/vi出队visitedi=TRUE;/置访问标记printf(%c,G-adjlisti.vertex;/访问 vifor(p=G-adjlisti.firstedge;p;p=p-next)/依次搜索 vi 的邻接点 vj(不妨设 p-adjvex=j)if(!visitedp-adjvex)/若 vj 没有访问过EnQueue(&Q,p-adjvex);/vj入队/endofwhile/BFS答：(1)对图中顶点 vn+1，它需入队 n 次,它被重复访问 n 次。(2)若要避免重复访问同一个

21、顶点的错误，应作如下修改：void BFS(ALGraph*G,int k)/以下省略局部变量的说明，visited 各分量初值为假InitQueue(&Q);/置空队列EnQueue(&Q,k);/k入队visitedi=TRUE;/置访问标记printf(%c,G-adjlisti.vertex;/访问 viwhile(!QueueEmpty(&Q)i=DeQueue(&Q);/vi出队for(p=G-adjlisti.firstedge;p;p=p-next)/依次搜索并访问 vi 的未访问邻接点 vj(不妨设 p-adjvex=j)if(!visitedp-adjvex)/若 vj 没

22、有访问过printf(%c,G-adjlisti.vertex;/访问 vjEnQueue(&Q,p-adjvex);/vj入队/endofwhile/BFS7.18 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS 和 BFS 遍历的算法来判别顶点 vi 和 vj(ij)之间是否有路径。答：(1)基于采用邻接矩阵的DFSint pathDFSM(MGraph*G，int i,int j)/以邻接矩阵为存储结构，判断vi 和 vj 之间是否有路径，若有返回1，否则返回 0int k;visitedi=TRUE；for(k=0；kn；k+)/依次搜索 vi 的邻接点if(G-edgesik=1

23、&!visitedk)if(k=j)return 1;/有路径相通else return(pathDFSM(G,k,j);return 0;/无路径相通/DFSM(2)基于采用邻接表的 DFSint PATHDFS(ALGraph*G，int i,int j)/以邻接表为存储结构，判断vi 和 vj 之间是否有路径，若有返回1，否则返回 0EdgeNode*p；visitedi=TRUE；/标记 vi 已访问p=G-adjlisti.firstedge；/取 vi 边表的头指针while(p)/依次搜索 vi 的邻接点 vk，这里 k=p-adjvexif（!visitedp-adjvex)/

24、若 vk 尚未被访问if(p-adjvex=j)return 1;else ruturn PATHDFS(g，p-adjvex,j);/则以 Vk 为出发点向纵深搜索p=p-next；/找 vi 的下一邻接点return 0;/PATHDFS(3)基于邻接矩阵的 BFS 算法int pathBFSM(MGraph*G，int i,int j)/以邻接矩阵为存储结构，判断vi 和 vj 之间是否有路径，若有返回1，否则返回 0int k；CirQueue Q；initQueue(&Q)；visitedi=TRUE；EnQueue(&Q，i)；while(!QueueEmpty(&Q)i=DeQu

25、eue(&Q)；/vi 出队for(k=0;kn;k+)/依次搜索 vi 的邻接点 vkif(G-edgesik=1&!visitedk)/vk未访问if(k=j)return 1;visitedk=TRUE；EnQueue(&Q，k)；/访问过的 vk 人队/endwhilereturn 0;/pathBFSM(4)基于邻接表为存储结构的BFS 算法int BFS(ALGraph*G，int i,int j)/以邻接表为存储结构，判断vi 和 vj 之间是否有路径，若有返回1，否则返回 0int i；CirQueue Q；/须将队列定义中 DataType改为 intEdgeNode*p；I

26、nitQueue(&Q)；/队列初始化visitedi=TRUE；EnQueue(&Q，i)；/vi 已访问，将其人队。（实际上是将其序号人队）while(!QueueEmpty(&Q)/队非空则执行i=DeQueue(&Q)；/相当于 vi 出队p=G-adjlisti.firstedge；/取 vi 的边表头指针while(p)/依次搜索 vi 的邻接点 vk(令 p-adjvex=k)if(!visitedp-adjvex)/若 vk 未访问过if(p-adjvex=j)return 1;elsevisitedP-adjvex=TRUE；EnQueue(&Q，p-adjvex)；/访问过

27、的 vk 人队p=p-next；/找 vi 的下一邻接点/endwhile/endwhilereturn 0;/end of pathBFS7.19 试分别写出求 DFS 和 BFS 生成树(或生成森林)的算法，要求打印出所有的树边。答：(1)求 DFS 生成树typedef enumFALSE，TRUEBoolean；/FALSE为 0，TRUE 为 1Boolean visitedMaxVertexNum；/访问标志向量是全局量void DFSTraverseTREE(ALGraph*G)/求深度优先生成树(以邻接表表示的图 G)，而以邻接矩阵表示G 时，/算法完全与此相同,只要将 DFS

28、Tree(G，i)改为 DFSMTree(G，i)即可int i；for(i=0;in;i+)visitedi=FALSE；/标志向量初始化for(i=0;in；i+)if(!visitedi)/vi未访问过DFSTree(G，i)；/以 vi 为源点开始 DFS 搜索,求 DFS 生成树的边/DFSTraversevoid DFSTree(ALGraph*G，int i)/以 vi 为出发点对邻接表表示的图G 进行深度优先搜索,打印生成树(生成森林)的边EdgeNode*p；visitedi=TRUE；/标记 vi 已访问p=G-adjlisti.firstedge；/取 vi 边表的头指针

29、while(p)/依次搜索 vi 的邻接点 vj，这里 j=p-adjvexif(!visitedp-adjvex)/若 vj 尚未被访问printf(%c,%c)n,G-adjlisti.vertex,G-adjlistp-adjvex.vertex)；/打印边DFSTree(g，p-adjvex);/则以 Vj 为出发点向纵深搜索p=p-next；/找 vi 的下一邻接点/DFSvoid DFSMTree(MGraph*G，int i)/以 vi 为出发点对邻接矩阵表示的图G 进行深度优先搜索,打印生成树(生成森林)的边int j；visitedi=TRUE；for(j=0；jn；j+)/

30、依次搜索 vi 的邻接点if(G-edgesij=1&!visitedj)printf(%c,%c)n,G-vexsi,G-vexsj);/打印边DFSMTree(G，j);/(vi，vj)E，且 vj 未访问过，故 vj 为新出发点/DFSMTree(2)求 BFS 生成树typedef enumFALSE，TRUEBoolean；/FALSE为 0，TRUE 为 1Boolean visitedMaxVertexNum；/访问标志向量是全局量void BFSTraverseTREE(ALGraph*G)/求广度优先生成树(以邻接表表示的图 G)，而以邻接矩阵表示G 时，/算法完全与此相同,

31、只要将 BFSTree(G，i)改为 BFSMTree(G，i)即可int i；for(i=0;in;i+)visitedi=FALSE；/标志向量初始化for(i=0;in；i+)if(!visitedi)/vi未访问过BFSTree(G，i)；/以 vi 为源点开始 BFS 搜索,求 BFS 生成树的边/BFSTraversevoid BFSTree(ALGraph*G，int k)/以 vk 为源点对用邻接表表示的图G 进行广度优先搜索,并求出 BFS 生成树边int i；CirQueue Q；/须将队列定义中 DataType改为 intEdgeNode*p；InitQueue(&Q)

32、；/队列初始化visitedk=TRUE；EnQueue(&Q，k)；/vk 已访问，将其人队。（实际上是将其序号人队）while(!QueueEmpty(&Q)/队非空则执行i=DeQueue(&Q)；/相当于 vi 出队p=G-adjlisti.firstedge；/取 vi 的边表头指针while(p)/依次搜索 vi 的邻接点 vj(令 p-adjvex=j)if(!visitedp-adivex)/若 vj 未访问过printf(%c,%c)n，G-adjlisti.vertex,G-adjlistp-adjvex.vertex)；/打印边visitedP-adjvex=TRUE；E

33、nQueue(&Q，p-adjvex)；访问过的 vj 人队/endifp=p-next；/找 vi 的下一邻接点/endwhile/endwhile/end of BFSTreevoid BFSMTree(MGraph*G，int k)/以 vk 为源点对用邻接矩阵表示的图G 进行广度优先搜索,并求出 BFS 生成树边int i，j；CirQueue Q；InitQueue(&Q)；visitedk=TRUE；EnQueue(&Q，k)；while(!QueueEmpty(&Q)i=DeQueue(&Q)；/vi 出队for(j=0;jn;j+)/依次搜索 vi 的邻接点 vjif(G-ed

34、gesij=1&!visitedj)/vi未访问printf(%c,%c)n，G-vexsi,G-vexsj)；/打印边visitedj=TRUE；EnQueue(&Q，j)；/访问过的 vj 人队/endwhile/BFSMTree7.20 写一算法求连通分量的个数并输出各连通分量的顶点集。答：typedef enumFALSE，TRUEBoolean；/FALSE为 0，TRUE 为 1Boolean visitedMaxVertexNum；/访问标志向量是全局量void DFSTraverse(ALGraph*G)/深度优先遍历以邻接表表示的图G，求连通分量的个数和各连通分量的顶点集in

35、t i；for(i=0;in;i+)visitedi=FALSE；/标志向量初始化j=0;/连通分量个数计数器for(i=0;in；i+)if(!visitedi)/vi未访问过j+;printf(connected component%d:,j);DFS(G，i)；/以 vi 为源点开始 DFS 搜索printf(n);/DFSTraversevoid DFS(ALGraph*G，int i)/以 vi 为出发点对邻接表表示的图G 进行深度优先搜索EdgeNode*p；printf(c,，G-adjlisti.vertex)；/访问顶点 vivisitedi=TRUE；/标记 vi 已访问p

36、=G-adjlisti.firstedge；/取 vi 边表的头指针while(p)/依次搜索 vi 的邻接点 vj，这里 j=p-adjvexif（!visitedp-adjvex)/若 vi 尚未被访问DFS(g，p-adjvex);/则以 Vj 为出发点向纵深搜索p=p-next；/找 vi 的下一邻接点/DFS7.21 设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法：(1)求顶点 vi 到顶点 vj(ij)的最短路径(2)求源点 vi 到其余各顶点的最短路径要求输出路径上的所有顶点(提示：利用 BFS 遍历的思想)答(1)求顶点 vi 到顶点 vj(ij)的最短路

37、径int shortestpath(ALGraph*G，int i,int j)/对邻接表表示的图 G，求顶点 vi 到顶点 vj(ij)的最短路径int distMaxVertexNum;CirQueue Q；/须将队列定义中 DataType改为 intEdgeNode*p；int k；for(k=0;kn;k+)distk=0；/距离向量初始化InitQueue(&Q)；/队列初始化visitedi=TRUE；EnQueue(&Q，i)；while(!QueueEmpty(&Q)/队非空则执行i=DeQueue(&Q)；/相当于 vi 出队p=G-adjlisti.firstedge；/

38、取 vi 的边表头指针while(p)/依次搜索 vi 的邻接点 vk(令 p-adjvex=k)if(!visitedp-adjvex)/若 vj 未访问过distp-adjvex+;if(p-adjvex=j)return distp-adjvex;visitedP-adjvex=TRUE；EnQueue(&Q，p-adjvex)；访问过的 vk 人队/endifp=p-next；/找 vi 的下一邻接点/endwhile/endwhile/end of shortestpathint BFSM(MGraph*G，int i,int j)/对邻接链表表示的图G，求顶点 vi 到顶点 vj(

39、ij)的最短路径int distMaxVertexNum,k；CirQueue Q；initQueue(&Q)；for(k=0;kn;k+)disti=0；/距离向量初始化visitedk=TRUE；EnQueue(&Q，i)；while(!QueueEmpty(&Q)i=DeQueue(&Q)；/vi 出队for(k=0;kn;k+)/依次搜索 vi 的邻接点 vkif(G-edgesik=1&!visitedk)/vk未访问distk+;if(k=j)return distj;visitedk=TRUE；EnQueue(&Q，k)；/访问过的 vk 人队/endwhile/BFSM(2)求

40、源点 vi 到其余各顶点的最短路径void shortestpath(ALGraph*G，int i)/对邻接表表示的图 G，求顶点 vi 到顶点 vj(ij)的最短路径int distMaxVertexNum;int preMaxVertexNum;/prek 中存放 vi 到 vk 路径中，vk 的前趋的序号CirQueue Q；/须将队列定义中 DataType改为 intEdgeNode*p；int k,j；for(k=0;kn;k+)distk=0；/距离向量初始化prek=k;InitQueue(&Q)；/队列初始化visitedi=TRUE；EnQueue(&Q，i)；while

41、(!QueueEmpty(&Q)/队非空则执行i=DeQueue(&Q)；/相当于 vi 出队p=G-adjlisti.firstedge；/取 vi 的边表头指针while(p)/依次搜索 vi 的邻接点 vk(令 p-adjvex=k)if(!visitedp-adjvex)/若 vj 未访问过distp-adjvex+;prep-adjvex=i;visitedP-adjvex=TRUE；EnQueue(&Q，p-adjvex)；访问过的 vk 人队/endifp=p-next；/找 vi 的下一邻接点/endwhile/endwhilefor(k=0;kn;k+)/打印各顶点的最短路径

42、和长度printf(path of%c is%d:,G-adjlistk.vertex,distk);j=k;printf(%c,G-adjlistk.vertex);doj=prej;print(adjlistj.vertex);while(j!=i);printf(n);/end of shortestpathvoid shortestpathBFSM(MGraph*G，int i)/对邻接矩阵表示的图G，求顶点 vi 到其他顶点的最短路径int distMaxVertexNum,k,j;int preMaxVertexNum;/prek 中存放 vi 到 vk 路径中，vk 的前趋的序号

43、CirQueue Q；initQueue(&Q)；for(k=0;kn;k+)distk=0；/距离向量初始化prek=k;visitedk=TRUE；EnQueue(&Q，i)；while(!QueueEmpty(&Q)i=DeQueue(&Q)；/vi 出队for(k=0;kn;k+)/依次搜索 vi 的邻接点 vkif(G-edgesik=1&!visitedk)/vk未访问distk+;prek=i;visitedk=TRUE；EnQueue(&Q，k)；/访问过的 vk 人队/endwhilefor(k=0;kn;k+)/打印各顶点的最短路径和长度printf(path of%c i

44、s%d:,G-vertexk,distk);j=k;printf(%c,G-vertexk);doj=prej;printf(vertexj);while(j!=i);printf(n);/shortestpathBFSM7.22 以邻接表为存储结构，写一个基于 DFS 遍历策略的算法，求图中通过某顶点 vk 的简单回路(若存在)。答：int circleDFS(ALGraph*G，int k)/以 vk 为出发点对邻接表表示的图G,求简单回路,若存在返回 1，否则返回 0EdgeNode*p；printf(c，G-adjlistk.vertex)；/访问顶点 vkvisitedk=TRUE；

45、/标记 vk 已访问p=G-adjlistk.firstedge；/取 vk 边表的头指针while(p)/依次搜索 vk 的邻接点 vj，这里 j=p-adjvexif(!visitedp-adjvex)/若 vj 尚未被访问DFS(G，p-adjvex);/则以 Vj 为出发点向纵深搜索else if(p-adjvex=k)printf(%c,G-adjlistk.vertex)；return 1;p=p-next；/找 vk 的下一邻接点return 0;/DFS7.23 写一算法求有向图的所有根(若存在)，分析算法的时间复杂度。答：typedef enumFALSE，TRUEBoole

46、an；/FALSE为 0，TRUE 为 1Boolean visitedMaxVertexNum；/访问标志向量是全局量void DFSTraverse(ALGraph*G)/对以邻接表表示的有向图G，求所有根(以邻接矩阵表示G 时，算法完全与此相同)int i,j；for(j=0;jn;j+)for(i=0;in;i+)visitedi=FALSE；/标志向量初始化DFS(G，j)；/以 vj 为源点开始 DFS 搜索，也可用 BFS(G,j)i=0;while(in)&(visitedi=TRUE)i+;if(i=G-n)printf(root:%c,G-adjlistj.vertex);

47、/DFSTraverse该算法的为二重循环，若调用的DFS 算法的复杂度为 O(n+e),所以该算法的时间复杂度为O(n(n+e)若调用的 DFSM 算法的复杂度为 O(n*n),所以该算法的时间复杂度为 O(n3)7.24 改写 7.5 节的算法 Print，使输出的从源点到各终点的最短路径是正向的。(提示：使用栈暂存路径)答：void print(path p,distance d)/输出最短路径及其长度，从源点到各终点的最短路径是正向的int i,pre;SeqStack S;/定义一个栈InitStack(&s);for(i=0;i=G.nSeqStack S,T;/将栈中 data

48、向量的基类型改为 intint i,j,count=0;/count对输出的顶点数目计数，初值为0for(i=0;iG.n;i+)outdegreei=0;for(i=0;iG.n;i+)for(j=0;jG.n;j+)outdegreei=outdegreei+g.edgeij;InitStack(&s);for(i=0;iG.n;i+)if(outdegreei=0)Push(&S,i);/出度为 0 的顶点 i 入栈InitStack(&T);while(!StackEmpty(S)/栈非空，有出度为 0 的顶点i=pop(&s);Push(&T,i);count+;/顶点计数加 1fo

49、r(j=0;jG.n;j+)/修改以 i 为弧头的弧的弧尾顶点的出度if(G.edgeji=1)G.edgeji=0;outdegreej-;if(outdegreej=0)/将新生成的出度为 0 的顶点入栈Push(&S,j);/出度为 0 的顶点 j 入栈/end of if/end of whileif(count=G.nSeqStack S,T;/将栈中 data 向量的基类型改为 intint i,j,count=0;/count对输出的顶点数目计数，初值为0EdgeNode*p;for(i=0;iG.n;i+)outdegreei=0;for(i=0;inext)/扫描 i 的入边

50、表outdegreep-adjvex+;/设 p-adjvex=j，则将的起点 j 出度加 1InitStack(&s);for(i=0;inext)/修改以 i 为弧头的弧的弧尾顶点的出度j=p-adjvex;outdegreej-;if(outdegreej=0)/将新生成的出度为 0 的顶点入栈Push(&S,j);/出度为 0 的顶点 j 入栈/end of for/end of whileif(countG.n)/输出顶点数小于 nprintf(G 中存在有向环，排序失败!);else/输出拓扑序列while(!StackEmpty(T)printf(%c,G.adjlistpop(