第七章参考答案 四、简答及应用 用邻接矩阵表示法来表示一个具有n个顶点的图时,除了用邻接矩阵中的n×n个元 素存储顶点问相邻关系外,往往还需要另设一个数组存储n个顶点的信息。类型定义如下 #t define vnum 20 typedef struct graph i Vertex Type vex[ vnum I 体*顶点信息* arcs( vnum] [vnum];/*邻接矩阵* vexnum, arcum;/*顶点数,弧(边)数*/ i GraphTp 若图中每个顶点只含有一个编号(1=i<=num),则只需一个二维数组表示图的邻接 矩阵。此时存储结构可简单说明如下: define vnum 20 typedef Int GraphTp vnum][vnum I 2.单链表中每一个结点称为表结点,应包括两个域:邻接点域,用以存放与v相邻接 的顶点序号;链域,用以指向同ⅵ邻接的下一个结点。另外,每一个单链表设一个表头结 点。每一个表头结点有两个域,一个用来存放顶点v的信息:另一个域用来指向邻接表中 的第一个结点。为了便于管理和随机访问任一顶点的单链表,将所有单链表的头结点组织成 个一维数组。邻接表的类型定义如下: # define nun顶点个数 typedef struct arcnode i int adjvex *下一条弧(边)的始点编号* struct arcnode nextarc /*指向下一条弧(边)的指针 g ArcNode Tp; typedef struct vexnode vertex /*顶点编号* AarcNodeTp firstarc;/*指向第一条弧(边)的指针 i AdjList vnum] typedef struct graph f AdjList adjlist vexnum-archum /*顶点和弧(边)的个数* i GraphTp 3.g1的邻接矩阵如下: g1的邻接表如图简答题3-1所示。 4.Gg2的邻接矩阵如下: g2的邻接表如图简答题41所示 5.深度优先搜索序列VsV4V3V2V1 广度优先搜索序列ⅤsV4VsV2V1 图的深度优先搜索和广度优先搜索的顶点序列不是惟一的。 6.答案见图简答题6-2 7.答案见图简答题7-2 8.图简答题8-1的拓扑排序序列:V3,V1,V4,Vs,V2,V6 9网图简答题9-1的邻接矩阵如下:
1 第七章 参考答案 四、简答及应用 1.用邻接矩阵表示法来表示一个具有 n 个顶点的图时，除了用邻接矩阵中的 n×n 个元 素存储顶点问相邻关系外，往往还需要另设一个数组存储 n 个顶点的信息。类型定义如下： ＃define vnum 20 typedef struct graph { VertexType vexs[ vnum ] ; /* 顶点信息 */ int arcs[vnum ] [vnum ] ; /* 邻接矩阵 */ int vexnum , arcnum ; /* 顶点数，弧（边）数 */ } GraphTp ; 若图中每个顶点只含有一个编号( 1 <= i <= vnum ),则只需一个二维数组表示图的邻接 矩阵。此时存储结构可简单说明如下： # define vnum 20 typedef int GraphTp [vnum] [vnum ] ; 2．单链表中每一个结点称为表结点，应包括两个域：邻接点域，用以存放与 vi 相邻接 的顶点序号；链域，用以指向同 vi 邻接的下一个结点。另外，每一个单链表设一个表头结 点。每一个表头结点有两个域，一个用来存放顶点 vi 的信息；另一个域用来指向邻接表中 的第一个结点。为了便于管理和随机访问任一顶点的单链表，将所有单链表的头结点组织成 一个一维数组。邻接表的类型定义如下： #define vnum 顶点个数 typedef struct arcnode { int adjvex ; /* 下一条弧（边）的始点编号 */ struct arcnode nextarc; /* 指向下一条弧（边）的指针 */ } ArcNodeTp ; typedef struct vexnode { int vertex; /* 顶点编号 */ AarcNodeTp firstarc ; /* 指向第一条弧（边）的指针 */ }AdjList[vnum] ; typedef struct graph { AdjList adjlist ; int vexnum ,arcnum ; /* 顶点和弧（边）的个数 */ }GraphTp ; 3．g1 的邻接矩阵如下： g1 的邻接表如图简答题 3-1 所示。 4．Gg2 的邻接矩阵如下： g2 的邻接表如图简答题 4-1 所示。 5．深度优先搜索序列 V5 V4 V3 V2 V1. 广度优先搜索序列 V5 V4 V3 V2 V1. 图的深度优先搜索和广度优先搜索的顶点序列不是惟一的。 6．答案见图简答题 6-2 7．答案见图简答题 7-2 8．图简答题 8-1 的拓扑排序序列：V3 ,V1, V4, V5, V2,V6. 9.网图简答题 9-1 的邻接矩阵如下：
10答案见图简答题10-2 11(1)有11条弧: (2顶点i之间有弧的条件是A[ij<0 (3)顶点i的出度是以顶点ⅱ为起点的弧的个数或A[i]<0的个数(k=0,1,2, 12(1)图简答题11-1每个顶点的入、出度 顶点 入度 出度 vvvvvv 2 022313 (2)邻接矩阵如下 (3)邻接表和逆邻接表见图简答题12-1 (4)逆邻接表如下 13.根据图简答题13-1进行拓扑排序,得出5个拓扑序列为 V1, V9, V3, V4, V9, V2, V7, V5, v6 V1, V4, V3, V9, V3, V,, V5, V8, v6 V9, V3, VI. V4. V2. V7. V5. V8. V6 14.(1)邻接矩阵非零元素个数的总和除以2 (2)当A[ij]∞0或A[ij]心0时,表示两顶点i之间有边相连 (3)计算邻接矩阵上任一行非零元素的个数。 15.(1)深度优先搜索顶点序列:V1,V2,V3,Vs,V4 (2)广度优先搜索顶点序列:V,V2,Vs,V,V3 (3)由深度优先搜索得到的一棵生成树如图简答题15-2所示 (4)由广度优先搜索得到的一棵生成树如图简答题15-2所示 16.(1)按题中顺序输入各条边后建立起来的邻接表如图简答题16所示。 (2)在邻接表上进行深度优先遍历所得到的DFS序列为4,5,3,1,6,2:在邻接 表上进行广度优先遍历所得到的BFS序列为4,5,3,6,1,2 17.假设无向连接通网络为G=(V,E),而构造出的最小生成树为T(U,TE)。初始时,U 中只有一个顶点(即出发点),而T=￠。应用prim算法的操作步骤是: ①将出发点用实线画出(表示出发点属于U集合) ②查找所有虚线顶点连接到实线顶点上的边的权值(若其顶点到出发点无边,则认为 它们之间有一条权值为∞的边),找出权值最小的那条边 ③将找出的权值最小的边改为用实线画出(表示将该条边加入TE中),将该条边的另 顶点也用实线画出(表示将该顶点加入到U中) ④调整所有虚线顶点到实线顶点边上的权值,原则是用权值较小的边取代权值较大的 ⑤如果V<>U,重复执行第②步,否则退出 按照上述操作步骤,最小生成树的构造过程如图简答题17-2所示。 五、算法设计 本题算法思路是:先设置一个空的邻接表,然后在邻接矩阵上查找值不为空的元素
2 10.答案见图简答题 10-2 11.⑴有 11 条弧； ⑵顶点 i,j 之间有弧的条件是 A[ i,j ] <> 0 ; ⑶顶点 i 的出度是以顶点 ii 为起点的弧的个数或 A[i,k] <> 0 的个数(k=0,1,2,…，9)。 12.⑴图简答题 11-1 每个顶点的入、出度 顶点 入度 出度 V1 3 0 V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 3 ⑵邻接矩阵如下： ⑶邻接表和逆邻接表见图简答题 12-1 ⑷逆邻接表如下： 13．根据图简答题 13-1 进行拓扑排序，得出 5 个拓扑序列为： V1, V4, V2, V7, V9, V3, V3, V8, V6 V1, V9, V3, V4, V9, V2, V7, V5, V6 V1, V4, V2, V9, V3, V7, V5, V8, V6 V9, V3, V1, V4, V2, V7, V5, V8, V6 V9, V1, V4, V2, V3, V7, V5, V8, V6 14．⑴邻接矩阵非零元素个数的总和除以 2. ⑵当 A[ i,j ] <> 0 或 A[ i,j ] <> 0 时，表示两顶点 i,j 之间有边相连。 ⑶计算邻接矩阵上任一行非零元素的个数。 15．⑴深度优先搜索顶点序列：V1, V2, V3, V5, V4 . ⑵广度优先搜索顶点序列：V1, V2, V5, V4, V3 . ⑶由深度优先搜索得到的一棵生成树如图简答题 15-2 所示。 ⑷由广度优先搜索得到的一棵生成树如图简答题 15-2 所示。 16．⑴按题中顺序输入各条边后建立起来的邻接表如图简答题 16 所示。 ⑵在邻接表上进行深度优先遍历所得到的 DFS 序列为 4，5，3，1，6，2；在邻接 表上进行广度优先遍历所得到的 BFS 序列为 4，5，3，6，1，2. 17．假设无向连接通网络为 G=( V, E ) ,而构造出的最小生成树为 T(U,TE)。初始时，U 中只有一个顶点（即出发点），而 TE=￠。应用 prim 算法的操作步骤是： ① 将出发点用实线画出（表示出发点属于 U 集合）； ② 查找所有虚线顶点连接到实线顶点上的边的权值（若其顶点到出发点无边，则认为 它们之间有一条权值为∞的边），找出权值最小的那条边； ③ 将找出的权值最小的边改为用实线画出（表示将该条边加入 TE 中），将该条边的另 一顶点也用实线画出（表示将该顶点加入到 U 中）； ④ 调整所有虚线顶点到实线顶点边上的权值，原则是用权值较小的边取代权值较大的 边； ⑤ 如果 V<>U，重复执行第②步，否则退出。 按照上述操作步骤，最小生成树的构造过程如图简答题 17-2 所示。 五、算法设计 1．本题算法思路是：先设置一个空的邻接表，然后在邻接矩阵上查找值不为空的元素
找到后在邻表的对应单链表中插入相应的边的表结点。 void mattolist( int al[, AdjList b[, int n) /*n为图的结点个数* i for(i=0; i<n; i++)b[i] firstarc=NULL /邻接表置空* for(i=0; i<n; 1++) /*逐行进行* for(=n-1;j>=0,j-) if(a[[j]=0) p=( ArcNodeTp*) mollo(sizeof( ArcNode Tp),陣*产生邻接点* p->adjvex= /*插入到表头* re=bi]. firstar bi]. firstarc=p 2.本题的算法思路是:先建一个空的邻接矩阵,然后在邻接表上顺序地取每个单链表 中的表结点,如果表结点不为空,则将邻接矩阵中对应单元的值置为1 void list to mat(AdjList bl, int n, int a[D) i for(i=0; i<n; i++)for (=0; j<n;j++)a00=0 for(i=0; i<n; 1++) (p=b[]. firstaid while(pl=NULL)fa[i, p->adjvex]=1; p=p->nextare 3.①连通图的深度优先搜索算法 本题的算法思路是:先访问并标记出发点v,然后在邻接矩阵中与ⅴ对应的行查找ⅴ的 邻接点,找到后,再以该邻接点为新的出发点,进行深度优先搜索遍历。 void dfs(int a[o, int v, int n) /*n为图的结点个数, visited数组初值为0*/ i printf("%d", v); visited(v]=l /*访问项点ⅴ* while(w<=n)&&(alvw]=0)w=w+1;/找顶点v的第一个邻接点* while(w<=n) f if(visited w)dfs(a, w, n); w++, 找顶点v处于w之后的下一个邻接点* ②连通图的广度优先搜索算法 本题借助一个队列Q来存放己访问过的顶点。基本算法思路是,首先输出出发点,并 标记已访问过,让其进入队列。接下来只要队列非空,则出队列,然后在与顶点对应的行上 查找其邻接点。如果该邻接点未被访问过,则输出该顶点并让它进入队列。重复上述步骤直 到队列为空队列为止。 void bfs(int a[o, int v, int n) /*n为图结点个数, visited数组初值为0*/ f Init Queue(Q) /*置队列Q为空队列* printf("%d, v); visited(v]=l /访问顶点* EnQueue(Q, v) /*v入队列*/ i V=OutQueue(Q) /*出队 while(w<=n) 体找顶点v的邻接点*
3 找到后在邻表的对应单链表中插入相应的边的表结点。 void mattolist ( int a[][], AdjList b[], int n) /*n 为图的结点个数*/ { for (i=0; i<n; i++) b[i].firstarc=NULL; /*邻接表置空*/ for (i=0; i<n; i++) /*逐行进行*/ for (j=n-1; j>=0; j--) if (a[i][j]!=0) { p=(ArcNodeTp*) molloe (sizeof (ArcNodeTp)); /*产生邻接点*/ p->adjvex=j; /*插入到表头*/ p->nextare=b[i].firstare; b[i].firstarc=p; } } 2．本题的算法思路是：先建一个空的邻接矩阵，然后在邻接表上顺序地取每个单链表 中的表结点，如果表结点不为空，则将邻接矩阵中对应单元的值置为 1。 void list_to_mat (AdjList b[], int n, int a[][]) { for (i=0; i<n; i++) for (j=0; j<n; j++) a[i][j]=0; for (i=0; i<n; i++) { p=b[i].firstarc; while (p!=NULL) {a[i, p->adjvex]=1; p=p->nextare;} } } 3．①连通图的深度优先搜索算法 本题的算法思路是：先访问并标记出发点 v，然后在邻接矩阵中与 v 对应的行查找 v 的 邻接点，找到后，再以该邻接点为新的出发点，进行深度优先搜索遍历。 void dfs (int a[][], int v, int n) /*n 为图的结点个数，visited 数组初值为 0*/ { printf (“%d”, v); visited[v]=1 /*访问项点 v*/ w=1; while ((w<=n)&&(a[v][w]==0)) w=w+1; /*找顶点 v 的第一个邻接点*/ while (w<=n) { if (!visited[w]) dfs(a, w, n); w++; } /*找顶点 v 处于 w 之后的下一个邻接点*/ } ②连通图的广度优先搜索算法 本题借助一个队列 Q 来存放已访问过的顶点。基本算法思路是，首先输出出发点，并 标记已访问过，让其进入队列。接下来只要队列非空，则出队列，然后在与顶点对应的行上 查找其邻接点。如果该邻接点未被访问过，则输出该顶点并让它进入队列。重复上述步骤直 到队列为空队列为止。 void bfs (int a[][], int v, int n) /*n 为图结点个数，visited 数组初值为 0*/ { InitQueue(Q); /*置队列 Q 为空队列*/ printf(“%d”, v); visited[v]=1; /*访问顶点*/ EnQueue (Q, v); /*v 入队列*/ while (!EmptyQueue (Q)) { v=OutQueue (Q); /*出队*/ w=1; while (w<=n) /*找顶点 v 的邻接点*/
if visited[w]) i printf(%d, w); visited[w]=1 /*访问顶点w* EnQueue(Q, w); /*入队* /*w后退 /*end if/ /*end while*/ 4.在有向图中,若邻接表中顶点Ⅵ有邻接点V,在逆邻接表中顶点一定有邻接点 ⅵi,由此得岀本题的算法思路是:首先,将逆邻接表表头结点的 firestar域置空,然后逐行 将表头结点的邻接点进行转化 Void list( AdjList bl[, AdjList b20, int n 体*n为图的结点个数* i for (i=0; i<n; i++)b2[0]. firstarc=NULL /*逐行进行转换* (1=0,1<n;,i++) /*指向第一个邻接点* while(pll=NULL /*j为邻接点* p2=( ArcNodeTp*) mollo( sizeof( ArcNodeTp),/产生逆邻接点* p2->adjvex= p2->nextarc=b2[]-firstarc 体*插入到表头 b2[j] pl=pl->nextarc *指向下一个邻接点* 5.(1)在邻接矩阵上,一行对应于一个顶点,而且每行的非零元素的个数等于对应顶 点的出度。因此,当某行非零元素的个数为零时,则对应顶点的出度为零。据此,从第一行 开始,查找每行是否有非零元素,如果没有则计数器加1。 Void sum zerol(inta[Dntn, Int count)/*n为结点个数, count计度数为0的结点数*/ tag为标志 for(=0; j<n; j++)if(a[noP=1)tag=1 /*有边* if (tag==0)count++ /*出度为0*/ (2)邻接表结构中的边表恰好就是出边表。因此,其表头数组中 firstarc域为空的个数等 于出度为零的元素个数。 Void sum zero2( Adj List al, int count)/* count的初值为0,a为有向图的邻接表* if(al] firstarc==NULL)count++; 6.在邻接表的表头中增加一个入度域in,数据结构修改如下 typedef struct vexnode i VertexType vertex
4 { if (!visited[w]) { printf (“%d”, w); visited[w]=1; /*访问顶点 w*/ EnQueue (Q, w); /*入队*/ } w++; /*w 后退*/ } /*end if*/ } /*end while*/ } 4．在有向图中，若邻接表中顶点 Vi 有邻接点 Vj，在逆邻接表中顶点 Vj 一定有邻接点 Vi，由此得出本题的算法思路是：首先，将逆邻接表表头结点的 firstarc 域置空，然后逐行 将表头结点的邻接点进行转化。 Void list (AdjList b1[], AdjList b2[], int n) /*n 为图的结点个数*/ { for (i=0; i<n; i++) b2[i].firstarc=NULL; /*逐行进行转换*/ for (i=0; i<n; i++) /*指向第一个邻接点*/ { p1=b1[i].firstarc; while (p1!=NULL) { j=p1->adjvex; /*j 为邻接点*/ p2=(ArcNodeTp *) molloe (sizeof (ArcNodeTp)); /*产生逆邻接点*/ p2->adjvex=i; p2->nextarc=b2[j].firstarc; /*插入到表头*/ b2[j].firstarc=p2; p1=p1->nextarc; /*指向下一个邻接点*/ } } } 5．（1）在邻接矩阵上，一行对应于一个顶点，而且每行的非零元素的个数等于对应顶 点的出度。因此，当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行 开始，查找每行是否有非零元素，如果没有则计数器加 1。 Void sum_zero1 (int a[][],int n, int count) /*n 为结点个数，count计度数为0的结点数 */ { for (I=0;I<n;I++) { tag=0; /*tag 为标志*/ for (j=0; j<n; j++) if (a[I][j]>=1) tag=1; /*有边*/ if (tag==0) count++; /*I 出度为 0*/ } } (2)邻接表结构中的边表恰好就是出边表。因此，其表头数组中 firstarc 域为空的个数等 于出度为零的元素个数。 Void sum_zero2 (AdjList a[], int count) /* count 的初值为 0，a 为有向图的邻接表*/ { for (I=0; I<n; I++) if (a[I].firstarc==NULL) count++; } 6．在邻接表的表头中增加一个入度域 in，数据结构修改如下： typedef struct vexnode { VertexType vertex;
/*增加一个入度域* g GraphTp 拓扑排序算法如下: Top Sort(GraphTp g) f StackuP "S 建立入度为0的顶点栈S*/ cNodeTp*p InitStack(S) if(g adjlist].in==0) /*if(w的入度=0)*/ /*w入S栈* m=0 while(! Empty Stack(S)) i Pop(s, &v) /*S出栈>v* /*输出v p=g adjlist[I].firstarc /*p=图g中顶点v的第一个邻接点* while (pl=nUll /p存在 i(g adjlist[p->adjvex in)-- /*p的入度- if(g adjlist[p->adjvex) in==0) /*if(p的入度==0)*/ (s,p- 入S栈* /p=图g中顶点v的下一个邻接点 if /*图含有环 else return l *拓扑排序完成*
5 int in; /*增加一个入度域*/ ArcNodeTp *firstarc; } AdjList[vnum]; typedef struct graph { AdjList adjlist; int vexnum, arcnum; } GraphTp; 拓扑排序算法如下： Top_Sort (GraphTp g) { LstackTp *S; /*建立入度为 0 的顶点栈 S*/ ArcNodeTp *p; int m, I, v; InitStack (S); for (I=0; I<g.vexnum; I++) if (g.adjlist[I].in==0) /*if (w 的入度==0)*/ push(S,&v) /*w 入 S 栈*/ m=0; while (!EmptyStack(S)) { Pop(S,&v); /*S 出栈->v*/ printf(“%d”,v); /*输出 v*/ m++; p=g.adjlist[I].firstarc; /*p=图 g 中顶点 v 的第一个邻接点*/ while (p!=NULL) /*p 存在*/ { (g.adjlist[p->adjvex].in)--; /*p 的入度--*/ if (g.adjlist[p->adjvex].in==0) /*if (p 的入度==0)*/ Push (S, p->adjvex); /*p 入 S 栈*/ p=p->nextarc; /*p=图 g 中顶点 v 的下一个邻接点*/ } } if (m<g.vexnum) return 0; /*图含有环*/ else return 1; /*拓扑排序完成*/ }