数据结构课后答案java版第5章.pdf-资料库

第 5 章图结构 1.简答题（1）对于如图 5-41 所示的有向图，试给出： 1）每个顶点的入度和出度； 2）邻接矩阵； 3）邻接表； 4）逆邻接表； 5）强连通分量。 ① ② ④ ③ ⑤ ⑥ （图 5-41）【解答】 1）每个顶点的入度和出度：顶点 1（2,1）、顶点 2（2,2）、顶点 3（1,3）、顶点 4（3,0）、顶点 5（2,3）、顶点 6（1,2）。 2）邻接矩阵： 3）邻接表： 0 1 2 3 4 5 1 2 3 4 5 6 ^ 3 ^ 0 3 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 2 ^ 4 1 4 ^ 5 ^ 3 ^

4）逆邻接表： 0 1 2 3 4 5 1 2 3 4 5 6 5）强连通分量： 1 4 1 ^ 0 2 2 ^ 4 ^ 5 ^ 2 5 ^ 4 ^ v5 v4 v7 v6 （图 5-42）（2）设无向图 G 如图 5-42 所示，试给出： 1）该图的邻接矩阵； 2）该图的邻接表； 3）该图的多重邻接表； 4）从 V1 出发的“深度优先”遍历序列； 5）从 V1 出发的“广度优先”遍历序列。 v2 v3 v1 【解答】 1）该图的邻接矩阵： 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0

2）该图的邻接表： 0 1 2 3 4 5 6 v1 v2 v3 v4 v5 v6 v7 1 0 0 3 3 3 4 3）该图的多重邻接表： 2 ^ 2 ^ 2 ^ 2 6 ^ 6 ^ 5 ^ 4 5 ^ v1 v2 v3 v4 v5 v6 v7 ^ 0 1 0 ^ 2 3 1 ^ 3 2 ^ 3 4 ^ 3 ^ 5 6 4 ^ 6 ^ 5 ^ 4）从 v1 出发的“深度优先”遍历序列：v1v2v4v3v5v7v6 5）从 v1 出发的“广度优先”遍历序列：v1v2v3v4v5v6v7 （3）用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？【解答】设图的顶点个数为 n(n≥0)，则邻接矩阵元素个数为 n2，即顶点个数的平方。矩阵元素的个数与图的边数无关。（4）设有向图 G 如图 5-43 所示，试画出图 G 的十字链表结构，并写出图 G 的两个拓扑序列。 v1 v2 v3 v5 v6 v4 图 5-43

【解答】 1）G 的十字链表结构： 0 v1 ^ 1 v2 2 v3 3 v4 ^ 4 v5 0 1 0 2 ^ ^ 1 4 1 5 ^ ^ 2 5 ^ 4 3 ^ 5 v6 5 3 ^ 5 4 ^ ^ 2）G 的两个拓扑序列：v1v2v3v6v5v4; v1v3 v2v6v5v4 （5）如图 5-44 所示 AOE 网： 1）列出各事件的最早、最迟发生时间； 2）列出各活动的最早、最迟发生时间； 3）找出该 AOE 网中的关键路径，并回答完成该工程需要的最短时间。 a1=3 A 1）ve(A)=0 a2=5 B a3=6 a4=7 C a5=9 a6=10 D E a9=5 F a10=3 H a7=8 a8=6 G a11=2 图 5-44 ve(D)=max(ve(B)+6, ve(C)+7)=12 ve(F)= max(ve(D)+10, ve(G)+6)=26 vl(H)=29 vl(G)=min(vl(H)–2, vl(F)–6)=20 vl(B)=vl(D)–6=6 ve(B)= ve(A)+3=3 ve(H)= max(ve(E)+E, ve(G)+2, ve(F)+3)=29 vl(F)= vl(H)–3=26 vl(D)=min(vl(E)–9, vl(F)–10, vl(G)–8)=12 vl(A)=min(vl(B)–3, vl(C)–5)= 0 ve(C)= ve(A)+5=5 ve(E)= ve(D)+9=21 vl(E)= vl(H)–5=24 ve(G)=ve(D)+8=20 2） e(a1)=0 e(a2)=0 vl(C)=vl(D)–7=5 e(a3)=3 e(a4)=5 e(a5)=12 e(a6)=12 e(a7)=12 l(a1)=3 (a7)=12 e(a8)=20 l(a2)=0 l(a8)=20 e(a9)=21 l(a3)=6 l(a9)=24 e(a10)=26 l(a4)=5 l(a10)=26 e(a11)=20 l(a5)=15 l(a11)=27 l(a6)=16

