数据结构电子教案 第七章_数据结构电子教案

数据结构电子教案 第七章由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构电子教案”。

同步综合练习及参考答案

（一）基础知识题

7．1 在图7.23所是的各无向图中：

（1）找出所有的简单环。

（2）那些图是连通图？对非连通图给出其连通分量。

（3）那些图是自由树（或森林）？ //自由树的概念见 7.4节 解：

（1）简单环

（a）(1 2 3 1)(b)无

(c)（1 2 3 1）（2 3 4 2）（1 2 4 3 1）(d)无

（2）连通图（a）（c）（d）

非连通图（b）的连通分量为（3）自由树（d）

森林（b）

7．2 在图7.24所是的有向图中：

（1）该图是强连通的码？若不是，则给出其强连通分量。（2）请给出所有简单路径及有向环。（3）请给出每个顶点的度、入度和出度。（4）请给出其邻接表、邻接矩阵及逆邻接表。解：

（1）图是强连通的。

（2）所有简单路径（重复环未计算）

（v1）（v2）（v3）（v4）

(v1 v2)(v2 v3)(v3 v1)(v1 v4)(v4 v3)(v1 v2 v3)(v2 v3 v1)(v3 v1 v4)(v3 v1 v2)(v1 v4 v3)(v4 v3 v1)（v1 v2 v3 v1）（v2 v3 v1 v4）（v3 v1 v4 v3）（v4 v3 v1 v2）有向环

（v1 v2 v4 v1）（v4 v1 v4 v4）(3)各顶点的度、入度、和出度。(4)①邻接表

① 邻接矩阵集。② 逆邻接表

7．3 假设图的顶点是A,B,„,请根据下属的邻接矩阵画出相应的无向图或有向图。

解：

7．4 假设一颗完全二叉树包含A,B,„,G第七个结点，写出其邻接表和邻接矩阵。解：

① 完全二叉树 ② 邻接矩阵 ③ 邻接表

7．5 对n各顶点的无向图和有向图，采用邻接矩阵和邻接表表示，如何判别下列有关问题：

（1）图中有多少条边？（2）任意两个顶点I和j是否有边相连？（3）任意一个顶点的度是多少？ 解：

① 对于无向图

（1）图中边数等于邻接矩阵中1的各数的一半；邻接表中的边表中结点各数的一半。

（2）若邻接矩阵中A[i,j]≠0则I和j两个顶点有边相连。

（3）顶点I的度为第I行中1的个数；邻接表中I的边表结点个数j.② 对于有向图

（1）图中边树等于邻接矩阵中的个数；邻接表中的出边表中结点数。（2）若邻接矩阵中A[i,j]>0则I和j两个顶点有边相连 ；

邻结表中I得出边表是否有结点j，决定I和j两个顶点有边相连。

（3）顶点I的度为第I行中1的个数加上第I列中1的个数之和；

邻接表中i得出边表结点个数加上边表中结点I的个数之和。

7．6 n个顶点的连通图至少有几条边？强连通图呢？ 解：

①n个顶点的连通图至少有n-1条边。②n个顶点的强连通图至少有n条边。

7．7 DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？ 解：

①DFS采用了栈；BFS采用了队列。

②采用BFS。

7．8画出以顶点v1为初始源点遍历图7。25所示的有向图所得到的DFS和BFS生成森林。解：

7．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节中算法CreateALGraph画出相应的邻接表，并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列，及DFS和BFS生成树。解：

依题意构造有向图： ①邻接表

②DFS和BFS序列

DFS序列：4 5 3 1 6 2 BFS序列：4 5 3 6 1 2 ③DFS和BFS生成树

DFS生成树 BFS生成树

7.10什么样的图其最小生成树是唯一的？用Prim和Kruskal求最小生成数的时间各为多少？他们分别适合于哪个图？

解：①具有n的结点，n-1条边的连通图其生成树是唯一的。① 的结点，e条边的无向连通图求最小生成树的时间分别为

Prim: O(n2);Kruskal:O(e*log2e)② Prim适应于稠密图（点少边多）；Kruskal 适应于稀疏图（点多边少）。

7．11 对图7.26所示的连通图，请分别用Pirm和Kruskal 算法构造其最小生成树。解：

① Pirm算法构造的生成树。② Kruskal 算法构造的生成树。

