第七章图 习题答案

/第七章图习题答案基础知识：7。１在图7.2３所示的各无向图中：ﻫ

(１）找出所有的简单环。ﻫ(２）哪些图是连通图？对非连通图给出其连通分量.

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

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

(ａ）12３1

(b）无ﻫ(ｃ）12３1、2342、12341ﻫ（d）无

(2)连通图：ﻫ(ａ）、（ｃ）、（ｄ）是连通图,

（b）不是连通图,因为从１到２没有路径.具体连通分量为:ﻫﻫ（３)自由树(森林):自由树是指没有确定根的树，无回路的连通图称为自由树:ﻫ（a）不是自由树，因为有回路.ﻫ(b）是自由森林,其两个连通分量为两棵自由树。ﻫ（c）不是自由树。

（ｄ)是自由树。7。2在图7．２４(下图）所示的有向图中：ﻫﻫ(1）该图是强连通的吗?若不是,则给出其强连通分量。

（２）请给出所有的简单路径及有向环。ﻫ(3）请给出每个顶点的度,入度和出度.

(4)请给出其邻接表、邻接矩阵及逆邻接表。ﻫ答：（1）该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径.ﻫ（2）简单路径是指在一条路径上只有起点和终点可以相同的路径：ﻫ有v1v２、v2v3、v3v1、ｖ1v４、v4ｖ3、v1ｖ２ｖ3、v2v3ｖ１、v３v1ｖ2、ｖ1v4v３、v4v3v１、v3ｖ1v4、另包括所有有向环,有向环如下:ﻫv1v２ｖ3v1、v１ｖ4v３v1(这两个有向环可以任一顶点作为起点和终点）

（3)每个顶点的度、入度和出度:ﻫD（v1）=３ID(v1)=1ＯD(ｖ1)=2ﻫD（v２）=２ＩD（v２）＝1OD（v2)=１ﻫD(v３）=３ＩD(v3)＝２OD(v3)=1ﻫD（v4)＝2ＩＤ（v4)=1OD(v4)=１

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

vｅrteｘｆirｓtｅｄge

next

┌─┬─┐

┌─┬─┐

┌─┬─┐ﻫ０│v１│─→│1│─→│3│∧│

├─┼─┤

├─┼─┤

└─┴─┘

1│v2│─→│2│∧│

├─┼─┤

├─┼─┤

2│v３│─→│0│∧│ﻫ

├─┼─┤

├─┼─┤

3│v４│─→│2│∧│

└─┴─┘

└─┴─┘ﻫ

逆邻接表：ﻫ

┌─┬─┐

┌─┬─┐ﻫ

0│v1│─→│2│∧│

├─┼─┤

├─┼─┤

1│v２│─→│0│∧│

├─┼─┤

├─┼─┤

┌─┬─┐ﻫ

2│v3│─→│1│─→│３│∧│

├─┼─┤

├─┼─┤

└─┴─┘

3│ｖ4│─→│0│∧│ﻫ

└─┴─┘

└─┴─┘ﻫ

邻接矩阵：

0101

0010

1000ﻫ

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

┌┓ﻫ

┌

┓

|０1１00|ﻫ

|0１１１|

｜０0010｜

ﻫ

｜101１|

｜0００1０｜

ﻫ

｜1101｜

｜１０001｜

|1110|

｜0101０|

┕

┙┕

┙

(ａ）

(ｂ）

答:ﻫ

７。４假设一棵完全二叉树包括Ａ，B，C。。.等七个结点，写出其邻接表和邻接矩阵。ﻫ解:

邻接表如下:

┌─┬─┐

┌─┬─┐

┌─┬─┐

0│A│─→│１│

─→│２│∧│

├─┼─┤

├─┼─┤

├─┼─┤

┌─┬─┐ﻫ

１│B│─→│0│─→│3│─→│４│∧│ﻫ

├─┼─┤

├─┼─┤

├─┼─┤

├─┼─┤

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

├─┼─┤

├─┼─┤

└─┴─┘

└─┴─┘ﻫ

3│D│─→│1│∧│ﻫ

├─┼─┤

├─┼─┤

4│Ｅ│─→│1│∧│ﻫ

├─┼─┤

├─┼─┤ﻫ

5│F│─→│2│∧│ﻫ

├─┼─┤

├─┼─┤

6│G│─→│2│∧│

└─┴─┘

└─┴─┘ﻫ

邻接矩阵如下：

01100００ﻫ

1001１00

1０00011

0100000ﻫ

0１０0０00

ﻫ

0010000ﻫ

001０00０7。5对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时，如何判别下列有关问题?ﻫ

（1）图中有多少条边？

（2)任意两个顶点i和ｊ是否有边相连?

(3）任意一个顶点的度是多少?

答：

对于n个顶点的无向图和有向图，用邻接矩阵表示时:ﻫ

(１）设m为矩阵中非零元素的个数

无向图的边数=m/2

有向图的边数=m

（2)无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。ﻫ（3）对于无向图,任一顶点i的度为第i行中非零元素的个数。ﻫ对于有向图,任一顶点i的入度为第i列中非零元素的个数,出度为第i行中非零元素的个数，度为入度出度之和。ﻫ当用邻接表表示时:ﻫ（1）对于无向图,图中的边数=边表中结点总数的一半。ﻫ对于有向图，图中的边数=边表中结点总数。

(2)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。ﻫ对于有向图,则表示有出边相连。

（3）对于无向图,任意一个顶点的度则由该顶点的边表中结点的个数来决定。ﻫ对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表.（用逆邻接表可容易地得到其入度。)７。6n个顶点的连通图至少有几条边？强连通图呢？

答:n个顶点的连通图至少有n—１条边，强连通图至少有2（ｎ-1）条边.７.7DFS和ＢＦS遍历各采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小,应采用何种遍历？

答：ＤFS遍历采用栈来暂存顶点。BＦＳ采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。7。8画出以顶点ｖ1为初始源点遍历图7。25(下图）所示的有向图所得到的DFS和ＢＦS生成森林。ﻫ

答:

7．9按顺序输入顶点对:(1，2)，（1,6）,(２，６），（1,4），(6,4），（1，3),（3，４),(６，５），（4,5），（1,5），（3,5），根据第７.2。2节中算法ＣreatALGrａph画出相应的邻接表。并写出在该邻接表上，从顶点4开始搜索所得的DＦS和BＦS序列,及ＤFS和ＢFS生成树。

ﻫ答：相应的邻接表如下:

┌─┬─┐

┌─┬─┐

┌─┬─┐

┌─┬─┐

┌─┬─┐

┌─┬─┐

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

├─┼─┤

├─┼─┤

├─┼─┤

└─┴─┘

└─┴─┘

└─┴─┘ﻫ

2│2│─→│6│─→│１│∧│

├─┼─┤

├─┼─┤

├─┼─┤

┌─┬─┐

3│３│─→│５│─→│4│─→│1│∧│ﻫ

├─┼─┤

├─┼─┤

├─┼─┤

├─┼─┤

┌─┬─┐

４│4│─→│5│─→│3│─→│6│─→│1│∧│ﻫ

├─┼─┤

├─┼─┤

├─┼─┤

├─┼─┤

├─┼─┤ﻫ

5│5│─→│3│─→│1│─→│4│─→│６│∧│

├─┼─┤

├─┼─┤

├─┼─┤

├─┼─┤

├─┼─┤

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

└─┴─┘

└─┴─┘

└─┴─┘

└─┴─┘

└─┴─┘

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

ﻫ

ﻫﻫ

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

从顶点4开始搜索所得的BFS序列是:45３612ﻫ

相应的生成树见上图。７．１０什么样的图其最小生成树是唯一的?用ＰRIM和Kｒusｋal求最小生成树的时间各为多少？它们分别适合于哪类图？

答：当候选轻边集中的轻边数始终等于１条时,其最小生成树是唯一的。用Prim和Kｒusｋal求最小生成树的时间复杂度分别为O（n2)和Ｏ(elge），前者适合于稠密图，后者适合于稀疏图.7．１１对图7。26（下图）所示的连通图,请分别用Ｐrim和Kｒuskal算法构造其最小生成树。

ﻫﻫ答：

７。12对图7。27(下图)所示的有向图，试利用Ｄijksｔra算法求出从源点1到其它各顶点的最短路径,并写出执行算法过程中扩充红点集的每次循环状态(见表７.2)．

答：循环状态表如下:ﻫ循环

红点集

KD［1]Ｄ[2］D[3]D［４］Ｄ［5］Ｄ[6］P［1］P［2］P［３]Ｐ［4]Ｐ［5]P[6]

初始化

{１}

-

0

２0

１５

∞

∞

∞

—１

1

1

-1

－1

—1

ﻫ

1

｛１,３｝

3

0

19

1５

∞

∞

２5

-1

３

1

－1

—１

3

２

{1，3,2｝

2

0

19

１５

∞

29

2５

-１

3

1

－1

２

3

ﻫ

3

{1，３,２,６｝

6

0

１9

15

29

29

25

—1

３

1

6

２

3

4

｛１,3，２，6,4｝

4

0

１9

１5

２9

2９

2５

－１

３

1

6

2

3

５｛1，３，２,6，4，5｝

5

０

19

15

２9

2９

25

-1

３

1

6

2

３

６

同上

—

同上

同上

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

1到2:132

１到3:１３

1到4:1364

1到5：１3２5

1到６：１３6ﻫ整个执行算法过程中的扩充红点集的每次循环状态见上表.７。13试写出图７．28(下图）所示有向图的所有拓扑序列，并指出就用7.６节给出的NonPreFiｒstTopSｏrt算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增有序的。

ﻫ

ﻫ答：

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

v0ｖ１ｖ5v２ｖ３v６v4＊

v０v1v5v2ｖ6v3ｖ4

ｖ0v1ｖ5v６ｖ2ｖ3v4

v１ｖ0v5v６ｖ2v3v４

v１ｖ０ｖ5ｖ２v3ｖ６ｖ４

v1v0v5v2ｖ6ｖ3v4

v1v5v0v2v3v6v４

v1v５v0v２ｖ6v3ｖ4

v１v5v0v6v２v3v４ﻫ

v5v1v0ｖ2v3ｖ6v4

v5ｖ1ｖ０v2ｖ6v3v4

v5v１ｖ０v6v２v3v４

v5ｖ0v1v２v3ｖ6v4

ｖ5v０v1ｖ2v6ｖ3ｖ4

v5v0v１ｖ6ｖ2v3v4

ｖ0v５ｖ6v1v２ｖ3v4

v1v５v6v0ｖ2ｖ3v４

v５ｖ6v１v0ｖ２v3v4ﻫ

v5v6v０v1v2v3v４

v5v0v6v1v2v3v4

v5v1v6ｖ０v２v3ｖ4

用NonＰreFirstTopSoｒt算法求得的是v0v1v5v2v3v６ｖ４也就是上面带*号的那个。7.１4什么样的DAG的拓扑序列是唯一的？

ﻫ答:

确定了排序的源点，DAG图中无前趋顶点只有一个且从该点到终点只有一条路径时，它的拓扑序列才是唯一的。7.15请以V0为源点，给出用DＦＳ搜索图７.28(下图）得到的逆拓扑序列.

答:

逆拓扑序列是：V４V2V１V0V1V6V5算法设计：7.16试在无向图的邻接矩阵和邻接链表上实现如下算法:

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

（2）往图中插入一条边

(3)删去图中某顶点ﻫ(4）删去图中某条边

解：（一）用邻接矩阵表示ﻫ#defineＭaxVｅrtｅxNuml0０//最大顶点数，应由用户定义

typedｅfｃharＶｅｒｔeｘType；／/顶点类型应由用户定义ﻫtypedefｉntEdgeType;/／边上的权值类型应由用户定义ﻫｔypeｄefsｔｒuｃｔ{ﻫVexｔeｘTypeｖeｘs[MａｘVｅrtexNｕm]//顶点表

EdeTypeｅｄges［MaｘVerteｘＮuｍ］［MaxVertexNｕｍ］;ﻫ／/邻接矩阵,可看作边表

ｉntn，ｅ；//图中当前的顶点数和边数ﻫ｝ＭGraｇh；

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

voｉdAdｄVertexＭGｒaph(MGｒaph＊G，ＶerteｘTypｅx)

{//往无向图的邻接矩阵中插入顶点ﻫiｆ(G－＞n〉=MａｘVerteｘNuｍ）

Erｒor（”顶点数太多"）；ﻫG－〉vexs[G－〉n］＝x；//将新顶点输入顶点表ﻫＧ—〉ｎ++；/／顶点数加１ﻫ｝ﻫ（2)往图中插入一条边

vｏidAddedgｅMGraｐｈ（MGraph＊G,VeｒｔeｘＴypｅx，ＶerｔexTypey）

{//往无向图的邻接矩阵中插入边（x，ｙ)ﻫintｉ,j，k;ﻫｉ=—1;j=—１；ﻫｆｏr(k＝0;k＜G-〉n;k++)//查找X，Y的编号

｛if（ｇ—〉veｘs［k］=＝=ｘ）i＝k；

ｉf(g-＞vexs［k]=＝y）ｊ=k;ﻫ｝ﻫif(i＝＝—1|｜ｊ==—1）Error（＂结点不存在＂）；

elｓｅ{//插入边（ｘ，y)

ｇ—>vｅx［i]［j］=1；ﻫg-〉vｅｘ［j]［i］=1；ﻫＧ—＞e++;//边数加1ﻫ｝

｝

（3）删去图中某顶点ﻫvoiｄDelｅｔeVertexMＧrａph（ＭGrａph*Ｇ，VerｔｅｘＴypeｘ）

｛/／无向图的邻接矩阵中删除顶点ｘﻫintｉ，k，j；ﻫi=—１；ﻫfｏr（k＝0；k<G-＞n；k＋＋）/／查找X的编号ﻫif(ｇ—〉vexs[k］＝x)i＝k；ﻫif（ｉ＝=-1)Erroｒ(”结点不存在”）;ﻫelsｅ{/／删除顶点以及边

k＝０；//求出与x结点相关联的边数kﻫfoｒ(j=0;j〈G—>n；ｊ＋+）ﻫif（ｇ-〉vexｓ[ｉ]［j]==0)k+＋；

G－>ｅ＝Ｇ－＞e－ｋ；／/设置新的边数ﻫfor（k＝i+1;k＜G—〉n；ｋ＋+）//在邻接矩阵中删除第ｉ行ﻫfｏr(ｊ=0;j〈G—>n；ｊ++）ﻫg－>ｖｅxｓ[k-１］[j]=g—>ｖｅxｓ［ｋ］[j]；

fｏr（k=i＋1;k<G-＞n;k+＋）//在邻接矩阵中删除第ｉ列ﻫfoｒ(j=０;ｊ＜G—〉n;ｊ++）

ｇ—〉veｘｓ［j］［ｋ-1］=ｇ－>ｖexｓ［j］[k］;

G->n-—；//总结点数-1

｝

｝

ﻫ(４）删去图中某条边

vｏidDeｌｅteedgeMＧraph(MGrapｈ＊G，VertｅｘＴｙpeｘ，ＶerｔｅｘＴypｅy）

{//无向图的邻接矩阵中删除边(x,y）

intｉ,j,k;

ｉ=-1;ｊ=—1；ﻫfoｒ(ｋ=0；k〈Ｇ-＞n;k+＋)//查找X，Y的编号

｛if(g—〉vexs［ｋ]＝x）ｉ=k;ﻫiｆ（g->veｘs［ｋ]=y）j=k；ﻫ}ﻫiｆ（i＝=—１｜|j==－１）Ｅrror（＂结点不存在”);ﻫｅlｓeｉｆ（g->vexs[i］［j］！=1）

｛//删除边（x，y)ﻫg—〉vex[i］[ｊ］=０;

g->vex[j］［i]=0；ﻫG-＞ｅ—－；//边数加1

｝ﻫ}ﻫ（二）用邻接表表示

ﻫtｙｐedｅｆstruｃtｎｏde｛//边表结点ﻫintａdjｖｅｘ;//邻接点域

ｓtｒuｃtnoｄe*nexｔ；//链域ﻫ//若要表示边上的权,则应增加一个数据域ﻫ｝EｄgeＮode;

tｙpedefｓｔｒuctvnoｄe{／/顶点表结点

VertexTypeveｒtex；//顶点域ﻫEｄgeNode*firstedgｅ;//边表头指针ﻫ}ＶertexNｏde；ﻫtypedefVertexNoｄｅAdjList［MaｘVertexＮｕm]；／/AdjList是邻接表类型ﻫtypedｅfsｔｒucｔ{ﻫAdjＬistadjlist；//邻接表ﻫintn，e；图中当前顶点数和边数

ﻫ｝ALGｒapｈ;//对于简单的应用，无须定义此类型,可直接使用ＡdjLiｓt类型。

（1）往图中插入一个顶点ﻫvoidＡddVertexALGraPh(ＡＬGｒaｈp＊G，ＶertｅxTyｐex）

｛/／往无向图的邻接表表示中插入一个顶点ﻫif(Ｇ—>n>=MａxVertｅxNum）

Error（"顶点数太多”);

Ｇ-＞aｄｊliｓt［G->n].verｔex=x；/／将新顶点输入顶点表ﻫＧ－〉adｊlｉsｔ[G—＞n］.firsｔedge=NULL；／/边表置为空表ﻫG－＞n++；//顶点数加1

｝ﻫ(2）往图中插入一条边

vｏｉdＡdｄｅｄgｅAＬGraPh（ALGrahp＊G,VeｒtexＴｙpｅx,ＶerｔexTypey)

｛//往无向图的邻接表中插入边(x,y）ﻫｉnti，j，k；ﻫEｄgeＮodｅ*s；ﻫi=—１；ｊ＝-1;

foｒ(ｋ=0；k<G—＞ｎ;k+＋）//查找X，Y的编号

｛ｉf（Ｇ-〉adｊlｉst[k］．verｔex＝=ｘ）i=ｋ；ﻫｉf(G—＞aｄjliｓt[k］．verｔex＝=y）ｊ＝k;ﻫ｝

if（ｉ==-1|｜ｊ=＝—1)Ｅrroｒ（"结点不存在＂)；

else｛

s＝G－〉aｄｊlｉst［i］。ｆirｓteｄgｅ；

ｗhilｅ（（s)&＆（s—>adjvex!=j)//查看邻接表中有无（x，y)ﻫs＝ｓ->next；

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

{

s=（EｄgeＮｏde*）malloc(sｉzeｏf(ＥｄgeNode））;//生成边表结点ﻫs-〉ａdｊvex＝j；//邻接点序号为jﻫs－>nｅxt=Ｇ->adjliｓt［i］。firｓtｅdｇe；ﻫG->adjlist[i]．firsｔｅｄge=ｓ；//将新结点＊s插入顶点x的边表头部

s=(ＥｄgeＮode＊）maｌｌoｃ(sizeof（EｄgeNode))；ﻫs－>aｄｊvｅx=i；//邻接点序号为i

s-＞next=G-〉adjliｓt[j］．firstｅｄge；ﻫG—〉adjliｓt［j］。fｉrstedge=ｓ；//将新结点*ｓ插入顶点ｘ的边表头部

Ｇ->e＋+；／/边数加1ﻫ｝

}ﻫ｝

ﻫ（3）删去图中某顶点

voidDelｅteVeｒtexALＧraPｈ(ＡＬGrahp＊G，VerｔｅxTｙpex)

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

ｉnti，k,j;ﻫＥdgｅNode＊s，＊p，＊q;

ｉ=—1；ﻫfor（k=０；k＜Ｇ-〉ｎ;k+＋)／/查找Ｘ的编号ﻫif（G－>ａdjlist[ｋ］．vｅrtex==x)i=k；ﻫｉf（i＝＝-1)Error（”结点不存在＂)；ﻫeｌｓｅ｛/／删除与x相关联的边ﻫs=Ｇ－〉aｄｊｌiｓｔ[i］.fiｒstedge;ﻫwhiｌe（ｓ）ﻫ{p=G－〉aｄｊlisｔ[s－〉ａdｊvｅx］.firｓtedge；//删除与ｉ相关联的其他结点边表中表结点

if(p）＆＆（ｐ-〉adjvｅx==i）/／是第一个边表结点,修改头指针ﻫ{G—＞ａdｊlist[s->aｄjvex]。firsｔedge＝p-〉nｅｘｔ；

frｅe（ｐ);

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

{while(p）&＆（p—>ｎexｔ)＆&(p—〉next—＞aｄjｖｅx＝＝i)ﻫp=p-＞nexｔ;ﻫq＝p－〉nexｔ；ﻫｐ->ｎeｘt=q－>ｎｅxt;free（ｑ）；ﻫ｝

ｑ=s;s＝ｓ—＞next；freｅ（q）；//在i结点的边表中删除表结点

G—>e-—；

｝

/／调整顶点表

ｆor(j＝ｉ；j<G-＞ｎ—1；ｊ++)

｛G—＞ａdjlist[j].firstedｇe＝G—>adjlisｔ［j+１］.fiｒｓteｄge;ﻫG－＞aｄjlist［j］．vertｅx=Ｇ－〉ａdｊlｉst［ｊ＋１]。vｅrtｅｘ；

｝ﻫG—>ｎ—-；

}

}

（４）删去图中某条边ﻫvoiｄDeleteedgeAＬGｒａPh(ＡLＧrapｈ*G，ＶeｒｔexTypex,VertexＴyｐｅy)

｛//往无向图的邻接表中删除边(x，ｙ)ﻫintｉ，j，ｋ;

EdｇeNode*s,＊p；

ｉ=－1;j=－1;ﻫfor(ｋ=0;k<Ｇ-〉ｎ；k++）／/查找X，Y的编号

{iｆ(G－〉aｄｊlist［ｋ].ｖertex==x）ｉ＝ｋ；

if(G—>aｄjlisｔ［k］。veｒtex==ｙ）j=k；

}

iｆ（i=＝-１｜|j＝＝－１）Eｒror("结点不存在"）；

else｛ﻫs＝G－＞aｄjliｓt［ｉ］.firsｔeｄge;／／在i的边表中删除值为j的边表结点

iｆ(ｓ)＆＆(s—〉adjveｘ＝=j）

｛G－〉adｊlist[i]。firstedge＝s—>next；ﻫfrｅｅ(ｓ）;ﻫ｝

elｓe{

whiｌｅ(s）&＆(s—〉next)＆＆（s-＞ｎexｔ—〉adjveｘ!＝j）

s=s-〉neｘt;

ｉf（!s-〉nｅxｔ）Eｒror("无此边＂）;ﻫelsｅ

ﻫ｛p=s－＞next；s＝ｐ->next;free（ｐ）;ﻫ｝

｝ﻫs=G->ａdjliｓt［j］.ｆｉrstedｇe;//在j的边表中删除值为i的边表结点

if（ｓ）＆&(s－〉adjvex=＝i）

ﻫ{G—〉adｊlisｔ［j].ｆｉｒsteｄｇｅ=ｓ—〉ｎext；

frｅｅ（ｓ）；

}

ﻫelｓe{

whｉle(s）&＆（s-＞nｅxt)＆＆（s-〉nexｔ—〉ａｄjveｘ！=j）

s=s—>nｅxt；ﻫｐ=s-＞next;s=ｐ->nexｔ;fｒeｅ（p);ﻫ｝ﻫG—>ｅ——;

｝ﻫ｝

７。1７下面的伪代码是一个广度优先搜索算法，试以图7。２9（下图)中的v0为源点执行该算法，请回答下述问题：ﻫﻫ（１）对图中顶点vn＋１,它需入队多少次?它被重复访问多少次?ﻫ（2）若要避免重复访问同一个顶点的错误，应如何修改此算法？

vｏiｄBFS（ＡＬＧraｐh*G，ｉntk)

｛/／以下省略局部变量的说明，viｓitｅｄ各分量初值为假

IniｔQuｅue（&Q）；//置空队列

ＥnQuｅuｅ（＆Q,k)；/／k入队ﻫwhile(！ＱｕｅueEmｐty(＆Q）)｛ﻫi=DeQｕeue(＆Q）;//vi出队ﻫvisiｔed［i］＝TRUE;／/置访问标记

priｎtf（＂%c＂，Ｇ—>aｄｊlｉsｔ［i］.ｖeｒｔex;／／访问vi

for（ｐ=G—>aｄｊｌisｔ［i］。fｉrstｅｄge；ｐ；p=ｐ—>next)ﻫ//依次搜索vｉ的邻接点vj(不妨设ｐ—〉ａdjvex=j)

iｆ（!ｖｉsiｔｅd［ｐ-＞aｄjveｘ］）／/若vj没有访问过

EnQueｕe（&Ｑ,p-〉aｄjvex)；／/vj入队ﻫ｝/／eｎdofwhileﻫ｝//ＢＦSﻫ答:（1)对图中顶点ｖｎ+１,它需入队n次，它被重复访问n次.ﻫ(２)若要避免重复访问同一个顶点的错误,应作如下修改：ﻫvｏiｄＢFＳ（AＬGraph＊G，intk）ﻫ｛//以下省略局部变量的说明，viｓiｔed各分量初值为假

ＩnitQueｕｅ(&Q);//置空队列

EnQｕeue（&Q,k）;／／ｋ入队

vｉsited［i］=ＴRUＥ;／/置访问标记ﻫpｒintf（”%ｃ"，G—>ａdjｌiｓｔ［ｉ］。ｖerteｘ;//访问ｖiﻫｗhｉle（!QｕｅueＥmpｔy（＆Q））{

i=DeQueue(&Ｑ);/／vｉ出队

for（p=G-〉ａdjlist［i］．ｆｉrsteｄge；p；p＝p—>nｅxt）ﻫ/／依次搜索并访问vi的未访问邻接点vj（不妨设p—>adjｖex=j）

ｉｆ(！visited[ｐ－＞adjｖex]）//若vｊ没有访问过ﻫ{priｎtｆ(”％c＂,G—〉adjｌiｓt[i］。verｔex;//访问vjﻫEｎＱueue（＆Ｑ,ｐ->adjvｅx);/／vj入队

｝

｝／/endｏｆwhile

）//ＢＦS7.1８试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和ＢFS遍历的算法来判别顶点vｉ和ｖj（i＜>j）之间是否有路径。

答：(1）基于采用邻接矩阵的DＦＳ

iｎtpathDFSM（MGraｐh＊G,inｔi，iｎtj）

｛//以邻接矩阵为存储结构，判断vi和vj之间是否有路径,若有返回1,否则返回０ﻫｉntk；

visited［i]=TRUE；

for（k=０;ｋ<G－〉ｎ;k++）//依次搜索ｖi的邻接点ﻫif(G-〉edges[i]［k]=＝１＆＆！viｓiｔｅd［k］）ﻫif(k＝=j)return1；/／有路径相通

eｌsｅｒｅｔurn（pａtｈＤFSＭ（G，k,j）；ﻫreturn０；/／无路径相通ﻫ}//DFＳMﻫ(2）基于采用邻接表的ＤFS

ﻫｉntPATＨDＦＳ（ALGraph*G，inti,inｔj)｛

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

EdgｅNｏｄe*p；

vｉsitｅd[i]=TRＵE;//标记ｖi已访问ﻫp＝Ｇ->ａｄｊlist[i］.fｉｒstｅdge；/／取vi边表的头指针ﻫｗhiｌｅ（ｐ){／/依次搜索vi的邻接点vk，这里ｋ=p—〉adjvexﻫiｆ（！visited［p－>ａｄｊｖex])／/若vk尚未被访问

if（ｐ—〉ａdjvex=＝ｊ）ﻫｒｅtuｒn1；

elseｒｕｔｕrnPＡTＨDFS（ｇ，p—〉adjｖｅx,j）;/／则以Ｖｋ为出发点向纵深搜索ﻫp=p—〉nｅxt；//找vi的下一邻接点ﻫ}ﻫreturn0;

｝//PATＨDFＳ

（３）基于邻接矩阵的BFＳ算法ﻫｉntpathBＦSM（MGraph＊G，ｉnti,ｉntj）ﻫ｛／/以邻接矩阵为存储结构，判断ｖi和vj之间是否有路径，若有返回1，否则返回0ﻫintk；ﻫCｉrＱueuｅQ;

initQueuｅ(＆Ｑ）；ﻫｖisiｔｅd[ｉ]=TRＵE;

EｎQｕeue(＆Q，i)；ﻫwhile(！QueueEmpｔy（&Q））{ﻫｉ=ＤｅQueue(＆Q);//ｖi出队

fｏr(k=0；k<G-〉n;k＋+）//依次搜索vi的邻接点vｋﻫif（G—〉eｄges［i]［k]=＝1＆＆！ｖisited［k]）｛//vｋ未访问ﻫif(ｋ==j）return１；ﻫvisited［k］=TRＵE；

ＥnQueue(&Ｑ,k)；//访问过的vk人队

｝

}//eｎdwhileﻫreturｎ0；ﻫ｝／／ｐathBFＳMﻫ（4)基于邻接表为存储结构的BFS算法ﻫintBFS（ALGｒａph＊G,inti,intj)

｛//以邻接表为存储结构，判断ｖｉ和vj之间是否有路径,若有返回1，否则返回０

iｎti；

CirＱｕeｕeQ；/／须将队列定义中DaｔaTｙpｅ改为int

EdgeNode＊p；

ＩnｉtQuｅue（&Q)；//队列初始化ﻫviｓｉtｅd［i］=ＴRUE；

ﻫＥｎQueuｅ（&Q,i）；//ｖi已访问，将其人队.(实际上是将其序号人队）ﻫｗhile（!QuｅuｅＥｍptｙ（＆Q））｛／/队非空则执行ﻫi=DeQueuｅ（＆Q);//相当于vｉ出队

p=Ｇ-＞ａdjlist[ｉ].ｆirsｔedge；/／取vi的边表头指针

wｈile（ｐ）｛//依次搜索vi的邻接点ｖｋ（令p—〉adjvｅx＝ｋ)

if（!visiteｄ[p->adjｖｅx]）//若vｋ未访问过ﻫiｆ（p-〉adjvex==j)

retuｒｎ1；ﻫelｓe｛

visited[P-〉adjvex］＝ＴRUE;

ﻫEnQueue（&Q，p－＞adjvex）；

}//访问过的vk人队ﻫ

p=ｐ—>ｎext；//找vi的下一邻接点

｝//endｗhilｅ

｝//ｅｎｄｗhilｅﻫ

reｔurn0；

｝//eｎdoｆpaｔｈBFS7．19试分别写出求DFS和BFS生成树(或生成森林)的算法，要求打印出所有的树边。

答：(1）求DFS生成树

tｙｐedefｅnｕm｛FAＬＳＥ,TRUE}Ｂooｌean；//ＦALSE为0，TＲUE为1

Boｏｌeanvｉsｉｔed［MaxＶeｒteｘＮum]；/／访问标志向量是全局量

voｉdDＦSTraversｅTREE(AＬGraph*G）ﻫ｛//求深度优先生成树（以邻接表表示的图G),而以邻接矩阵表示G时，

／/算法完全与此相同，只要将DFＳTrｅe(G，i）改为DＦSＭTｒee(G，i）即可

inti；

foｒ(i＝0；ｉ<G-＞n；ｉ+＋)ﻫｖｉsited[i]=ＦAＬＳE;//标志向量初始化ﻫfoｒ(ｉ=０;i<G－>n；i++)ﻫiｆ（！visｉteｄ［i]）//vi未访问过ﻫDFＳTrｅe(G,ｉ）；//以vi为源点开始DＦS搜索，求DFＳ生成树的边ﻫ｝//ＤＦSTraｖersｅ

voｉdDFSTree（ＡLGｒaph*Ｇ，inｔi）｛

//以ｖi为出发点对邻接表表示的图G进行深度优先搜索，打印生成树（生成森林)的边ﻫEdgeNｏdｅ＊p;

visited［i]=ＴＲUE;//标记vi已访问

p=G-〉adｊliｓt［ｉ］．ｆiｒstedｇｅ；//取vi边表的头指针

ｗhilｅ（p)｛／/依次搜索vｉ的邻接点ｖj，这里j＝ｐ-〉aｄjvｅx

if（！visitｅd[p－>adjvex]）//若ｖj尚未被访问ﻫ｛pｒiｎtf（＂（％c，％c)\ｎ”，Ｇ—＞aｄjlist[i］.vｅｒteｘ，G-〉ａｄｊｌist［p—>ａdｊvex］.ｖertex）

；

/／打印边

DFSＴree（g，p-〉adjｖex）;//则以Vj为出发点向纵深搜索ﻫ}

p=p－>ｎext；//找vi的下一邻接点

}

｝/／ＤＦS

voidＤFSＭＴrｅe(MＧraph*G，iｎti）ﻫ{//以ｖi为出发点对邻接矩阵表示的图G进行深度优先搜索，打印生成树（生成森林）的边

intj;ﻫvｉsｉtｅd[i]＝TRUE；

fｏｒ（j=0；j<G-＞n；j＋+）//依次搜索vi的邻接点

iｆ（G—〉ｅdges［i］[j]==1＆&！visitｅd[j］）ﻫ｛

ｐriｎtf(”(％c，％c）\n”，G—〉ｖｅxｓ［ｉ]，Ｇ－>veｘs［j]）;//打印边

DＦＳMＴree(G,ｊ)；//(vi,vj)∈E,且vｊ未访问过，故vj为新出发点

}

｝//ＤＦSMTrｅeﻫ（2）求BFS生成树ﻫtypｅdefenum{FALSE，TＲUＥ｝Boｏｌｅan;/／FALSＥ为0，TRUE为１

Boolｅaｎｖisitｅｄ［MaｘVeｒｔexＮum］;／/访问标志向量是全局量ﻫvoidBFSTraｖeｒseＴRＥE（ＡLＧrａph＊G）

｛／/求广度优先生成树(以邻接表表示的图G），而以邻接矩阵表示Ｇ时,

/／算法完全与此相同，只要将BFＳTrｅe（G,i）改为BＦSＭＴreｅ（G，i）即可ﻫ

inti；ﻫ

for（i=0;i<Ｇ—>n；i+＋)ﻫ

visitｅd[i］=FALSＥ；//标志向量初始化

fｏr（i＝0；ｉ<G－〉n；i+＋）ﻫif(!visited[i］)/／vi未访问过ﻫＢＦSTree（G,i）;/／以vi为源点开始ＢFS搜索，求BFS生成树的边ﻫ｝//BFSTｒaverseﻫｖoｉdBＦＳTreｅ(ＡLGrａph*G，iｎtｋ）

｛//以ｖｋ为源点对用邻接表表示的图G进行广度优先搜索,并求出ＢFS生成树边ﻫinｔi;ﻫCirＱｕeuｅQ;／／须将队列定义中DataTyｐe改为intﻫEdgeＮｏde*ｐ；

IｎitQuｅｕe（＆Ｑ)；//队列初始化

visｉｔｅd[ｋ]=TＲＵE；

EnＱｕeue(＆Ｑ，ｋ）;/／vk已访问，将其人队。(实际上是将其序号人队）ﻫwｈｉｌe（！QｕｅueＥmｐty（&Q)）｛／/队非空则执行

ｉ=DeQuｅｕe（＆Q)；//相当于vi出队

p＝Ｇ－〉ａdjlｉst[i］.firstedｇe；//取vi的边表头指针

ｗｈilｅ(p){//依次搜索vi的邻接点ｖj（令ｐ—>ａｄjveｘ=j）

if（!ｖisｉｔｅd［p-＞adiveｘ]){//若vj未访问过

ｐrｉntf("（％c，％c）\n"，G－〉adjlｉsｔ［i］.vｅｒteｘ，G-〉aｄjliｓt［ｐ—＞adjveｘ］.verｔeｘ）;

/／打印边ﻫvisited［P—＞adｊvex］=ＴRUE;

ﻫEnQueue(＆Q,p—〉adjｖｅｘ)；／／访问过的vｊ人队

｝//endiｆﻫp=p-＞ｎext;//找vi的下一邻接点ﻫ｝//endwhileﻫ}//enｄwhiｌeﻫ｝/／ｅndofBＦＳTreｅ

ﻫvoidBFSＭTrｅe（MＧraph＊G，intk）

{/／以vｋ为源点对用邻接矩阵表示的图Ｇ进行广度优先搜索，并求出BFS生成树边ﻫiｎti，j；ﻫＣiｒＱｕｅuｅＱ;

IｎitQueue(＆Ｑ）；

visiｔｅｄ［k］=ＴRUE;

EnQueuｅ（&Q,ｋ)；

ｗｈｉｌe(!QueｕｅEmpty（＆Q）)｛

i=ＤeＱｕeue（＆Q）;／/vｉ出队ﻫfor（j=0；j〈G－〉n；j++）//依次搜索vi的邻接点vj

if（G-＞edges［i][j]==１&&!vｉsitｅd[ｊ］){／／vi未访问ﻫprintf（”(％c,％c)\n",G->vexs［i］，Ｇ－＞vexs［j］);//打印边ﻫvisiteｄ［j］＝TＲUE；

EｎQuｅｕe（&Q,j）；//访问过的ｖj人队ﻫ}ﻫ}//endwhilｅﻫ}//ＢＦＳMTree7.20写一算法求连通分量的个数并输出各连通分量的顶点集。

答：tｙpedefｅnｕm{FALSE,TＲUE}Boolean；/／ＦＡLＳE为０,TRＵＥ为1ﻫBooleaｎｖisｉｔed[MaｘVｅrtexNｕm]；/／访问标志向量是全局量ﻫvoｉdDFSTｒaverse(AＬGｒaph＊Ｇ）ﻫ｛//深度优先遍历以邻接表表示的图G，求连通分量的个数和各连通分量的顶点集ﻫinｔi；

for(i=0；i〈G－〉n；i++）

viｓited［i]=ＦＡLSE；／/标志向量初始化ﻫj=0；//连通分量个数计数器ﻫfor(i=0；i<G—>n；i＋+)

if（！viｓｉｔｅd[i］）//vｉ未访问过

｛j＋+；ﻫｐriｎtf("connecｔedcoｍｐonｅｎt%d：｛”，j）；

ＤＦS(G，i)；//以ｖi为源点开始DFS搜索ﻫprｉntｆ(”｝\n");

}

｝//DFＳTraverseﻫvoｉｄDFS(AＬＧraph*G,ｉntｉ）｛

ﻫ／/以vi为出发点对邻接表表示的图G进行深度优先搜索ﻫEdgeＮｏde＊ｐ；

printf(＂%ｃ,”，G—＞ａdjlist[i］。ｖertｅx）；//访问顶点viﻫvisitｅｄ[i］=TＲUE；/／标记vi已访问

p=G-＞adjｌist[i]．firｓteｄge；//取vi边表的头指针ﻫwhile（p)｛//依次搜索vi的邻接点ｖj，这里j=ｐ-〉adjｖｅxﻫｉf（!visiｔed［p—〉ａｄjvex]）/／若vi尚未被访问

DFS（g，p-＞ａdjｖeｘ）;／/则以Ｖj为出发点向纵深搜索

p=ｐ—〉next；/／找ｖi的下一邻接点

｝

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

(１)求顶点vi到顶点vｊ（ｉ<〉j)的最短路径

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

要求输出路径上的所有顶点(提示：利用ＢFS遍历的思想）ﻫ答：(1)求顶点vｉ到顶点vj（i〈〉ｊ）的最短路径

intshoｒteｓtpath（AＬGraｐh＊G,iｎti，intj）ﻫ｛//对邻接表表示的图Ｇ，求顶点ｖi到顶点ｖj（i<＞j)的最短路径

ｉｎｔdｉsｔ[MａxVertexNum］；ﻫＣｉrQueueＱ；//须将队列定义中DaｔａTｙpｅ改为inｔﻫEdgeNode＊p；ﻫintk；

for(k＝０;k〈G－〉n;ｋ++)ﻫｄist［k]=0;/／距离向量初始化ﻫIｎｉtQueue(＆Q）；//队列初始化

viｓｉtｅｄ［i]=ＴRUE；

ﻫEｎQueue(＆Q,i);

ｗhｉｌｅ(!ＱuｅuｅＥmpty（&Ｑ））{//队非空则执行

i=DeQueue（&Ｑ)；/／相当于vi出队ﻫp=Ｇ->adjｌist[i]．firstｅdge；//取vi的边表头指针ﻫwhile(p）{//依次搜索vi的邻接点ｖｋ(令ｐ-〉ａdjｖex=k）ﻫiｆ(！visitｅd［p－〉adjｖｅx］）｛／/若vj未访问过

dｉsｔ［ｐ-＞ａdjvｅｘ]++；ﻫｉf(p－>adjｖex=＝ｊ)reｔuｒnｄist[p-〉aｄｊvex］;ﻫviｓｉｔｅd［P-＞adｊvex]=TRＵE；

EnQuｅuｅ(&Q，ｐ—>ａdｊvex）;/／访问过的vk人队

}//endｉｆ

p＝ｐ-＞neｘt；//找vi的下一邻接点

}//eｎｄwｈileﻫ｝//endwhilｅﻫ｝//ｅｎdofshorteｓtpatｈﻫﻫiｎtＢFSM(MGｒaph＊G，ｉｎti，ｉntj）ﻫ｛//对邻接链表表示的图G,求顶点vi到顶点vj(i＜>j）的最短路径ﻫintｄisｔ［MａｘVeｒｔｅxNum],k;ﻫＣirQuｅｕeQ;

initQueｕe（＆Q）;

ｆｏr（k＝0；k<G-〉n；k++）

dist［i］＝0;/／距离向量初始化ﻫvisｉted［k]=TＲUＥ;ﻫEnQueuｅ(＆Q,i）；

whｉｌｅ(！QueuｅEmｐty（&Ｑ）)｛ﻫi＝DｅQueｕe(＆Q）；//ｖｉ出队

ｆｏr（k=0；k〈G－〉n;k＋+)//依次搜索vi的邻接点vk

ｉf（G->ｅｄｇes[i］[k］=＝１＆＆!visited[ｋ］）{／/vｋ未访问ﻫｄist［k］++；ﻫｉf（ｋ=＝j）returｎdist[ｊ］;ﻫｖｉsiｔed［ｋ］=TRUE；

EnQueue（＆Q,k）；／／访问过的ｖk人队

}

｝/／eｎdwhｉleﻫ}／/ＢFSMﻫ

（２）求源点vi到其余各顶点的最短路径

ﻫvoidshｏrtestpａth（ALGraph＊Ｇ，ｉntｉ)

｛//对邻接表表示的图Ｇ,求顶点vi到顶点vj（i＜〉j)的最短路径

ｉntｄist[MaｘＶeｒtexNuｍ］；ﻫｉntpｒe[ＭaxVｅrtexNｕｍ］;//pre［k]中存放vi到vk路径中,vk的前趋的序号

CirＱuｅuｅQ；/／须将队列定义中ＤａtaType改为intﻫEdgeNode＊p；

intｋ,j；

foｒ(k=0;ｋ＜Ｇ—>n；ｋ++)

｛dｉｓt［ｋ］=0；／/距离向量初始化ﻫpｒe[ｋ］=k；ﻫ}

IniｔQuｅue（&Q）；//队列初始化

visｉteｄ［i］＝TRUE;

ﻫEnQｕeue（＆Q，i）；

whilｅ(！QｕeueEmpｔy(＆Q)）{//队非空则执行ﻫi=DeQueue（＆Ｑ）；／／相当于vi出队ﻫp=G—＞adjlist［i]．ｆｉrsteｄｇe；//取vi的边表头指针

while（p）{／／依次搜索ｖｉ的邻接点vk（令p－〉adjvex=k）

if（!visited［p—〉ａｄjｖex］）｛//若vj未访问过ﻫdisｔ［p->ａdjvex］＋＋;ﻫpre[ｐ-〉adｊvex］=i;

visiｔed[P—＞ａdjvex］＝TRUＥ；

ﻫEnQｕeue（&Q，p—＞adjveｘ)；／/访问过的vk人队ﻫ｝//endｉf

p=p—〉next；//找vi的下一邻接点

}／/endwｈｉｌeﻫ｝/／ｅｎdwhile

for(k＝０；k<Ｇ—〉ｎ；k++)/／打印各顶点的最短路径和长度ﻫ{printf（"paｔhof％ｃis％d："，Ｇ－＞ａdjｌist［ｋ］。ｖerｔex，dist［k]）；ﻫ

j=k；ﻫ

ｐrintｆ(＂％ｃ"，G-〉aｄjlisｔ［ｋ]．vertex）;ﻫ

ｄoﻫ｛ﻫj=ｐｒe［j］；

print(”〈-%ｃ”,G—>adjlｉｓt［j］.vertex）;ﻫ｝ﻫｗｈｉlｅ（j！=ｉ）;

printｆ（”\n"）;

}

}/／endofshorteｓｔｐａtｈﻫﻫvoidsｈorｔeｓｔpａthＢFSM(MGｒaｐh*G，inti)

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

ｉntｄist[ＭaxVeｒtｅxＮum]，k,ｊ；

intｐre[MaxVertｅxNum］;/／pre［k］中存放ｖi到vｋ路径中，vk的前趋的序号

CiｒＱuｅueQ；ﻫiniｔQueｕe（＆Q)；

ｆｏｒ（ｋ＝0;k<Ｇ—〉n;ｋ＋+）

{disｔ[k］＝0；/／距离向量初始化

pre[k］=k;ﻫ}

ｖiｓｉｔed[k]＝TRＵE；

ＥnQueuｅ（＆Q，ｉ)；

while(！QueueEmｐtｙ（＆Q)）{ﻫｉ=DeQueue（&Q）；//ｖｉ出队

for(k=0；ｋ〈G—>n;k++）//依次搜索ｖｉ的邻接点vk

ｉf（G—>edges［i][k]==1＆&!vｉsｉtｅｄ[k]）{//vk未访问

dｉsｔ[k]+＋;

pｒe［k］＝i；ﻫvisiｔed［k]=TRUＥ；

EnQuｅue(＆Q，k);／／访问过的vk人队ﻫ}

｝／/enｄwhile

for（k=0;k＜Ｇ—〉ｎ；k＋＋）//打印各顶点的最短路径和长度ﻫ｛ｐriｎtf(”ｐａthof％cis％d：＂，G-＞ｖerｔex［k］,dist[ｋ］);

ｊ=k；ﻫprintf("%c”，G->vertex［k］);ﻫdｏﻫ｛ﻫｊ=pre［j];

ｐriｎtf（＂<－％c”,G-＞veｒtex［ｊ]）；

}ﻫwｈilｅ（j！＝ｉ)；

pｒiｎｔf(”＼n”)；

}

}／／ｓhｏrtｅstpathＢFSM7．22以邻接表为存储结构,写一个基于DＦS遍历策略的算法，求图中通过某顶点ｖｋ的简单回路（若存在）.

答：ﻫintｃｉrcleＤFS（ALGrａｐｈ＊G,iｎtk)｛

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

EdgｅＮode*p;

prｉntf（"％ｃ”，G—〉adｊlｉst［k］.veｒｔex)；／/访问顶点ｖk

viｓitｅd[ｋ]＝TRUE；//标记vｋ已访问ﻫp=G->adjlist[k]。fiｒstｅdgｅ；／／取ｖｋ边表的头指针ﻫwhｉlｅ（p)｛//依次搜索vk的邻接点vj,这里j=p-〉adjvexﻫif(!vｉｓｉted[ｐ—>adjvex］）//若vｊ尚未被访问ﻫDFS(G，ｐ-〉ａdjvex）；//则以Vｊ为出发点向纵深搜索ﻫelseiｆ（p-〉ａdjvex==k)

ﻫ｛priｎｔf（”％c"，G—>ａdjlist［k］。vｅｒｔex)；retｕrn１；｝ﻫp=p->next;//找vk的下一邻接点

}

return0；ﻫ}//ＤFS7.23写一算法求有向图的所有根(若存在)，分析算法的时间复杂度。ﻫ

答：

typｅdefｅnum｛FALＳE，TRUE}Boolｅan；//FALSE为０,TRUＥ为1ﻫBooleanviｓited［MaｘVerｔexNum］；／／访问标志向量是全局量

voidDFSTraveｒｓe(ALGraｐh＊Ｇ）

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

for(j＝0；j〈G—〉n；j＋+)

{ﻫfoｒ(i=0;i<G->n；i+＋)ﻫvｉｓiｔed［i]=FALSＥ；//标志向量初始化ﻫＤＦS（G，j）;//以ｖj为源点开始DFS搜索,也可用BＦS（G，j)ﻫi＝0;ﻫwhilｅ（ｉ<Ｇ-〉n）&&（vｉsiｔeｄ[ｉ]==TRUＥ）ﻫｉ+＋;ﻫif(i＝＝G—>n)pｒinｔf（”root:％c",G-〉ａdjlisｔ［j］.ｖertex);ﻫ｝ﻫ｝//DFSTｒａversｅ

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

若调用的DＦSM算法的复杂度为Ｏ（n＊n）,所以该算法的时间复杂度为O(ｎ^3)7。2４改写７。５节的算法Ｐrｉnｔ,使输出的从源点到各终点的最短路径是正向的。(提示:使用栈暂存路径)ﻫﻫ答：ﻫvoidpriｎｔ（ｐathｐ，ｄistancｅd）ﻫ{//输出最短路径及其长度，从源点到各终点的最短路径是正向的ﻫｉnti，ｐrｅ;ﻫSeｑSｔａｃkS；//定义一个栈ﻫIｎitSｔａｃk（&s）；ﻫfor(i＝0；i<n;i+＋){/／依次打印各顶点ｉ的最短路径及其长度ﻫprintｆ("＼ｎdistanｃe：%ｄ,patｈ：”,ｄ[i］)；//输出终点ｉ的最短距离

Push（＆Ｓ，i）；//终点i入栈

ｐre＝ｐ[ｉ]；/／找终点ｉ的前趋

while（pre！=—1)

｛ｐush（＆ｓ，pre)；ﻫpre=ｐ[prｅ]；/／继续找前趋ﻫ}//endｗhileﻫpriｎｔf（"%d”,ｐop（&s））;

ｗhile(！StackEmpty（Ｓ））

prｉntf(”，％d”,pｏｐ(&s）)；ﻫ｝//eｎdfor

ﻫ｝／／endｐriｎｔ７.２５对7.６节的NonＳuccＦirsｔToｐSort算法求精，分别以邻接矩阵和邻接表作为存储结构，写出其具体算法，并分析算法的时间。ﻫﻫ答：ﻫﻫ(1）以邻接矩阵作为存储结构

vｏidNonＳuccFiｒstTｏpＳｏｒt（MGraphG）{／/优先输出无后继的顶点

iｎtoutdegｒｅe［MａxＶertexＮum]；//出度向量，此处MａxVｅrtｅxNｕm〉=Ｇ．ｎﻫSeqSｔａcｋS，T；//将栈中data向量的基类型改为inｔﻫinｔｉ，j，ｃｏunｔ=0；／/ｃｏｕnt对输出的顶点数目计数，初值为０ﻫfor（i=0；i<G.ｎ；i++)

outdｅgreｅ［i］=０;ﻫfｏr(i=0;i〈Ｇ．ｎ；i＋+)

fｏr（j＝0;ｊ<G。n;j＋+)ﻫｏｕｔdｅgｒee［i］=ouｔｄegree［i]＋ｇ.edｇe［i]［ｊ]；

ＩnitSｔaｃｋ（&ｓ）;

for（i＝0;i<G。n;ｉ＋+）ﻫif(outｄegｒee［ｉ]＝＝０）

ﻫPusｈ（＆S,i）；//出度为0的顶点ｉ入栈

ＩnitSｔaｃk（＆T)；ﻫwhilｅ（！SｔaｃkEｍpty（S）)/／栈非空，有出度为０的顶点

{ｉ＝pop（＆ｓ);ﻫＰuｓｈ（＆T,ｉ）;

ｃouｎｔ++；/／顶点计数加1

ｆoｒ(ｊ=0;j〈Ｇ。ｎ；ｊ+＋)／/修改以ｉ为弧头的弧的弧尾顶点的出度ﻫif（G.eｄge［j］[ｉ］==1)

｛G.ｅdge［j］［ｉ］＝0；

ｏutｄegrｅe［j］——;ﻫif（oｕtｄegｒee［ｊ］＝=0)／/将新生成的出度为０的顶点入栈

ﻫＰush（&S,j）；/／出度为0的顶点j入栈ﻫ}/／endoｆifﻫ}//ｅndofwhile

if（count〈G。n）

ｐrｉntｆ（"Ｇ中存在有向环，排序失败！”）；ﻫeｌse{／/输出拓扑序列

whilｅ(！ＳtackEmptｙ（T）)

printｆ(”％c”,G.ｖertex［pop(&T)]）;

｝

}ﻫ

（2）以邻接表作为存储结构ﻫvoidNｏnＳuccFｉrstTopSort(ALＧraphG){

//优先输出无后继的顶点,此处用逆邻接表存储ﻫiｎtｏutdegreｅ[MａxＶｅrtexNｕm］；//出度向量，此处MaxVertexNuｍ>＝G.nﻫSeqStaｃｋS，T；//将栈中dａｔa向量的基类型改为intﻫinti,ｊ,coｕｎt=０;／／count对输出的顶点数目