第七章 参考答案
四、简答及应用
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.⑴有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 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])
{ 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;
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; /*拓扑排序完成*/
}
四、简答及应用
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.⑴有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 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])
{ 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;
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; /*拓扑排序完成*/
}