7．12 对图7.27所示的有向网，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行短发过程中扩充红点集的每天次循环状态（类似表7.2）.解：

7．13 是写出图7.28所示有向图的所有拓扑序列，并指出应用教材中 NonPrefirtTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。解：

NonPreFirtTopSort算法求得的序列是： V0 V1 V5 V2 V6 V3 V4 其余序列有多种（略）。

7．14 什么样的DAG的拓扑序列是唯一的？ 解：

设DAG中有n个结点，则当DAG中有至少n-1个不同的后继结点且至少有n-1个前缀结点时其拓扑序列是唯一的。

7．15 以V4为源点，给出用DFS搜索7.28的道德你拓扑序列。V4 V3 V2 V0 V1 V5 V6.（二）算法设计题

7．16 试在无向图的邻接矩阵和邻接表上实现如下算法：（1）往图中插入一个顶点（2）往图中插入一条边（3）删去图中某顶点（4）删去图中某条边 解：

（1）插入给定结点

① 邻接表

viod Inser-ALGraph(ALGraph *G,int k){ int i;G->n++;for(i=G->n;i>k;i--){ G->adjlist[i].vertex=G->adjlist[i-1].vertex;G->adjlist[i].firstedge=G->adjlist[i-1].Firstedge;} G->adjlist[i].vertex=getchar();G->adjlist[i].firstedge=Null;} ② 邻接矩阵

void Inser-Mgraph(mGraph *G,int k){int i,j;G->n++;for(i=G->n;i>k;i--)G->vexs[i]=G->vexs[i-1];G->cexs[k]=getchar();for(i=G->n;i>k;i--){ for(j=G->n;j>k;j--)G->e[i][j]=G->e[i-1][j-1];G->e[i][j]=0;for(j=k-1;j>=0;j--)G->e[i][j]=G->e[i-1][j];} for(j=G->n;j>=0;j--)G->e[i][j]=0;for(i=k-1;i>=0;j--){ for(j=g->n;j>k;j--)G->e[i][j]=G->e[i][j-1];G->e[i][j]=0 } } ⑵插入一条边 ① 邻接表

InsertLAGraph(ALGraph *G,int m,INT n){ EdgeNode *E;EdgeNode *sm=new EdgeNode;EdgeNode *sn=new Edgenode;Sm->adjvex=n;sm->next=Null;Sn->adjvex=m;sn->next=Null;for(E=G->adjlist[m].firstedge;E!=NULL;E=E->next){ } E=sm;for(E=G->adjlist[n].firstedge;E!=NULL;E=E->next){ } E=sn;} ② 邻接矩阵

void InsertLMGraph(mGraph *G,int m,int n){ G->e[m][n]=1;}（3）删除某结点 ① 邻接表

void DelVALGraph(ALGraph *g,int k){ int I;G->n--;EdgeNode *e *s;for(E=G->adjlist[k].firstdge;E!=NULL;E=E->next){ for(s=G->adjlist[E->adjvxe].firstedge;E!=NULL;E->E->next)if(s->adjvex==k){s=s->next;break;} } for(i=k;in;i++){ G->adjlist[i].vertex=G->adjlist[i+1].vextex;G->adjlist[i].first[i].firstedge=G->adjlist[i+1].firstedge;} } ② 邻接矩阵

