中南大学数据结构与算法第7章图课后作业答案分解

7章图(基础知识)习题练习答案

7.1 在图7.23所示的各无向图中：

(1)找出所有的简单环。

(2)哪些图是连通图?对非连通图给出其连通分量。

(3)哪些图是自由树(或森林)?

答:

(1)所有的简单环：(同一个环可以任一顶点作为起点)

(a)1231

(b)无

(c)1231、2342、12341

(d)无

第

(2)连通图：

(a)、(c)、(d)是连通图，

(b)不是连通图，因为从1到2没有路径。具体连通分量为：

(3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为自由树：

(a)不是自由树，因为有回路。

(b)是自由森林，其两个连通分量为两棵自由树。

(c)不是自由树。

(d)是自由树。

7.2 在图7.24(下图)所示的有向图中：

(1) 该图是强连通的吗? 若不是，则给出其强连通分量。

(2) 请给出所有的简单路径及有向环。

(3) 请给出每个顶点的度，入度和出度。

(4) 请给出其邻接表、邻接矩阵及逆邻接表。

答：

(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。

(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：

有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：

v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)

(3)每个顶点的度、入度和出度：

D(v1)=3 ID(v1)=1 OD(v1)=2

D(v2)=2 ID(v2)=1 OD(v2)=1

D(v3)=3 ID(v3)=2 OD(v3)=1

D(v4)=2 ID(v4)=1 OD(v4)=1

(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1)

vertex firstedge next

┌─┬─┐ ┌─┬─┐ ┌─┬─┐

0│v1│ ─→│ 1│ ─→│ 3│∧│

├─┼─┤ ├─┼─┤ └─┴─┘

1│v2│ ─→│ 2│∧│

├─┼─┤ ├─┼─┤

2│v3│ ─→│ 0│∧│

├─┼─┤ ├─┼─┤

3│v4│ ─→│ 2│∧│

└─┴─┘ └─┴─┘

逆邻接表：

┌─┬─┐ ┌─┬─┐

0│v1│ ─→│ 2│∧│

├─┼─┤ ├─┼─┤

1│v2│ ─→│ 0│∧│

├─┼─┤ ├─┼─┤ ┌─┬─┐

2│v3│ ─→│ 1│ ─→│ 3│∧│

├─┼─┤ ├─┼─┤ └─┴─┘

3│v4│ ─→│ 0│∧│

└─┴─┘ └─┴─┘

邻接矩阵：

0 1 0 1

0 0 1 0

1 0 0 0

0 0 1 0

7.3 假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。

┌ ┓

┌ ┓ | 0 1 1 0 0 |

| 0 1 1 1 | | 0 0 0 1 0 |

| 1 0 1 1 | | 0 0 0 1 0 |

| 1 1 0 1 | | 1 0 0 0 1 |

| 1 1 1 0 | | 0 1 0 1 0 |

┕ ┙ ┕ ┙

(a) (b)

答:

7.4 假设一棵完全二叉树包括A,B,C...等七个结点，写出其邻接表和邻接矩阵。

解：

邻接表如下：

┌─┬─┐ ┌─┬─┐ ┌─┬─┐

0│A │ ─→│ 1│ ─→│ 2│∧│

├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐

1│B │ ─→│ 0│ ─→│ 3│ ─→│ 4│∧│

├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤

2│C │ ─→│ 0│ ─→│ 5│ ─→│ 6│∧│

├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘

3│D │ ─→│ 1│∧│

├─┼─┤ ├─┼─┤

4│E │ ─→│ 1│∧│

├─┼─┤ ├─┼─┤

5│F │ ─→│ 2│∧│

├─┼─┤ ├─┼─┤

6│G │ ─→│ 2│∧│

└─┴─┘ └─┴─┘

邻接矩阵如下：

0 1 1 0 0 0 0

1 0 0 1 1 0 0

1 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

0 0 1 0 0 0 0

0 0 1 0 0 0 0

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)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。

对于有向图，则表示有出边相连。

(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。

对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)

7.6 n个顶点的连通图至少有几条边?强连通图呢?

答：

n个顶点的连通图至少有n-1条边，强连通图至少有2(n-1)条边。

7.7 DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?

答：

DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。

7.8 画出以顶点v1为初始源点遍历图7.25（下图）所示的有向图所得到的DFS 和BFS生成森林。

答：

7.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生成树。

答：

相应的邻接表如下：

┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐

1│1 │ ─→│ 5│ ─→│ 3│ ─→│ 4│ ─→│ 6│ ─→│ 2│∧│

├─┼─┤ ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘ └─┴─┘

2│2 │ ─→│ 6│ ├─┼─┤ ├─┼─┤3│3 │ ─→│ 5│ ├─┼─┤ ├─┼─┤4│4 │ ─→│ 5│ ├─┼─┤ ├─┼─┤5│5 │ ─→│ 3│ ├─┼─┤ ├─┼─┤6│6 │ ─→│ 5│ └─┴─┘ └─┴─┘─→│ 1│∧│

├─┼─┤ ┌─┬─┐

─→│ 4│ ─→│ 1│∧│

├─┼─┤ ├─┼─┤ ┌─┬─┐

─→│ 3│ ─→│6 │ ─→│ 1│∧│

├─┼─┤ ├─┼─┤ ├─┼─┤

─→│ 1│ ─→│ 4│ ─→│ 6│∧│

├─┼─┤ ├─┼─┤ ├─┼─┤

─→│ 4│ ─→│ 2│ ─→│ 1│∧│

└─┴─┘ └─┴─┘ └─┴─┘

根据上面的邻接表画出的图见下图:

从顶点4开始搜索所得的DFS序列是：453162

从顶点4开始搜索所得的BFS序列是：453612

相应的生成树见上图。

7.10 什么样的图其最小生成树是唯一的?用PRIM 和Kruskal求最小生成树的时间各为多少?它们分别适合于哪类图?

答：

当候选轻边集中的轻边数始终等于1条时，其最小生成树是唯一的。用Prim和Kruskal求最小生成树的时间复杂度分别为O(n2)和O(elge),前者适合于稠密图，后者适合于稀疏图.

7.11 对图7.26（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。

答：

7.12 对图7.27(下图)所示的有向图，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行算法过程中扩充红点集的每次循环状态(见表7.2).

答：

循环状态表如下：

循环 红点集 K D[1] D[2] D[3] D[4] D[5] D[6] P[1] P[2] P[3] P[4] P[5] P[6]

初始化 {1} - 0 20 15 ∞ ∞ ∞ -1 1 1 -1 -1 -1

1 {1,3} 3 0 19 15 ∞ ∞ 25 -1 3 1 -1 -1 3

2 {1,3,2} 2 0 19 15 ∞ 29 25 -1 3 1 -1 2 3

3 {1,3,2,6} 6 0 19 15 29 29 25 -1 3 1 6 2 3

4 {1,3,2,6,4} 4 0 19 15 29 29 25 -1 3 5 {1,3,2,6,4,5} 5 0 19 15 29 29 25 -1 3 6 同上 - 同上 同上

从源点1到各点的路径如下所示：

1到2：132

1到3：13

1到4：13

1到5：1325

1到6：136

整个执行算法过程中的扩充红点集的每次循环状态见上表。1 6 2 1 6 2 3

3

7.13 试写出图7.28(下图)所示有向图的所有拓扑序列，并指出就用7.6节给出的NonPreFirstTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增有序的。

答：

上图中所有拓扑序列如下：

v0v1v5v2v3v6v4 *

v0v1v5v2v6v3v4

v0v1v5v6v2v3v4

v1v0v5v6v2v3v4

v1v0v5v2v3v6v4

v1v0v5v2v6v3v4

v1v5v0v2v3v6v4

v1v5v0v2v6v3v4

v1v5v0v6v2v3v4

v5v1v0v2v3v6v4

v5v1v0v2v6v3v4

v5v1v0v6v2v3v4

v5v0v1v2v3v6v4

v5v0v1v2v6v3v4

v5v0v1v6v2v3v4

v0v5v6v1v2v3v4

v1v5v6v0v2v3v4

v5v6v1v0v2v3v4

v5v6v0v1v2v3v4

v5v0v6v1v2v3v4

v5v1v6v0v2v3v4

用NonPreFirstTopSort算法求得的是v0v1v5v2v3v6v4也就是上面带*号的那个。

7.14 什么样的DAG的拓扑序列是唯一的?

答：

确定了排序的源点，DAG图中无前趋顶点只有一个且从该点到终点只有一条路径时，它的拓扑序列才是唯一的。

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； //边上的权值类型应由用户定义

typedef struct{

VextexType vexs[MaxVertexNum] //顶点表

EdeType edges[MaxVertexNum][MaxVertexNum];

//邻接矩阵，可看作边表

int n，e； //图中当前的顶点数和边数

}MGragh；

(1)往图中插入一个顶点

void AddVertexMGraph(MGraph *G,VertexType x)

{//往无向图的邻接矩阵中插入顶点

if (G->n>=MaxVertexNum)

Error(\"顶点数太多\")；

G->vexs[G->n]=x;//将新顶点输入顶点表

G->n++；//顶点数加1

}

(2)往图中插入一条边

void AddedgeMGraph(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->vexs[k]===x) i=k;

if (g->vexs[k]==y) j=k;

}

if (i==-1||j==-1) Error(\"结点不存在\");

else {//插入边(x,y)

g->vex[i][j]=1;

g->vex[j][i]=1;

G->e++;//边数加1

}

}

(3)删去图中某顶点

void DeleteVertexMGraph(MGraph *G,VertexType x)

{//无向图的邻接矩阵中删除顶点x

int i,k,j;

i=-1;

for(k=0;kn;k++)//查找X的编号

if (g->vexs[k]=x) i=k;

if (i==-1) Error(\"结点不存在\");

else {//删除顶点以及边

k=0;//求出与x结点相关联的边数k

for (j=0;jn;j++)

if (g->vexs[i][j]==0) k++;

G->e=G->e-k;//设置新的边数

for (k=i+1;kn;k++)//在邻接矩阵中删除第i行

for(j=0;jn;j++)

g->vexs[k-1][j]=g->vexs[k][j];

for (k=i+1;kn;k++)//在邻接矩阵中删除第i列

for(j=0;jn;j++)

g->vexs[j][k-1]=g->vexs[j][k];

G->n--;//总结点数-1

}

}

(4)删去图中某条边

void 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->vexs[k]=x) i=k;

if (g->vexs[k]=y) j=k;

}

