《数据结构书本习题附标准答案(续)》由会员分享，可在线阅读，更多相关《数据结构书本习题附标准答案(续)（48页珍藏版）》请在金锄头文库上搜索。
1、7.5 对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题? (1) 图中有多少条边? (2)任意两个顶点i和j是否有边相连? (3) 任意一个顶点的度是多少?答：对于n个顶点的无向图和有向图，用邻接矩阵表示时： (1)设m为矩阵中非零元素的个数无向图的边数=m/2有向图的边数=m(2)无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。(3)对于无向图，任一顶点i的度为第i行中非零元素的个数。对于有向图，任一顶点i的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度之和。当用邻接表表示时：(1)对于无向图，图中的
2、边数=边表中结点总数的一半。对于有向图，图中的边数=边表中结点总数。(2)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。对于有向图，则表示有出边相连。(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)7.6 n个顶点的连通图至少有几条边?强连通图呢?答：n个顶点的连通图至少有n-1条边，强连通图至少有2(n-1)条边。7.7 DFS和BFS遍历各采用什么样的数据结构来暂存顶点
3、?当要求连通图的生成树的高度最小，应采用何种遍历?矚慫润厲钐瘗睞枥庑赖。答： 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生成树。答：相应的邻接表如下： 11 5 3 4 6 2 22 6 1 33 5 4 1
4、 44 5 36 1 55 3 1 4 6 66 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 v1v5v0v6v2v
6、3v4 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 V5鹅娅尽損鹌惨歷茏鴛賴。7.16 试在无向图的邻接矩阵和邻接链表上实现如下算法：(1)往图中插入一个顶点(2)往图中插入一条边(3)删去图中某顶点(4)删去图中某条边解：(一)用邻接矩阵表示#define MaxVertexNum l00 /最大顶点数，应由用户定义typedef char VertexType； /顶点类型应由用户定义typedef int EdgeType； /边上的权值类型应由
8、用户定义typedef structVextexType 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(MGra
9、ph *G,VertexType x,VertexType 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=
10、-1;for(k=0;kn;k+)/查找X的编号if (g-vexsk=x) i=k;if (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)删去图中某条边voi
11、d DeleteedgeMGraph(MGraph *G,VertexType x,VertexType 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 vnode /顶点表结点 VertexType vertex； /顶点域EdgeNode *firstedge；/边表头指针 VertexNode；typedef VertexNode AdjListMaxVertexNum；/AdjList是邻接表类型渗釤呛俨匀谔鱉调硯錦。typedef struct AdjLis