void delvMGraph(mGraph *G,int k){int i,j;G->n--;for(i=k;in;i++)G->vexs[i]=G->vexs[i+1];for(i=0;ie[i][j]=G->e[i][j];for(i=k;in;i++){for(j=0;je[i][j]=G->e[i+1][j];for(j=k;je[i][j]=G->e[i+1][j];} }(4)删除某条边 ① 邻接表

void dellALGraph(ALGraph *G,int m,int n){EdgeNode *s;for(S=G->adjlist[m].firstedge;s->adjvex!=k;s=s->next)s=s->next;for(s=G->adjlist[n].firstedge;s->adjvex!=k;s=s->next)s=s->next;} ②邻接矩阵

void InsertLMGraph(mGraph *G,int m,int n){G->e[m][n]=0;G->e[n][m]=0;} 7.17 下面的伪代码是一个广度优先搜索算法,试以图7.29中的V4为源点执行该算法,请回答下述问题:(1)对图中顶点Vn+1,它需要入队多少次?它被重复访问多少次?(2)若要避免重复访问同一个顶点的错误,应如何修改此算法? Void BFS(ALGraph *G,int k){//以下省略局部变量的说明,visited各分量初值为假

InitQueue(&Q);//置空队列 EnQueue(&Q,k);//k入队 While(!QueueEmpty(&Q)){I=DeQueue(&Q);//vi出队

visited[I]=true //置访问标记// printf(“%c”,G->adjilist[i],vertes);//访问j for(p=G->adjilist[i],firstedge;p;p=p->adjves=j)//依次搜索vi的邻接点vj(不妨设p->adjves=j)if(!Visited[p->adjves])//若vj未被访问 EnQueue(&Q,p->adjves);//vj入队 } //endwhile } //BFS 解：

对图中顶点vn+1,它需入队n次？它被重复访问n-1次。若要避免重复访问同一个顶点的错误，应修改算法如下： Void BFS(ALGraph*G,int K){ /*以下省略局部变量得说明，visited各分量初值为假*/ InitQueue(&Q);/*置空队列*/ EnQueue(&Q,k);/*k队列*/ While(!QueueEmpty(&Q)){I=DeQueue(&Q);/*vi出队*/ visited[I]=true /*置访问标记*/ printf(“%c”,G->adjilist[i],vertes);/*访问vi*/ for(p=G->adjlist[i],firstedge;p;p->adjves=j)/*依次搜索vi的邻接点vj（不妨设p->adjves=j）*/ if(!Vvisit[p->adjves])/*若vj未访问过*/ { EnQueue(&Q,p->adjves);/*/vj入队*/ Visited[p->adjvex]=TRUE;} } /*endwhile*/ } /*BFS*/ 7.18 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(Ij)之间是否有路径。

解：

/*基于邻接表方式*/ /*所有数据类型*/ #define maxvn 10 typedef struct node { int vertex;int vertex;setuct node *list;} vertexNode vertexNode *head[maxvn];bool JUDGE(vertexNode *adjl[maxvn],int n,int j);/*深度优先搜索判别n个顶点的有向图中顶点I到顶点j是否存在路径*/ { int stack[maxvn];bool visit[maxvm];int top,k;vertexNODE *p;bool yes;for(k=1;kvertex]p=p->link);if(p==NULL)top=top-1;/*p之后无邻接结点，退栈*/ else {i=p->vertex;/*p指向的顶点未访问*/ if(i==j)yes=true;else { visit[i]=true;top=top+1;stack[top]=i;} }while(top1=0&&!yes);return(yes);} 7．19 试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。解：

①/*以Vi为树根，对邻接矩阵表示的图G进行DFS搜索*/ void DFSM(Mgraph *G,int){ int j;printf(“visit vertex:%c”,G->vexs[i]);visitcd[i]=True;for(j=0;jn;j++)if(G->edges[i][j]==1&&!visit[j]){ print(“edye:%d%dn”,i,j);DESM(G,j);} } ②/*以VI为树根，对邻接矩阵表示的图G进行DFS搜索*/ void DFSM(Mgraph *G,int k){ int i,j;SETNULL(Q);/*置空队Q*/ Printf(‘%/“，G.vexs[k]);Visited[k]=True;/*标志Vk+1已经访问过*/ ENQUEUE(Q,k);/* 已经访问过的顶点如队列*/ While(!EMPTY(Q))/*队列非空时执行*/ {i=DEQUEUE(Q);/*队头元素序号出队列*/ for(j=0;j

/*修改DFS函数，每当使visited[i]=true时打印printf（“%D”，i）；可输出各连通分量顶点集。*/ {int i;int m=0;for(i=0;ij)顶点的最短路径；（2）求源点Vi 到其余各顶点的最短路径。

要求输出路径上的所有顶点（提示：利用BFS遍历的思想）解：

利用BFS的遍历思想，同时构造一棵树，使每个孩子结点均指向双亲，当搜索到目标结点时，则从目标回溯到根结点即可，具体算法如下 ：

typedef struct node { int data;struct node *parent;}Tree;void Path(ALGraph,*G,int i,int j)/*以邻接点存储*/ { int k;/*求vi到vj的最短路径*/ CirQueue Q;/*将DataType改为 int */ EdyeNode P;InitQueue(&Q)/*队列初始化*/ Visit[i]=TRVE;/*源点*/ S=(tree)mallo((sizeof(Tree));新建一个结点 s->data=i /*树根*/ s->patent=NULL;EnQueue(&Q,i);/*入队列*/ While(!Queue Empty(&Q)){ k=DeQueue(&Q);p=G->dajlist[k]->firstdeye;while(P){ if(!Visited[p->adjvex]){ visited[p->adjvex]=TRVE;*S=(Tree*)mallo((sizeof(Tree));/*新结点*/ s->data=p->adkvex;s->parent->data=k;EnQueue(&Q,p->adjvex);} /*end if */ if(p->adjvex==j)bread;/*已搜索到j点*/ p-=p->next;} /*end if */ if(p->adjvex==j)break;/*已搜索到j点，结束搜索*/ } /*end if */ while(s!=NULL)/*此时打印出来的路径为反序*/ { printf(“%d”,G->adjlist[s->data]->vertex)s=s->parent;}（2）求源点到其余各顶点最短路径，则可调用上面算法。

Void PathALL(ALGraph *G.int i){int j, for(j=0;fn;j++)if(j!=i)path(G,i,j);} 对于用邻接矩阵存储的图:(1)求顶点vi到顶点vj(i≠j)最短路径

算法思想，采用弗洛伊德算法，可表示为

A[K][i,j]=Min(A k-1[i,j],A k-1[i,k]+A k-1[k.j])(1

算法思想，从给定顶点v4出发进行深度优先搜索，在搜索过程中判断当前访问的顶点是否为v4。若是，则找到一条回路。否则继续搜索。为此设一个顺序栈cycle记录构成回路的顶点序列，把访问顶点的操作改为将当前访问的顶点入栈；相应地，若从某一顶点出发搜索完再回溯，则做退栈操作，同时要求找到的回路的路径应大于2。另外还设置一个found，出值为0，当找到回路后为1。

Void dfscycle(ALGrph *G,int V4){int i,j,top=0,V=V4,found=0,w;int Visitde[100],cycle[100];EdgeNode *P;i=1;cycle[i]=Vi /*从V是开始搜索*/ Visitde[v]==1;P=G[v]->firstedge;While(p!=NULL！top>0)&&!found){ while(p!=NULL&&!found)if(p->adjvex==V4&&iadjvex]==0)p=p->next;/*找到下一个邻接点*/ elst {w=p->adjvex;/*记下路径，继续搜索*/ visited[w]=1;i++;cycle[i]=w;top++;stack[top]=p;p=G[w]->firstedge;} if(!found&&top>0)/*沿原路径退回后，另选路径进行搜索*/ { p=attack[top];top--;p=p->next;i--;} } /*end while*/ if(found){for(j=1;j

算法思想：以有向图的每一个结点为源点对圆进行搜索，若能搜索到每个结点。则该结点为根。否则不是。

Void searchroot（ALGraph *G）{ int i;for(i=0;in;i++){for(j=0;jn;j++)visited[j]=false;/*标志向量初始化*/ DPS(G,i);/*以Vi为源点开始DPS搜索*/ } } void DPS(ALGtaph *G,int i){ int count=0;EdgeNode *P;Visited[i]=true;count ++;p=G->adjlist[i]->firstedge;while(p){if(!Visited[p->adjvex])DPS(G,p->adjvex);P=p->next;} if(count==G->n)/*该结点是根结点*/ printf(“%c”,G->adjlist[i]->vertex);} 7．24 改写7.5节的算法print,试输出的从源点到各终点的最短路径是正想。（提示：使用栈暂存路径）。解：

使用栈暂存路径

void Ptint(PathP,Distance D){ int i,pre;seqstack *S;s->top=-1 /*置空栈*/ for(i=0;itop++;s->stack[s->top]=i;/*i入栈*/ pre=p[i];/*栈终点的前趋*/ while(s->top>1){printf(“%d”,s->stack[s->top]);/*输出路径*/ s->top--;} /*end while */ } /*end for*/ } 7.24改写7.5节的算法print，使输出的从源点到各终点的最短路径是正向。（提示：使用栈暂存路径）。

解：

使用栈暂存路径

void Print(PathP,Distance D){ int ,pre;seqstack *s;s->top=-1 /*置空栈*/ for(i=0;itop++;s->stack[s->top]=i;/*I入栈*/ pre=p[i];/*栈终点的前趋*/ while(pre!=-1){s->top++;s->stack[s->top]=pre;/*路径入栈保存*/ pre=p[pre];/*继续上溯前趋*/ } while(s->top>-1){printf(“%d”,s->stack[s->top]);/*输出路径*/ s->top--;} /*end while*/ } /*end for*/ } 7.25 对7.6节的NonSuccFirstTopSort算法，分别以邻接矩阵和邻接表作为存储结构，写出其具体算法，并分析算法的时间。解：

① 用逆邻接表作为G的存储结构。Void NonSuccPirstTopSort(G){int outdehree[maxvertexNum];/*出度向量，Maxvertexnum>=G,n*/ seqstack S,T;/*应将栈中data向量改为int类型*/ int i,j,count=0;Edgenode *P;for(i=0;iadjlist[i]->firstedge;p;p->next)/*扫描的入边表*/ outdegree[p->adjvex]++;/*出度为1*/ Initstack(&S);/*置空栈*/ Initstack(&T);for(i=0;in;i++)if(outdegree[i]==0)push（&S,i）/*出度为零的顶点i入栈 */ while(!stackEmpty(&S))/*栈非空，即图中有出度为0的顶点*/ {i=pop(&S);push(&T,i);count++;for(p=G->adjlist[i]->firstedge;P;p=p->next);/*扫描的i入边表*/ {j=p->adjvex;/*j是i的入边的起点*/ outdegree[j]--;/*j的出度减肥。相当于删去边*/ if(!outdegree[i])/*j无后继*/ push(&S,j);}/*end for*/ } /*end while*/ if(countn)printf(“n The Graph is not a DAG.n”);/*图中有环，排序失败*/ else {while(!stackEmpty(&S))/*输出拓扑序列*/ {i=po(&T);print(“%d”,G->adjlist[i]->vertex);} } } ②用邻接矩阵作为存储结构。

Void NoSucePirstTopSort(Mgraph *G){seqstack s,T;int i,j,count=0;

/*用i,j代表Vi,Vj*/

Initstack(&S);

Initstack(&T);

for(i=0;in;i++)

for(j=0;jn;j++)

if(G->edges[i][j]= =0)

push(&S,i);

/*出度为0，入栈*/

while(!sruckEmpty(&S))

{ i=po(&S);

push(&T,i);

count+ +;

for(j=0;jn;j++)

G->edges[i][j]=0;

/*修改邻接矩阵*/

for(i=0;in;i++)

for(j=0;jn;j++)

if(G->edges[i][j]= =0)

push(&S,i);

}

/*end while */

if(countn)

printf(“n The Graph is not a DAG.n”);else {while(!stackEmpty(&T))

/*输出拓扑序列*/ {i=pop(&T);

printf(“%d”,G->adjlist[i]->vertex);} } } 7.26设有向图一个DAG，试以邻接矩阵和邻接表作为存储结构，写出对7.6节的DFSTopSort求精的算法。问什么有向图不是DAG时，该算法不能正常工作？

解：

① 用邻接矩阵作为存储结构。

Void DPSTopSort(Mgraph*G,i,Setstack T){int j;visited[i]=true;for(j=0;jm;j++)

/*栈所i有的邻接点j*/ if(G->edges[i][j]= =1)if(!visited[j])DPSTopSort(G,j,T);Push(&T,i);

/*从I出发的搜索已完成，保存i*/ } ② 用邻接表作为存储结构。

Void DPSTopSort(ALGraph G,i,T){int j;visited[i]=true;for(p=G->adjlist[i]->firstedge;p;p=p->next)if(!visited[p->adjvex])DPSTopSort(G,p->adjvex,T);Push(&T,i);} 由于有向图不是DAG时，从某点出发的搜索将陷入循环状态，所以算法不能正常工作。

7．27 利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环 存在时，输出构成环的顶点。解：

设有向图用邻接表存储 Void SearckCycle(ALGraph G){int i;EdgeNode *P;for(i=0;in;i++)

/*对每一个顶点i*/ for(p=G->adjlist[i]->firstedge;p;p=p->next)

/*扫描i的出边表*/ if(p->next=G->adjlist[i]->firstedge)

/*存在环*/ printf(“%d”,G->adjlist[i]->vertex);}