if (i==-1||j==-1) Error(\"结点不存在\");

else if (g->vexs[i][j]!=1)

{//删除边(x,y)

g->vex[i][j]=0;

g->vex[j][i]=0;

G->e--;//边数加1

}

}

(二)用邻接表表示

typedef struct node{//边表结点

int adjvex； //邻接点域

struct node *next； //链域

//若要表示边上的权，则应增加一个数据域

}EdgeNode;

typedef struct vnode{ //顶点表结点

VertexType vertex； //顶点域

EdgeNode *firstedge；//边表头指针

}VertexNode；

typedef VertexNode AdjList[MaxVertexNum]；//AdjList是邻接表类型

typedef struct{

AdjList adjlist；//邻接表

int n，e； 图中当前顶点数和边数

}ALGraph； //对于简单的应用，无须定义此类型，可直接使用AdjList类型。

(1)往图中插入一个顶点

void AddVertexALGraPh(ALGrahp *G,VertexType x)

{//往无向图的邻接表表示中插入一个顶点

if (G->n>=MaxVertexNum)

Error(\"顶点数太多\")；

G->adjlist[G->n].vertex=x;//将新顶点输入顶点表

G->adjlist[G->n].firstedge=NULL;//边表置为空表

G->n++；//顶点数加1

}

(2)往图中插入一条边

void AddedgeALGraPh(ALGrahp *G,VertexType x,VertexType y)

{//往无向图的邻接表中插入边(x,y)

int i,j,k;

EdgeNode *s；

i=-1;j=-1;

for(k=0;kn;k++)//查找X，Y的编号

{ if (G->adjlist[k].vertex==x) i=k;

if (G->adjlist[k].vertex==y) j=k;

}

if (i==-1||j==-1) Error(\"结点不存在\");

else {

s=G->adjlist[i].firstedge;

while ((s)&&(s->adjvex!=j)//查看邻接表中有无(x,y)

s=s->next;

if (!s)//当邻接表中无边(x,y),插入边(x,y)

{

s=(EdgeNode *)malloc(sizeof(EdgeNode))； //生成边表结点

s->adjvex=j; //邻接点序号为j

s->next=G->adjlist[i].firstedge；

部

}

}

}

(3)删去图中某顶点

G->adjlist[i].firstedge=s；//将新结点*s插入顶点x的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode))；

s->adjvex=i; //邻接点序号为i

s->next=G->adjlist[j].firstedge；

G->adjlist[j].firstedge=s； //将新结点*s插入顶点x的边表头G->e++;//边数加1

void DeleteVertexALGraPh(ALGrahp *G,VertexType x)

{//无向图的邻接表中删除顶点x

int i,k,j;

EdgeNode *s,*p,*q；

i=-1;

for(k=0;kn;k++)//查找X的编号

if (G->adjlist[k].vertex==x) i=k;

if (i==-1) Error(\"结点不存在\");

else {//删除与x相关联的边

s=G->adjlist[i].firstedge;

while (s)

{p=G->adjlist[s->adjvex].firstedge;//删除与i相关联的其他结点边表中表结点

if (p)&&(p->adjvex==i)//是第一个边表结点，修改头指针

{G->adjlist[s->adjvex].firstedge=p->next;

free(p);

}

else//不是第一个 边表结点，查找并删除

{while (p)&&(p->next)&&(p->next->adjvex==i)

p=p->next;

q=p->next;

p->next=q->next;free(q);

}

q=s;s=s->next;free(q);//在i结点的边表中删除表结点

G->e--;

}

//调整顶点表

for (j=i;jn-1;j++)

{G->adjlist[j].firstedge=G->adjlist[j+1].firstedge;

G->adjlist[j].vertex=G->adjlist[j+1].vertex;

}

G->n--;

}

}

(4)删去图中某条边

void DeleteedgeALGraPh(ALGraph *G,VertexType x,VertexType y)

{//往无向图的邻接表中删除边(x,y)

int i,j,k;

EdgeNode *s,*p；

i=-1;j=-1;

for(k=0;kn;k++)//查找X，Y的编号

{ if (G->adjlist[k].vertex==x) i=k;

if (G->adjlist[k].vertex==y) j=k;

}

if (i==-1||j==-1) Error(\"结点不存在\");

else {

s=G->adjlist[i].firstedge;//在i的边表中删除值为j的边表结点

if (s)&&(s->adjvex==j)

{G->adjlist[i].firstedge=s->next;

free(s);

}

else{

while (s)&&(s->next)&&(s->next->adjvex!=j)

s=s->next;

if (!s->next) Error(\"无此边\");

else

{p=s->next;s=p->next;free(p);

}

}

s=G->adjlist[j].firstedge;//在j的边表中删除值为i的边表结点

if (s)&&(s->adjvex==i)

{G->adjlist[j].firstedge=s->next;

free(s);

}

else{

while (s)&&(s->next)&&(s->next->adjvex!=j)

s=s->next;

p=s->next;s=p->next;free(p);

}

G->e--;

}

}

7.17 下面的伪代码是一个广度优先搜索算法，试以图7.29（下图）中的v0为源点执行该算法，请回答下述问题：

(1)对图中顶点vn+1，它需入队多少次？它被重复访问多少次?

(2)若要避免重复访问同一个顶点的错误，应如何修改此算法?

void BFS(ALGraph *G,int k)

{//以下省略局部变量的说明，visited各分量初值为假

InitQueue(&Q);//置空队列

EnQueue(&Q,k);//k入队

while(!QueueEmpty(&Q)){

i=DeQueue(&Q);//vi出队

visited[i]=TRUE;//置访问标记

printf(\"%c\访问vi

for(p=G->adjlist[i].firstedge;p;p=p->next)

//依次搜索vi的邻接点vj(不妨设p->adjvex=j)

if(!visited[p->adjvex])//若vj没有访问过

EnQueue(&Q,p->adjvex);//vj入队

}//endofwhile

}//BFS

答：

(1)对图中顶点vn+1，它需入队n次,它被重复访问n次。

(2)若要避免重复访问同一个顶点的错误，应作如下修改：

void BFS(ALGraph *G,int k)

{//以下省略局部变量的说明，visited各分量初值为假

InitQueue(&Q);//置空队列

EnQueue(&Q,k);//k入队

visited[i]=TRUE;//置访问标记

printf(\"%c\访问vi

while(!QueueEmpty(&Q)){

i=DeQueue(&Q);//vi出队

for(p=G->adjlist[i].firstedge;p;p=p->next)

//依次搜索并访问vi的未访问邻接点vj(不妨设p->adjvex=j)

if(!visited[p->adjvex])//若vj没有访问过

{printf(\"%c\访问vj

EnQueue(&Q,p->adjvex);//vj入队

}

}//endofwhile

}//BFS

7.18 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(i<>j)之间是否有路径。

答：

(1)基于采用邻接矩阵的DFS

int pathDFSM(MGraph *G，int i,int j)

{ //以邻接矩阵为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0

int k;

visited[i]=TRUE；

for(k=0；kn；k++) //依次搜索vi的邻接点

if(G->edges[i][k]==1&&!visited[k])

if (k==j) return 1;//有路径相通

else return(pathDFSM(G,k,j);

return 0;//无路径相通

}//DFSM

(2)基于采用邻接表的DFS

int PATHDFS(ALGraph *G，int i,int j){

//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0

EdgeNode *p；

visited[i]=TRUE； //标记vi已访问

p=G->adjlist[i].firstedge； //取vi边表的头指针

while(p){//依次搜索vi的邻接点vk，这里k=p->adjvex

if （!visited[p->adjvex])//若vk尚未被访问

if (p->adjvex==j)

return 1;

else ruturn PATHDFS(g，p->adjvex,j);//则以Vk为出发点向纵深搜索

p=p->next； //找vi的下一邻接点

}

return 0;

}//PATHDFS

(3)基于邻接矩阵的BFS算法

int pathBFSM(MGraph *G，int i,int j)

{//以邻接矩阵为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0

int k；

CirQueue Q；

initQueue(&Q)；

visited[i]=TRUE；

EnQueue(&Q，i)；

while(!QueueEmpty(&Q)){

i=DeQueue(&Q)； //vi出队

for(k=0;kn;k++)//依次搜索vi的邻接点vk

if(G->edges[i][k]==1&&!visited[k]){//vk未访问

if (k==j) return 1;

visited[k]=TRUE；

EnQueue(&Q，k)；//访问过的vk人队

}

}//endwhile

return 0;

}//pathBFSM

(4)基于邻接表为存储结构的BFS算法

int BFS(ALGraph *G，int i,int j)

{//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0

int i；

CirQueue Q； //须将队列定义中DataType改为int

EdgeNode *p；

InitQueue(&Q)；//队列初始化

visited[i]=TRUE；

EnQueue(&Q，i)；//vi已访问，将其人队。（实际上是将其序号人队）

while(!QueueEmpty(&Q)){//队非空则执行

i=DeQueue(&Q)； //相当于vi出队

p=G->adjlist[i].firstedge； //取vi的边表头指针

while(p){//依次搜索vi的邻接点vk(令p->adjvex=k)

if(!visited[p->adjvex]) //若vk未访问过

if (p->adjvex==j)

return 1;

else{

visited[P->adjvex]=TRUE；

EnQueue(&Q，p->adjvex)；

}//访问过的vk人队

p=p->next；//找vi的下一邻接点

}//endwhile

}//endwhile

return 0;

}//end of pathBFS

7.19 试分别写出求DFS和BFS生成树(或生成森林)的算法，要求打印出所有的树边。

答：

(1)求DFS生成树

typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1

Boolean visited[MaxVertexNum]； //访问标志向量是全局量

void DFSTraverseTREE(ALGraph *G)

{ //求深度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，

//算法完全与此相同,只要将DFSTree(G，i)改为DFSMTree(G，i)即可

int i；

for(i=0;in;i++)

visited[i]=FALSE； //标志向量初始化

for(i=0;in；i++)

if(!visited[i]) //vi未访问过

DFSTree(G，i)； //以vi为源点开始DFS搜索,求DFS生成树的边

}//DFSTraverse

void DFSTree(ALGraph *G，int i){

//以vi为出发点对邻接表表示的图G进行深度优先搜索,打印生成树(生成森林)的边

EdgeNode *p；

visited[i]=TRUE； //标记vi已访问

p=G->adjlist[i].firstedge； //取vi边表的头指针

while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex

if (!visited[p->adjvex])//若vj尚未被访问

{printf(\"(%c,%c)\\n\；

// 打印边

DFSTree(g，p->adjvex);//则以Vj为出发点向纵深搜索

}

p=p->next； //找vi的下一邻接点

}

}//DFS

void DFSMTree(MGraph *G，int i)

{ //以vi为出发点对邻接矩阵表示的图G进行深度优先搜索,打印生成树(生成森林)的边

int j；

visited[i]=TRUE；

for(j=0；jn；j++) //依次搜索vi的邻接点

if(G->edges[i][j]==1&&!visited[j])

{

printf(\"(%c,%c)\\n\j]);// 打印边

DFSMTree(G，j);//(vi，vj)∈E，且vj未访问过，故vj为新出发点

}

}//DFSMTree

(2)求BFS生成树

typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1

Boolean visited[MaxVertexNum]； //访问标志向量是全局量

void BFSTraverseTREE(ALGraph *G)

{ //求广度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，

//算法完全与此相同,只要将BFSTree(G，i)改为BFSMTree(G，i)即可

int i；

for(i=0;in;i++)

visited[i]=FALSE； //标志向量初始化

for(i=0;in；i++)

if(!visited[i]) //vi未访问过

BFSTree(G，i)； //以vi为源点开始BFS搜索,求BFS生成树的边

}//BFSTraverse

void BFSTree(ALGraph*G，int k)

{// 以vk为源点对用邻接表表示的图G进行广度优先搜索,并求出BFS生成树边

int i；

CirQueue Q； //须将队列定义中DataType改为int

EdgeNode *p；

InitQueue(&Q)；//队列初始化

visited[k]=TRUE；

EnQueue(&Q，k)；//vk已访问，将其人队。（实际上是将其序号人队）

while(!QueueEmpty(&Q)){//队非空则执行

i=DeQueue(&Q)； //相当于vi出队

p=G->adjlist[i].firstedge； //取vi的边表头指针

while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)

if(!visited[p->adivex]){ //若vj未访问过

printf(\"(%c,%c)\\n\"，

G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex)；

//打印边

visited[P->adjvex]=TRUE；

EnQueue(&Q，p->adjvex)；／／访问过的vj人队

}//endif

p=p->next；//找vi的下一邻接点

}//endwhile

}//endwhile

}//end of BFSTree

void BFSMTree(MGraph *G，int k)

{// 以vk为源点对用邻接矩阵表示的图G进行广度优先搜索,并求出BFS生成树边

int i，j；

CirQueue Q；

InitQueue(&Q)；

visited[k]=TRUE；

EnQueue(&Q，k)；

while(!QueueEmpty(&Q)){

i=DeQueue(&Q)； //vi出队

for(j=0;jn;j++)//依次搜索vi的邻接点vj

if(G->edges[i][j]==1&&!visited[j]){//vi未访问

printf(\"(%c,%c)\\n\"，G->vexs[i],G->vexs[j])；//打印边

visited[j]=TRUE；

EnQueue(&Q，j)；//访问过的vj人队

}

}//endwhile

}//BFSMTree

7.20 写一算法求连通分量的个数并输出各连通分量的顶点集。

答：

typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1

Boolean visited[MaxVertexNum]； //访问标志向量是全局量

void DFSTraverse(ALGraph *G)

{ //深度优先遍历以邻接表表示的图G，求连通分量的个数和各连通分量的顶点集

int i；

for(i=0;in;i++)

visited[i]=FALSE； //标志向量初始化

j=0;//连通分量个数计数器

for(i=0;in；i++)

if(!visited[i]) //vi未访问过

{j++;

printf(\"connected component %d:{\

DFS(G，i)； //以vi为源点开始DFS搜索

printf(\

}

}//DFSTraverse

void DFS(ALGraph *G，int i){

//以vi为出发点对邻接表表示的图G进行深度优先搜索

EdgeNode *p；

printf(\"％c,\"，G->adjlist[i].vertex)；//访问顶点vi

visited[i]=TRUE； //标记vi已访问

p=G->adjlist[i].firstedge； //取vi边表的头指针

while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex

if （!visited[p->adjvex])//若vi尚未被访问

DFS(g，p->adjvex);//则以Vj为出发点向纵深搜索

p=p->next； //找vi的下一邻接点

}

}//DFS

7.21 设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法：

(1)求顶点vi到顶点vj(i<>j)的最短路径

(2)求源点vi到其余各顶点的最短路径

要求输出路径上的所有顶点(提示：利用BFS遍历的思想)

答：

(1)求顶点vi到顶点vj(i<>j)的最短路径

int shortestpath(ALGraph*G，int i,int j)

{// 对邻接表表示的图G，求顶点vi到顶点vj(i<>j)的最短路径

int dist[MaxVertexNum];

CirQueue Q； //须将队列定义中DataType改为int

EdgeNode *p；

int k；

for(k=0;kn;k++)

dist[k]=0； //距离向量初始化

InitQueue(&Q)；//队列初始化

visited[i]=TRUE；

EnQueue(&Q，i)；

while(!QueueEmpty(&Q)){//队非空则执行

i=DeQueue(&Q)； //相当于vi出队

p=G->adjlist[i].firstedge； //取vi的边表头指针

while(p){//依次搜索vi的邻接点vk(令p->adjvex=k)

if(!visited[p->adjvex]){ //若vj未访问过

dist[p->adjvex]++;

if (p->adjvex==j) return dist[p->adjvex];

visited[P->adjvex]=TRUE；

EnQueue(&Q，p->adjvex)；／／访问过的vk人队

}//endif

p=p->next；//找vi的下一邻接点

}//endwhile

}//endwhile

}//end of shortestpath

int BFSM(MGraph *G，int i,int j)

{// 对邻接链表表示的图G，求顶点vi到顶点vj(i<>j)的最短路径

int dist[MaxVertexNum],k；

CirQueue Q；

initQueue(&Q)；

for(k=0;kn;k++)

dist[i]=0； //距离向量初始化

visited[k]=TRUE；

EnQueue(&Q，i)；

while(!QueueEmpty(&Q)){

i=DeQueue(&Q)； //vi出队

for(k=0;kn;k++)//依次搜索vi的邻接点vk

if(G->edges[i][k]==1&&!visited[k]){//vk未访问

dist[k]++;

if (k==j) return dist[j];

visited[k]=TRUE；

EnQueue(&Q，k)；//访问过的vk人队

}

}//endwhile

}//BFSM

(2)求源点vi到其余各顶点的最短路径

void shortestpath(ALGraph*G，int i)

{// 对邻接表表示的图G，求顶点vi到顶点vj(i<>j)的最短路径

int dist[MaxVertexNum];

int pre[MaxVertexNum];//pre[k]中存放vi到vk路径中，vk的前趋的序号

CirQueue Q； //须将队列定义中DataType改为int

EdgeNode *p；

int k,j；

for(k=0;kn;k++)

{dist[k]=0； //距离向量初始化

pre[k]=k;

}

InitQueue(&Q)；//队列初始化

visited[i]=TRUE；

EnQueue(&Q，i)；

while(!QueueEmpty(&Q)){//队非空则执行

i=DeQueue(&Q)； //相当于vi出队

p=G->adjlist[i].firstedge； //取vi的边表头指针

while(p){//依次搜索vi的邻接点vk(令p->adjvex=k)

if(!visited[p->adjvex]){ //若vj未访问过

dist[p->adjvex]++;

pre[p->adjvex]=i;

visited[P->adjvex]=TRUE；

EnQueue(&Q，p->adjvex)；／／访问过的vk人队

}//endif

p=p->next；//找vi的下一邻接点

}//endwhile

}//endwhile

for(k=0;kn;k++)// 打印各顶点的最短路径和长度

{printf(\"path of %c is %d:\

j=k;

printf(\"%c\

do

{

j=pre[j];

print(\"<-%c\j].vertex);

}

while (j!=i);

printf(\"\\n\");

}

}//end of shortestpath

void shortestpathBFSM(MGraph *G，int i)

{// 对邻接矩阵表示的图G，求顶点vi到其他顶点的最短路径

int dist[MaxVertexNum],k,j;

int pre[MaxVertexNum];//pre[k]中存放vi到vk路径中，vk的前趋的序号

CirQueue Q；

initQueue(&Q)；

for(k=0;kn;k++)

{dist[k]=0； //距离向量初始化

pre[k]=k;

}

visited[k]=TRUE；

EnQueue(&Q，i)；

while(!QueueEmpty(&Q)){

i=DeQueue(&Q)； //vi出队

for(k=0;kn;k++)//依次搜索vi的邻接点vk

if(G->edges[i][k]==1&&!visited[k]){//vk未访问

dist[k]++;

pre[k]=i;

visited[k]=TRUE；

EnQueue(&Q，k)；//访问过的vk人队

}

}//endwhile

for(k=0;kn;k++)// 打印各顶点的最短路径和长度

{printf(\"path of %c is %d:\

j=k;

printf(\"%c\

do

{

j=pre[j];

printf(\"<-%c\j]);

}

while (j!=i);

printf(\"\\n\");

}

}//shortestpathBFSM

7.22 以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在)。

答：

int circleDFS(ALGraph *G，int k){

//以vk为出发点对邻接表表示的图G,求简单回路,若存在返回1，否则返回0

EdgeNode *p；

printf(\"％c\"，G->adjlist[k].vertex)；//访问顶点vk

visited[k]=TRUE； //标记vk已访问

p=G->adjlist[k].firstedge； //取vk边表的头指针

while(p){//依次搜索vk的邻接点vj，这里j=p->adjvex

if (!visited[p->adjvex])//若vj尚未被访问

DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索

else if (p->adjvex==k)

{printf(\"%c\；return 1;}

p=p->next； //找vk的下一邻接点

}

return 0;

}//DFS

7.23 写一算法求有向图的所有根(若存在)，分析算法的时间复杂度。

答：

typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1

Boolean visited[MaxVertexNum]； //访问标志向量是全局量

void DFSTraverse(ALGraph *G)

{ //对以邻接表表示的有向图G，求所有根(以邻接矩阵表示G时，算法完全与此相同)

int i,j；

for (j=0;jn;j++)

{

for(i=0;in;i++)

visited[i]=FALSE； //标志向量初始化

DFS(G，j)； //以vj为源点开始DFS搜索，也可用BFS(G,j)

i=0;

while(in)&&(visited[i]==TRUE)

i++;

if (i==G->n) printf(\"root:%c\j].vertex);

}

}//DFSTraverse

该算法的为二重循环，若调用的DFS算法的复杂度为O(n+e),所以该算法的时间复杂度为O(n(n+e))

若调用的DFSM算法的复杂度为O(n*n),所以该算法的时间复杂度为O(n^3)

7.24 改写7.5节的算法Print，使输出的从源点到各终点的最短路径是正向的。(提示：使用栈暂存路径)

答：

void print(path p,distance d)

{//输出最短路径及其长度，从源点到各终点的最短路径是正向的

int i,pre;

SeqStack S; //定义一个栈

InitStack (&s);

for(i=0;iprintf(\"\\n distance:%d,path:\输出终点i的最短距离

Push(&S, i);//终点i入栈

pre=p[i];//找终点i的前趋

while (pre!=-1)

{push(&s,pre);

pre=p[pre];//继续找前趋

}//endwhile

printf(\"%d\

while (!StackEmpty(S))

printf(\

}//endfor

}//endprint

7.25 对7.6节的NonSuccFirstTopSort算法求精，分别以邻接矩阵和邻接表作为存储结构，写出其具体算法，并分析算法的时间。

答：

(1)以邻接矩阵作为存储结构

void NonSuccFirstTopSort(MGraph G){//优先输出无后继的顶点

int outdegree[MaxVertexNum];//出度向量，此处MaxVertexNum>=G.n

SeqStack S,T;//将栈中data向量的基类型改为int

int i,j,count=0;//count对输出的顶点数目计数，初值为0

for(i=0;ioutdegree[i]=0;

for(i=0;ifor(j=0;joutdegree[i]=outdegree[i]+g.edge[i][j];

InitStack(&s);

for(i=0;iif (outdegree[i]==0)

Push(&S, i);//出度为0的顶点i入栈

InitStack(&T);

while(!StackEmpty(S))//栈非空，有出度为0的顶点

{i=pop(&s);

Push(&T, i);

count++;//顶点计数加1

for (j=0;jif (G.edge[j][i]==1)

{G.edge[j][i]=0;

outdegree[j]--;

if (outdegree[j]==0)//将新生成的出度为0的顶点入栈

Push(&S, j);//出度为0的顶点j入栈

}//end of if

}//end of while

if (countprintf(\"G中存在有向环，排序失败!\");

else{//输出拓扑序列

while (!StackEmpty(T))

printf(\"%c\

}

}

(2)以邻接表作为存储结构

void NonSuccFirstTopSort(ALGraph G){

//优先输出无后继的顶点,此处用逆邻接表存储

int outdegree[MaxVertexNum];//出度向量，此处MaxVertexNum>=G.n

SeqStack S,T;//将栈中data向量的基类型改为int

int i,j,count=0;//count对输出的顶点数目计数，初值为0

EdgeNode *p;

for(i=0;ioutdegree[i]=0;

for(i=0;ifor(p=G.adjlist[i].firstedge;p;p=p->next)//扫描i的入边表

outdegree[p->adjvex]++;//设p->adjvex=j，则将的起点j出度加1

InitStack(&s);

for(i=0;iif (outdegree[i]==0)

Push(&S, i);//出度为0的顶点i入栈

InitStack(&T);

while(!StackEmpty(S))//栈非空，有出度为0的顶点

{i=pop(&s);

Push(&T, i);

count++;//顶点计数加1

for(p=G.adjlist[i].firstedge;p;p=p->next)

//修改以i为弧头的弧的弧尾顶点的出度

{

j=p->adjvex;

outdegree[j]--;

if (outdegree[j]==0)//将新生成的出度为0的顶点入栈

Push(&S, j);//出度为0的顶点j入栈

}//end of for

}//end of while

if (countprintf(\"G中存在有向环，排序失败!\");

else{//输出拓扑序列

while (!StackEmpty(T))

printf(\"%c\

}

}

7.26 设一个有向图DAG，试以邻接矩阵和邻接表作为存储结构，写出对7.6节的DFSTopSort求精算法。为什么有向图不是DAG时，该算法不能正常工作?

答：

(1)以邻接矩阵作为存储结构

void DFSTopSort(MGraph G,int i,SeqStack T){

EdgeNode *p;

visited[i]=TRUE;

for(j=0;jif (G.edge[i][j]==1)&&(!visited[j])

FFSTopSort(G,j,T);

push(&T,i);

}

(2)以邻接表作为存储结构

void DFSTopSort(ALGraph G,int i,SeqStack T){

int j;

visited[i]=TRUE;

for(p=G.adjlist[i].firstedge;p;p=p->next)

if (!visited[p->adjvex])//若vj尚未被访问

DFSTopSort(G，p->adjvex,T);

push(&T,i);

}

当有向图不是DAG图时，该算法不能检测出回路，仍然能给出包含所有顶点的序列，所以该算法不能正常工作。

7.27 利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环存在时，输出构成环的顶点。

答：

typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1

Boolean visited[MaxVertexNum]； //访问标志向量是全局量

int i；

for(i=0;in;i++)

visited[i]=FALSE； //标志向量初始化

以邻接表作为存储结构

void NonSuccFirstTopSort(ALGraph G){

//优先输出无后继的顶点,此处用逆邻接表存储

int outdegree[MaxVertexNum];//出度向量，此处MaxVertexNum>=G.n

SeqStack S;//将栈中data向量的基类型改为int

int i,j,count=0;//count对输出的顶点数目计数，初值为0

EdgeNode *p;

for(i=0;i{ outdegree[i]=0;

visited[i]=FALSE； //标志向量初始化

}

for(i=0;ifor(p=G.adjlist[i].firstedge;p;p=p->next)//扫描i的入边表

outdegree[p->adjvex]++;//设p->adjvex=j，则将的起点j出度加1

InitStack(&s);

for(i=0;iif (outdegree[i]==0)

Push(&S, i);//出度为0的顶点i入栈

while(!StackEmpty(S))//栈非空，有出度为0的顶点

{i=pop(&s);visited[i]=TRUE;

count++;//顶点计数加1

for(p=G.adjlist[i].firstedge;p;p=p->next)

//修改以i为弧头的弧的弧尾顶点的出度

{

j=p->adjvex;

outdegree[j]--;

if (outdegree[j]==0)//将新生成的出度为0的顶点入栈

Push(&S, j);//出度为0的顶点j入栈

}//end of for

}//end of while

if (count{printf(\"G中存在有向环，排序失败!\");

for(i=0;iif (visited[i]==FALSE)

printf(\"%c\

}

else printf(\"G中无有向环!\");

}