《习题六和上机答案》由会员分享，可在线阅读，更多相关《习题六和上机答案（20页珍藏版）》请在金锄头文库上搜索。
1、习题六 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个顶点的强连通图至少有多少条边，
2、这样的有向图是什么形状？解：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：V21111V311111V411111V511111V611V711111V811111V111111BFS：V11111V31111
3、1V711111V511111V611111V811111V211111V4111116-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*/
4、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 i
5、f(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
6、+; 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;Fo
7、r(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
8、*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)/*广度遍历*/
9、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-
10、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(D
11、FS)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
