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

17.5对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题?(1)图中有多少条边?(2)任意两个顶点i和j是否有边相连?(3)任意一个顶点的度是多少?答：对于n个顶点的无向图和有向图，用邻接矩阵表示时：(1)设m为矩阵中非零元素的个数无向图的边数=m/2有向图的边数=m(2)无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。(3)对于无向图，任一顶点i的度为第i行中非零元素的个数。对于有向图，任一顶点i的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度之和。当用邻接表表示时：(1)对于无向图，图中的边数=边表中结点总数的一半。对于有向图，图中的边数=边表中结点总数。(2)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。对于有向图，则表示有出边相连。(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)7.6n个顶点的连通图至少有几条边?强连通图呢?答：n个顶点的连通图至少有n-1条边，强连通图至少有2(n-1)条边。7.7DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?答：DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。7．87.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│1│─→│5│─→│3│─→│4│─→│6│─→│2│∧│├─┼─┤├─┼─┤├─┼─┤└─┴─┘└─┴─┘└─┴─┘2│2│─→│6│─→│1│∧│├─┼─┤├─┼─┤├─┼─┤┌─┬─┐23│3│─→│5│─→│4│─→│1│∧│├─┼─┤├─┼─┤├─┼─┤├─┼─┤┌─┬─┐4│4│─→│5│─→│3│─→│6│─→│1│∧│├─┼─┤├─┼─┤├─┼─┤├─┼─┤├─┼─┤5│5│─→│3│─→│1│─→│4│─→│6│∧│├─┼─┤├─┼─┤├─┼─┤├─┼─┤├─┼─┤6│6│─→│5│─→│4│─→│2│─→│1│∧│└─┴─┘└─┴─┘└─┴─┘└─┴─┘└─┴─┘根据上面的邻接表画出的图见下图:从顶点4开始搜索所得的DFS序列是：453162从顶点4开始搜索所得的BFS序列是：453612相应的生成树见上图。7.10什么样的图其最小生成树是唯一的?用PRIM和Kruskal求最小生成树的时间各为多少?它们分别适合于哪类图?答：当候选轻边集中的轻边数始终等于1条时，其最小生成树是唯一的。用Prim和Kruskal求最小生成树的时间复杂度分别为O(n2)和O(elge),前者适合于稠密图，后者适合于稀疏图.7.11对图7.26（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。答：7.13试写出图7.28(下图)所示有向图的所有拓扑序列，并指出就用7.6节给出的NonPreFirstTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增有序的。3答：上图中所有拓扑序列如下：v0v1v5v2v3v6v4*v0v1v5v2v6v3v4v0v1v5v6v2v3v4v1v0v5v6v2v3v4v1v0v5v2v3v6v4v1v0v5v2v6v3v4v1v5v0v2v3v6v4v1v5v0v2v6v3v4v1v5v0v6v2v3v4v5v1v0v2v3v6v4v5v1v0v2v6v3v4v5v1v0v6v2v3v4v5v0v1v2v3v6v4v5v0v1v2v6v3v4v5v0v1v6v2v3v4v0v5v6v1v2v3v4v1v5v6v0v2v3v4v5v6v1v0v2v3v4v5v6v0v1v2v3v4v5v0v6v1v2v3v4v5v1v6v0v2v3v4用NonPreFirstTopSort算法求得的是v0v1v5v2v3v6v4也就是上面带*号的那个。7.14什么样的DAG的拓扑序列是唯一的?答：确定了排序的源点，DAG图中无前趋顶点只有一个且从该点到终点只有一条路径时，它的拓扑序列才是唯一的。7.15请以V0为源点，给出用DFS搜索图7.28(下图)得到的逆拓扑序列。答：逆拓扑序列是：V4V2V1V0V1V6V57.16试在无向图的邻接矩阵和邻接链表上实现如下算法：(1)往图中插入一个顶点(2)往图中插入一条边4(3)删去图中某顶点(4)删去图中某条边解：(一)用邻接矩阵表示#defineMaxVertexNuml00//最大顶点数，应由用户定义typedefcharVertexType；//顶点类型应由用户定义typedefintEdgeType；//边上的权值类型应由用户定义typedefstruct{VextexTypevexs[MaxVertexNum]//顶点表EdeTypeedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn，e；//图中当前的顶点数和边数}MGragh；(1)往图中插入一个顶点voidAddVertexMGraph(MGraph*G,VertexTypex){//往无向图的邻接矩阵中插入顶点if(G-n=MaxVertexNum)Error(顶点数太多)；G-vexs[G-n]=x;//将新顶点输入顶点表G-n++；//顶点数加1}(2)往图中插入一条边voidAddedgeMGraph(MGraph*G,VertexTypex,VertexTypey){//往无向图的邻接矩阵中插入边(x,y)inti,j,k;i=-1;j=-1;for(k=0;kG-n;k++)//查找X，Y的编号{if(g-vexs[k]===x)i=k;if(g-vexs[k]==y)j=k;}if(i==-1||j==-1)Error(结点不存在);else{//插入边(x,y)g-vex[i][j]=1;g-vex[j][i]=1;G-e++;//边数加1}}(3)删去图中某顶点voidDeleteVertexMGraph(MGraph*G,VertexTypex){//无向图的邻接矩阵中删除顶点xinti,k,j;i=-1;5for(k=0;kG-n;k++)//查找X的编号if(g-vexs[k]=x)i=k;if(i==-1)Error(结点不存在);else{//删除顶点以及边k=0;//求出与x结点相关联的边数kfor(j=0;jG-n;j++)if(g-vexs[i][j]==0)k++;G-e=G-e-k;//设置新的边数for(k=i+1;kG-n;k++)//在邻接矩阵中删除第i行for(j=0;jG-n;j++)g-vexs[k-1][j]=g-vexs[k][j];for(k=i+1;kG-n;k++)//在邻接矩阵中删除第i列for(j=0;jG-n;j++)g-vexs[j][k-1]=g-vexs[j][k];G-n--;//总结点数-1}}(4)删去图中某条边voidDeleteedgeMGraph(MGraph*G,VertexTypex,VertexTypey){//无向图的邻接矩阵中删除边(x,y)inti,j,k;i=-1;j=-1;for(k=0;kG-n;k++)//查找X，Y的编号{if(g-vexs[k]=x)i=k;if(g-vexs[k]=y)j=k;}if(i==-1||j==-1)Error(结点不存在);elseif(g-vexs[i][j]!=1){//删除边(x,y)g-vex[i][j]=0;g-vex[j][i]=0;G-e--;//边数加1}}(二)用邻接表表示typedefstructnode{//边表结点intadjvex；//邻接点域structnode*next；//链域//若要表示边上的权，则应增加一个数据域}EdgeNode;typedefstructvnode{//顶点表结点VertexTypevertex；//顶点域EdgeNode*firstedge；//边表头指针6}VertexNode；typedefVertexNodeAdjList[MaxVertexNum]；//AdjList是邻接表类型typedefstruct{AdjListadjlist；//邻接表intn，e；图中当前顶点数和边数}ALGraph；//对于简单的应用，无须定义此类型，可直接使用AdjList类型。(1)往图中插入一个顶点voidAddVertexALGraPh(ALGrahp*G,VertexTypex){//往无向图的邻接表表示中插入一个顶点if(G-n=MaxVertexNum)Error(顶点数太多)；G-adjlist[G-n].vertex=x;//将新顶点输入顶点表G-adjlist[G-n].firstedge=NULL;//边表置为空表G-n++；//顶点数加1}(2)往图中插入一条边voidAddedgeALGraPh(ALGrahp*G,VertexTypex,VertexTypey){//往无向图的邻接表中插入边(x,y)inti,j,k;EdgeNode*s；i=-1;j=-1;for(k=0;kG-n;k++)//查找X，Y的编号{if(G-adjlist[k].vertex==x)i=k;if(G-adjlist[k].vertex==y)j=k;}if(i==-1||j==-1)Error(结点不存在);else{s=G-adjlist[i].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-adjlist[i].firstedge；G-adjlist[i].firstedge=s；//将新结点*s插入顶点x的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode))；s-adjvex=i;//邻接点序号为is-next=G-adjlist[j].firstedge；G-adjlist[j].firstedge=s；//将新结点*s插入顶点x的边表头部G-e++;//边数加1}}}7(3)删去图中某顶点voidDeleteVertexALGraPh(ALGrahp*G,VertexTypex){//无向图的邻接表中删除顶点xinti,k,j;EdgeNode*s,*p,*q；i=-1;for(k=0;kG-n;k++)//查找X的编号if(G-adjlist[k].vertex==x)i=k;if(i==-1)Error(结点不存在);else{//删除与x相关联的边s=G-adjlist[i].firstedge;while(s){p=G-adjlist[s-adjvex].firstedge;//删除与i相关联的其他结点边表中表结点if(p)&&(p-adjvex==i)//是第一个边表结点，修改头指针{G-adjlist[s-adjvex].fi