习题六和上机答案

习题六 6-1 在下图所示的有向图中，试给出 (1) 每一个顶点的入度和出度； (2) 邻接矩阵； (3) 邻接表； (4) 强连通分量。 题6.1解：顶点123456入度221123出度122312邻接矩阵：邻接表：123456强连通分量：1、6、2、4、5。6-2 在下图所示的有向图中：（1） 该图是强连通的吗？若不是，则给出其强连通分量。（2） 给出图的邻接矩阵、邻接表、逆邻接表。（3） 给出每个顶点的度、入度和出度。解：（1）、是强连通图。（2）、邻接矩阵：邻接表：1234逆邻接表：1234（3）、结点1234入度1112出度2111度32236-3 n个顶点的强连通图至少有多少条边，这样的有向图是什么形状？解：n-1条。环行。6-4 对于下图所示的带权的有向图 (1)写出邻接矩阵； (2)邻接表。 解：（1）、邻接矩阵：（2）、邻接表：1234566-5 分别写出用深度优先搜索法和广度优先搜索法遍历具有6个顶点的完全图的序列。 假设都以v1为出发点。解：深度优先遍历：v1，v2，v3，v4，v5，v6广度优先遍历：v1，v2，v3，v4，v5，v66-6 对下图所示的有向图，从顶点v1出发，分别画出其深度和广度生成树。题6.6解：DFS：V21111VVVV611VVVBFS：V11111VVVVVVV6-7 实现在邻接表上删除一条边，删除一个结点的算法。解：Void delete_side(ALGraph *G,int A,int B)/*A,B为边的两个结点的下标*/Arcnode *p,*q;P=q=G-verticesA.firstarc;/*使p,q指向结点A的后续*/While(p-adjvex!=B&p!=next) q=p; p=p-next; /*寻找边，p指向B，q指向p的前一个*/If(p=NULL) printf(“input errorn”); return; /*删除结点p*/ q-next=p-next;Garcnum-;/*结点数减一*/Free(p);Free(q); Void delete_drop(ALGraph *G,int A)/*A是要删除的结点下标*/Int I；Arcnode *p,*q;For(i=A;ivexnum;i+) /*删除结点A*/G-verticesi=G-verticesi+1;G-vexnum-;For(i=1;ivexnum;i+)/*删除结点的前驱*/P=q=G-verticesi.firstarc; While(p!=NULL)If(p-adjvexA)/*查看是否有结点的信息，有则删除*/p-adjvex-;else if(p-adjvex=A)/*删除结点*/q-next=p-next;Q=p; p=p-next;Free(p);Free(q);6-8 实现计算有向图中各顶点的入度的算法。设有向图用邻接表作为存储结构。解：Void InDegree(ALGraph *G)Int I,countmaxsize;/*记录与下标相同的结点的入度数组*/Arcnode *p;For(i=1;ivexnum;i+)/*数组初始化*/Counti=0;For(i=1;ivexnum;i+)P=G-verticesi.firstarc;While(p!=NULL)/*使相对应的数组每一次加一*/Countp-adjvex+; p=p-next;For(i=1;ivexnum;i+)；/*输出入度*/Printf(“%s InDegree=%d”,G-verticesi.data,counti);Free(p);6-9 实现将一个已知图的邻接矩阵存储形式转移成邻接表的存储形式。解：ALGraph* change(MGraph *T)ALGraph *G;Int I,j;Arcnode *p;G=(ALGraph)malloc(sizeof(ALGraph);For(i=1;ivexnum;i+)/*新图初始化*/ G-verticesi=T-vexsi; G-verticesi.firstarc=NULL;For(i=1;ivexnum;i+)/*矩阵转换成邻接表*/ For(j=1;jvexnum;i+)/*相连则放入邻接表*/If(T-arcsij)P=(Arcnode*)malloc(sizeof(Arcnode);p-adjvex=j;p-next=G-verticesi.firstarcG-verticesi.firstarc=p;G-vexnum=T-vexnum;G-arcnum=T-arcnum;Free(p);return G;6-10 实现在邻接距阵存储结构上实现深度优先遍历和广度优先遍历。解：Int visitedmaxsize;Void DFSTraverse(MGraph *G)/*深度优先遍历*/Int I,visitedmaxsize;For(i=1;ivexnum;i+)/*标记数组初始化*/visitedi=0;for(i=1;ivexnum;i+)if(!visitedi)DFS(G,i);/*对还没有访问的结点调用DFS*/Void DFS(MGraph *G,int v)int I;Visitv=1;/*标记已经调用*/Printf(“-%d,”,G-vexsi);For(i=1;ivexnum;i+)/*深度遍历*/If(!visitedi&G-arcsvi)DFS(G,i);Void BFSTraverse(MGraph *G)/*广度遍历*/LinkQueue Q;Int visitedmaxsize,I,j,e;For(i=1;ivexnum;i+) visitedi=0;/*标记数组初始化*/InitQueue(Q);For(i=1;ivexnum;i+)If(!visitedi) visitedi=1; Printf(“-%d,”,G-vexsi);EnQueue(Q,i);While(!QueueEmtype(Q)e=DeQueue(Q);For(j=1;jvexnum;j+)If(!visitedj&G-arcsej) visitedi=1; Printf(“-%d,”,G-vexsi); EnQueue(Q,i);6-11 实现在邻接表上，深度优先遍历和广度优先遍历的非递归算法。解：int sort(char x)/*查找data值对应的num*/ int i; for(i=1;i=n;i+) if(ai.data=x) return(ai.num); return(0);int compare(int x,int b)/*查找有没有处理过*/ int i; for(i=0;bi!=NULL;i+) if(x=bi) return(1); return(0);void DFS(JD a)/*深度优先遍历*/ int i,j,x,y,queueN,stackN; char m; JD *p; printf(DFS)input the vertex you want to search first:);getchar(); scanf(%c,&m); y=sort(m); if(y=0) printf(not exist!);return; for(i=0;inum,queue)!=0&p!=NULL) p=p-next; if(p!=NULL) printf( %d %c ,ap-num.num,ap-num.data); stack+j=queuei+=p-num; p=ap-num.next; p=&astack-j; while(j=0); printf(n);void BFS(JD *a)/*广度有限遍历*/ JD *p; char m; int y,i=0,j=0; int queueN=0; printf(BFS)input the vertex you want to search first:);getchar(); scanf(%c,&m); y=sort(m); if(y=0) printf(not exist!);return; do p=&ay; while(p!=NULL) if(compare(p-num,queue)=0) queuei+=p-num; printf( %d %c,p-num,ap-num.data); p=p-next; y=queue+j; while(queuej!=0);6-12 自选存储结构，实现判别无向图中任意给定的两个顶点之间是否存在一条长度为K 的简单路径的算法。解：int visitedMAXSIZE; int exist_path_len(ALGraph G,int i,int j,int k)/判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 if(i=j&k=0) return 1; /找到了一条路径,且长度符合要求 else if(k0) visitedi=1; for(p=G.verticesi.firstarc;p;p=p-nextarc) l=p-adjvex; if(!visitedl) if(exist_path_len(G,l,j,k-1) return 1; /剩余路径长度减一 /for visitedi=0; /本题允许曾经被访问过的结点出现在另一条路径中 /else return 0; /没找到/exist_path_len6-13有边集，求此图的所有可能的拓扑序列。若以此顺序输入建立图的邻接表，再在此存储储结构上执行toposort过程。 则得到的拓扑序列是哪一种？解：拓朴序列：1-5-2-3-6-4;1-5-6-2-3-4;1-5-2-6-3-4; 5-1-2-3-6-4;5-1-6-2-3-4;5-1-2-6-3-4;所得序列：5-1-6-2-3-4;6-14 对于下列图中AOE_网，求出各活动可能的最早开始时间和可能的最早开始时间， 并问：整个工程的最短完成时间是多少？哪些活动是关键活动？ 是否有哪项活动提高速度后能导致整个工程提前完成？题6.14解：活动SASBSDSFSGSIACBCDCDEDJFE可能的最早开始时间000000163334可能的最早开始时间163431781018930活动FHGTGHIHHCCEHKKJHJJEETJT可能的最早开始时间43311310132213313431可能的最早开始时间9351371718223131344444最短完成时间：44关键活动：SA、SB、SD、SF、SG、SI、AC、BC、DC、DJ、FH、GH、IH、HC、CE、HK、KJ、JE、ET。提高速度后能导致整个工程提前完成的活动：SA、SB、SD、SF、SG、SI、AC、BC、DC、DJ、FH、GH、IH、HC、CE、HK、KJ、JE、ET。6-15 对题6.4所示的有向网，试利用Dijkstra算法求从源点1到其他各顶点的最短路径。解：顶点最短路径长度1-21、3、2191-31、3151-41、2、6、4291-51、3、2、5291-61、3、6256-16 对下图所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。 题6-16解：Struct /*辅助数组*/VertexType adjvex;VRType lowcost;node;Void MiniSpanTree_Prim(MGraph *G,int u)/*u是默认开始的那个元素的下标*/node closedgemaxsize;int i,k,j;for(i=1;ivexnum;i+)/*辅助数组初始化*/if(i!=k&G-arcsui) closedgei.adjvex=i; closedgei.lowcost=G-arcsui.adj;closedgeu.lowcost=0;For(i=1;ivexnum;i+)K=10000;For(j=1;jvexnum;j+)/*取最小的一个权值的点的下标*/If(closedgej.lowcost&closedgej.lowcostvexsk);closedgek.lowcost=0;for(j=1;jvexnum;j+)/*更新数组，使其最小*/if(G-arcskj.adjarcskj.adj) closedgei.adjvex=i; closedgei.lowcost=G-arcsui.adj;Void MiniSpanTree_Kruskal(MGarph *G)/*克鲁斯卡尔算法*/Int i,j,k,min,x,y,visitedmaxsize,t=1;For(i=1;ivexnum;i+)/*辅助数组初始化*/Visitedi=0;For(i=1;ivexnum;)/*找出其G-vexnum-1条边，i表示边数*/min=10000;For(j=1;jvexnum;j+)/*找出小的权值，x,y记下边的两个结点*/For(k=1;kvexnum;k+)if(G-arcsjk.adjarcsjk.adj) min=G-arcsjk.adj; x=j; y=k;G-arcsxy.adj=0;/*标记已经找过的边*/If(visitedx|visitedy) printf(“(%d-%d-%d)”,x,min,y); i+; 6-17 设计算法，求有向图的深度和广度优先遍历的生成森林。解：为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这个算法，以建立生成森林。te mplate void Graph : DFS_Tree ( const int v, int visited , TreeNode *t ) /从图的顶点v出发, 深度优先遍历图, 建立以t (已在上层算法中建立)为根的生成树。Visitedv = 1; int first = 1; TreeNode * p, * q;int w = GetFirstNeighbor ( v ); /取第一个邻接顶点while ( w != -1 ) /若邻接顶点存在if ( vositedw = 0 ) /且该邻接结点未访问过p = new TreeNode ( GetValue (w) ); /建立新的生成树结点if ( first = 1 ) /若根*t还未链入任一子女 t-setFirstChild ( p ); first = 0; /新结点*p成为根*t的第一个子女else q-setNextSibling ( p ); /否则新结点*p成为*q的下一个兄弟q = p; /指针q总指示兄弟链最后一个结点DFS_Tree ( w, visited, q ); /从*q向下建立子树w = GetNextNeighbor ( v, w ); /取顶点v排在邻接顶点w的下一个邻接顶点下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。template void Graph : DFS_Forest ( Tree & T ) /从图的顶点v出发, 深度优先遍历图, 建立以左子女-右兄弟链表表示的生成森林T。T.root = NULL; int n = NumberOfVertices ( ); /顶点个数TreeNode * p, * q;int * visited = new int n ; /建立访问标记数组for ( int v = 0; v n; v+ ) visitedv = 0;for ( v = 0; v n; v+ ) /逐个顶点检测if ( visitedv = 0 ) /若尚未访问过p = new TreeNode ( GetValue ( v ) ); /建立新结点*pif ( T.root = NULL ) T.root = p; /原来是空的生成森林, 新结点成为根else q- setNextSibling ( p ); /否则新结点*p成为*q的下一个兄弟q = p;DFS_Tree ( v, visited, p ); /建立以*p为根的生成树6-18 设计算法，求有向图的强连通分量。解：int visitedMAXSIZE;int finishedMAXSIZE;int count; /count在第一次深度优先遍历中用于指示finished数组的填充位置 void Get_SGraph(OLGraph G)/求十字链表结构储存的有向图G的强连通分量 count=0; for(v=0;vG.vexnum;v+) visitedv=0; for(v=0;vG.vexnum;v+) /第一次深度优先遍历建立finished数组 if(!visitedv) DFS1(G,v); for(v=0;v=0;i-) /第二次逆向的深度优先遍历 v=finished(i); if(!visitedv) printf(n); /不同的强连通分量在不同的行输出 DFS2(G,v); /for/Get_SGraph void DFS1(OLGraph G,int v)/第一次深度优先遍历的算法 visitedv=1; for(p=G.xlistv.firstout;p;p=p-tlink) w=p-headvex; if(!visitedw) DFS1(G,w); /for finished+count=v; /在第一次遍历中建立finished数组/DFS1 void DFS2(OLGraph G,int v)/第二次逆向的深度优先遍历的算法 visitedv=1; printf(%d,v); /在第二次遍历中输出结点序号 for(p=G.xlistv.firstin;p;p=p-hlink) w=p-tailvex; if(!visitedw) DFS2(G,w); /for/DFS26-19 用Dijstra和Floyed算法求题6.4所示有向网，源点为1的最短路径，写出执行算法过程中各步的状态。解：Dijstra 算法终点从1点到个终点的D值和最短路径的求解过程i=1i=2i=3i=4i=5i=6v1无穷无穷无穷无穷无穷无穷无v220(1,2)19(1,3,2)v315(1,3)v4无穷无穷无穷29(1,3,6,4)v5无穷无穷29(1,3,2,5)29(1,3,2,5)29(1,3,2,5)v6无穷25(1,3,6)25(1,3,6)vj32645S1,31,3,21,3,61,3,6,41,3,2,5以1为中转 以2为中转020152 01710304010015041000201530502 0171030640141001504100以3为中转 以5为中转0191529252 0171027640141001504100019154429252 01725102764029141001504100 以6为中转019152929252 01725102764014141001504100第六章上机内容：6.1、 设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。解：int jurdge()/*判断是否为连通图*/ int i,j,k,x,queueN,stackN; JD *p; for(i=0;inum,queue)!=0&p!=NULL) p=p-next; if(p!=NULL) stack+j=queuei+=p-num; p=ap-num.next; p=&astack-j; while(j=0); for(k=1;k=n;k+) if(compare(k,queue)=0) return 0; return 1;6.2、 建立一个邻接表存储结构的图G，分别设计实现以下功能的算法：求出图中每个顶点的出度；计算图中出度为0的顶点数。解：#define NULL 0#define N 10typedef struct graph int num; struct graph *next;JD;JD aN;JD *creat(int n) int i,x,y; JD *p; for(i=1;i=n;i+) printf(num=); scanf(%d,&ai.num); if(ai.num=0) printf(wrong!); return(NULL); ai.next=NULL; do printf(input edge:); scanf(%d,%d,&x,&y); if(x!=0) p=(JD *)malloc(sizeof(JD); p-num=y; p-next=ax.next; ax.next=p; while(x!=0); return(a);void outdegree(JD a,int n) JD *p; int i,u,v=0; for(i=1;inext!=0) p=p-next; u+; printf(the outdegree of vertex %d is %d.n,i,u); if(u=0) v+; printf(the number of the vertex with a 0 outdegree is:%d,v);main() int n; JD *p; printf(how many vertex:); scanf(%d,&n); if(n=0) printf(empty graph!); else p=creat(n); if(p!=NULL) outdegree(p,n); getch();6.3、 设计一个算法创建一个带权（路径）的无向图，输出从V0到其它各个顶点的最短路径长度和路径。提示：采用Dijstra算法求一个顶点到其它所有顶点的最短路径。解：void ALGraph_DIJ(ALGraph G,int v0,Pathmatrix &P,ShortestPathTable &D)/在邻接表存储结构上实现迪杰斯特拉算法 for(v=0;vnextarc) Dp-adjvex=*p-info; /给D数组赋初值 for(v=0;vG.vexnum;v+) finalv=0; for(w=0;wG.vexnum;w+) Pvw=0; /设空路径 if(DvINFINITY) Pvv0=1; Pvv=1; /for Dv0=0;finalv0=1; /初始化 for(i=1;iG.vexnum;i+) min=INFINITY; for(w=0;wG.vexnum;w+) if(!finalw) if(Dwnextarc) w=p-adjvex; if(!finalw&(min+(*p-info)Dw) /符合迪杰斯特拉条件 Dw=min+edgelen(G,v,w); Pw=Pv; Pww=1; /构造最短路径 /for /for/ALGraph_DIJ分析:本算法对迪杰斯特拉算法中直接取任意边长度的语句作了修改.由于在原算法中,每次循环都是对尾相同的边进行处理,所以可以用遍历邻接表中的一条链来代替.6.4、 最小生成树问题。基本要求：利用克鲁斯卡尔算法求网的最小生成树，输出构造生成树过程中的连通分量，以文本形式输出生成树中各条边以及他们的权值。解：void kruscal(edgeset ge,edgeset c,int n)/利用kruscal算法求边集数组ge（按权值递增存储）所示图的最小生成树/树中每条边依次存于数组c中 int i; arcnode *p; adjlist s;/链接表s作为集合使用，其中每一个单链表si用来表示一个集合，若一个顶点属于 /这个集合，则对应该单链表中的一个结点，该结点的adjvex域的值为该顶点序号。 for (i=0;i adjvex=i;p-nextarc=NULL; si=p; int k=1;/k表示待获取的最小生成树中的边数，初值为1 int d=0;/d 表示ge中待扫描边元素的下标位置，初值为0 int m1,m2;/m1,m2用来