D A 3）关键路径如下图，完成该工程需要的最短时间：29 a8=6 G a10=3 a4=7 a7=8 a2=5 C H F 2.算法设计题（1）试以邻接矩阵为存储结构实现图的基本操作：InsertVex(G,v)、InsertArc(G,v,w)、 DeleteVex(G,v)和 DeleteArc(G,v,w)。【解答】算法如下： public static void InsertVex (MGraph G, int v) {int i,j; for(i=G.vexnum;i>v;i--) G.vexs[i]=G.vexs[i-1]; G.vexs[v]=getchar(); for(i=G.vexnum;i>v;i--) {for(j=G.vexnum;j>v;j--) G.edges[i][j]=G.edges[i-1][j-1]; G.edges[i][v]=0; for(j=v-1;j>=0;j--) G.edges[i][j]=G.edges[i-1][j]; } //在图 G 中插入一个顶点做为第 v 个顶点 //腾出第 v 个顶点值的位置 G.vexnum; //插入第 v 个顶点的值 //第 v 行以后和第 v 列以后的元素后移一行一列 //将第 v 行以后行的 v 列赋 0 //第 v 行以后第 v 列以前的元素后移一行 for(j=G.vexnum;j>=0;j--) G.edges[k][j]=0; //将第 v 行的元素赋 0 for(i=v-1;i>=0;j--) //第 v 行以前第 v 列以后的元素后移一列 {for(j=G.vexnum;j>k;j--) G.edges[i][j]=G.edges[i][j-1]; G.edges[i][v]=0 } } //将第 v 行以前的 v 列赋 0 public static void InsertArc (MGraph G, int v, int w)//在图 G 中序号为 v,w 的顶点之间插入一条边 {G.edges[v][w]=1; G.edges[w]p[v]=1; G.edgenum++; } public static void DeleteVex (MGraph G, int v) //在邻接矩阵表示的图 G 中删除序号为 v 的点 {int i,j; G.vexnum--; for(i=v;i<=G.vexnum;i++) 　　　　　 G.vexs[i]=G.vexs[i+1]; for(i=0;i

G.edges[i][j]=G.edges[i][j＋1]; for(i=v;i<=G->n;i++) {for(j=0;jv;i--) //将原图中从 n 到 v 的结点后移一个位置 {G.adjlist[i].vertex=G.adjlist[i-1].vertex; G.adjlist[i].firstedge=G.adjlist[i-1].Firstedge; } G.adjlist[v].vertex=getchar( ); G.adjlist[v].firstedge=NULL; //将插入点放入 } public static void InsertArc (ALGraph G, int v, int w)//在图 G 中序号为 v,w 顶点之间插入一条边 {EdgeNode E; EdgeNode sm=new EdgeNode; EdgeNode sn=new EdgeNode; sm.adjvex=w; sm.next=G.adjlist[m].firstedge; sn.adjvex=v; sn.next= G.adjlist[m].firstedge; G.adjlist[v].firstedge＝sm； G.adjlist[v].firstedge＝sn； G.edgenum++; //将边结点插入到边表首部 } public static void DeleteVex (ALGraph G, int v)//在邻接表表示的图 G 中删除序号为 v 的点 {int i; G.vexnum--; EdgeNode e,s,p,q; for(q=e=G.adjlist[v].firstedge;e;q=e,e=e.next,free(q)) {s=G.adjlist[e.adjvex].firstedge; p=s;

for(;s;p=s, s=s.next) if(s.adjvex==v) {if(p!=s) p.next=s.next; else (G.adjlist[e.adjvex].firstedge=s.next;)} if(s) free(s); break; } } for(i=v;i

{p= G.adjlist[i].firstedge; //取指向邻接表的指针 while (p!=null) {j=p->adjvex; //申请边结点空间 s= new EdgeNode; s.adjvex=i; s.next= H.AdjList[i] [j].firstedge; H.AdjList[i] [j].firstedge=s; p=p.next; } //下一个邻接点 } } （6）试写一算法，由图的邻接表存储得到图的十字链表存储。算法略。（7）写一算法，由依次输入图的顶点数目、边的数目、各顶点的信息和各条边的信息建立无向图的邻接多重表。算法略。（8）试写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点 vi 到顶点 vj 的路径（i≠j）。假设分别基于下述策略： 1）图的深度优先搜索； 2）图的广度优先搜索。【提示】在有向图中，判断顶点 vi 和顶点 vj 间是否有路径，可采用遍历的方法，从顶点 vi 出发，不论是深度优先遍历（dfs）还是广度优先遍历（bfs），在未退出 dfs 或 bfs 前,若访问到 vj，则说明有通路，否则无通路。设一全程变量 flag。初始化为 0，若有通路，则 flag=1。 1）基于图的深度优先搜索算法： //全局变量，访问数组初始化*/ int visited[]=0; public static int DFS(ALGraph G, int vi) //以邻接表为存储结构的有向图 G，判断顶点 vi 到 vj 是否有通路,返回 1 或 0 表示有或无 //若顶点 vi 和 vj 不是编号，必须先用顶点定位函数,查出其在邻接表顶点向量中的下标 i 和 j //visited 是访问数组，设顶点的信息就是顶点编号 //第一个邻接点 //vi 和 vj 有通路 {visited[vi]=1; p=G.adjlist[vi].firstedge; while(p!=NULL) {if(vj==j) {flag=1; Return(1);} if(visited[j]==0) DFS(G, p.adjvex); p=p.next; } if (!flag) return(0); } 2）基于图的广度优先搜索算法：思想是用一栈存放遍历的顶点，遇到顶点 vj 时输出路径。 public static void BFS(ALGraph G, int i) //有向图 G 的顶点 vi（编号 i）和顶点 vj（编号 j）间是否有路径，如有，则输出。 {int n; Init_Stack(S); //S 是存放顶点编号的栈

资料库

数据结构课后答案java版第5章.pdf

相关推荐

课程资源

热门标签

最新资料