工大數(shù)據(jù)結(jié)構(gòu)第四章作業(yè)

數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)

第四章圖

一、選擇題

1、在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。

A.1/2B.1C.2D.4

2、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的B倍。

A.1/2B.1C.2D.4

3、G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有D個(gè)頂點(diǎn)。

A.6B.7C.8D.9

邊=頂點(diǎn)數(shù)*（頂點(diǎn)數(shù)-1）/2再加入一個(gè)孤立點(diǎn)

4、有n個(gè)頂點(diǎn)的圖的鄰接矩陣使用B數(shù)組存儲(chǔ)的。

A.一維B.n行n列C.任意行n列D.n行任意列

5、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表表示，則表頭數(shù)組大小至少為（假

設(shè)下標(biāo)為0的數(shù)組參與使用）D。

A.n-1B.n+lC.nD.n+e

6、下列說(shuō)法正確的是C。

A.有向圖的鄰接矩陣一定是不對(duì)稱的

B.有向圖的鄰接矩陣一定是對(duì)稱的

C,無(wú)向圖的鄰接矩陣一定是對(duì)稱的

D.無(wú)向圖的鄰接矩陣可以不對(duì)稱

7、深度優(yōu)先遍歷類(lèi)似與二叉樹(shù)的A：

A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷

8、廣度優(yōu)先遍歷類(lèi)似與二叉樹(shù)的D：

A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷

9、下列關(guān)于開(kāi)放樹(shù)（FreeTree）的說(shuō)法錯(cuò)誤的是￡：

A.具有n個(gè)結(jié)點(diǎn)的開(kāi)放樹(shù)包含n-1條邊

B.開(kāi)放樹(shù)沒(méi)有回路

C.開(kāi)放樹(shù)可以是非連通圖

D.在開(kāi)放樹(shù)中任意加一條邊，一定會(huì)產(chǎn)生回路

10、在如下圖所示的圖中，從頂點(diǎn)a出發(fā)，按深度優(yōu)先遍歷，則可能得到的一種頂點(diǎn)的序列

為Do

A.a,b,e,c,d,fB.a,c,f,e,b,d

C.a,e,b,c,f,dD.a,e,d,f,c,b

11、在如上圖所示的圖中，從頂點(diǎn)a出發(fā)，按廣度優(yōu)先遍歷，則可能得到的一種頂點(diǎn)的序列

為A?

A.a,b,e,c,d,fB.a,b,e,c,f,d

C.a,e,b,c,f,dD.a,e,d,f,c,b

12、設(shè)網(wǎng)(帶權(quán)的圖)有n個(gè)頂點(diǎn)和e條邊，則采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的Prim算

法的時(shí)間復(fù)雜度為C。

A.0(n)B.O(n+e)C.0(n2)D.0(n3)

13、設(shè)圖有n個(gè)頂點(diǎn)和e條邊，求解最短路徑的Flovd算法的時(shí)間復(fù)雜度為D。

A.O(n)B.O(n+e)C.0(n2)D.O(n3)

14、最小生成樹(shù)是指C。

A.由連通網(wǎng)所得到的邊數(shù)最少的生成樹(shù)。

B.由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹(shù)。

C.連通網(wǎng)中所有生成樹(shù)中權(quán)值之和為最小的生成樹(shù)。

D.連通網(wǎng)的極小連通子圖。

15、下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是B。

A.關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。

B.任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成?！赡苡卸鄺l關(guān)鍵路徑

C.所有關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成。

D.某些關(guān)鍵工程若提前完成，那么整個(gè)工程將會(huì)提前完成。

16、在AOE網(wǎng)中，始點(diǎn)和匯點(diǎn)的個(gè)數(shù)為B。

A.1個(gè)始點(diǎn)，若干個(gè)匯點(diǎn)B.若干個(gè)始點(diǎn)，若干個(gè)匯點(diǎn)

C.若干個(gè)始點(diǎn)，1個(gè)匯點(diǎn)D.一個(gè)始點(diǎn)，一個(gè)匯點(diǎn)

17、在下圖所示的無(wú)向圖中，從頂點(diǎn)vl開(kāi)始采用Prim算法生成最小生成樹(shù)，算法過(guò)程中產(chǎn)

生的頂點(diǎn)次序?yàn)锽。

A.vl,v3,v4,v2,v5,v6B.vl,v3,v6,v2,v5,v4

C.vl,v2,v3,v4,v5,v6D.vl,v3,v6,v4,v2,v5

18、在上圖所示的途中,采用Cruskal算法生成最小生成樹(shù)，過(guò)程中產(chǎn)生的邊的次序是C.

A.(vl,v2),(v2,v3),(v5,v6),(vl,v5)B.(vl,v3),(v2,v6),(v2,v5),(vl,v4)

C.(vl,v3),(v2,v5),(v3,v6),(v4,v5)D.(v2,v5),(vl,v3),(v5,v6),(v4,v5)10>如下

圖所示的圖中，其中一個(gè)拓?fù)渑判虻慕Y(jié)果是A。

A.vl->v2->v3->v6->v4->v5->v7->v8

B.vl->v2-*v3->v4->v5-^v6-*v7-*v8

C.vl->v6->v4->v5->v2->v3->v7->v8

19、在下圖所示的AOE網(wǎng)中，活動(dòng)a9的最早開(kāi)始時(shí)間為B

A.13B.14C.15D.16

20、在上圖所示的AOE網(wǎng)中，活動(dòng)a4的最遲開(kāi)始時(shí)間為D

A.4B.5C.6D.7

21、設(shè)圖有n個(gè)頂點(diǎn)和e條邊，當(dāng)用鄰接矩陣表示該圖時(shí)，則求解最短路徑的Floyd算法的

時(shí)間復(fù)雜度為Do

A.O(n)B.O(n+e)C.O(n2)D.O(n,)

二、填空題

1、若無(wú)向圖G中頂點(diǎn)數(shù)為n,則圖G至多有n*(n-l)/2條邊;若G為有向圖，則圖

G至多有n*(n-l)條邊。

2、圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是鄰接矩陣和鄰接

________________o

3、若G是有向圖，則把鄰接到頂點(diǎn)v的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v的指針域

;把鄰接于頂點(diǎn)v的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v的頂點(diǎn)

M____________________?

4、己知一個(gè)圖的鄰接矩陣表示，計(jì)算第j個(gè)頂點(diǎn)的入度的方法是第i列元素之

和___________，計(jì)算第j個(gè)頂點(diǎn)的出度的方法是第i行非零元素之和。

5、若將圖中的每條邊都賦予一個(gè)權(quán)，則稱這種帶權(quán)的圖為網(wǎng)絡(luò)。

6、無(wú)論是有向圖還是無(wú)向圖，頂點(diǎn)數(shù)n、邊數(shù)e和各頂點(diǎn)的度D(v。之間的關(guān)系為：

。=導(dǎo)士D(vl

2i=0。

7、若路徑上第一個(gè)頂點(diǎn)V,與最后一個(gè)頂點(diǎn)Vm重合，則稱這樣的簡(jiǎn)單路徑為_(kāi)____回

_______。

8、如果圖中任意一對(duì)頂點(diǎn)都是連通的，則稱此圖是連通圖；非連通

圖的極大連通子圖叫做連通分量。

創(chuàng)建一個(gè)鄰接矩陣圖的復(fù)雜度是；創(chuàng)建一個(gè)鏈接表圖的復(fù)雜度是

O(2e+n)o

9、圖的遍歷有深度優(yōu)先搜索和廣度優(yōu)先遍歷等方法。

10、在深度優(yōu)先搜索和廣度優(yōu)先搜索中，都采用visitedril=1的方式設(shè)置第i個(gè)頂點(diǎn)

為new,而采用visited[i]=0的方式標(biāo)識(shí)第i個(gè)結(jié)點(diǎn)為old。

11、由于深度優(yōu)先算法的特點(diǎn)，深度優(yōu)先往往采用遞歸的方式實(shí)現(xiàn)。

12、由于廣度優(yōu)先算法的特點(diǎn)，在廣度優(yōu)先實(shí)現(xiàn)過(guò)程中，往往要借助于另一種數(shù)據(jù)結(jié)構(gòu)

隊(duì)列實(shí)現(xiàn)。

13、在深度優(yōu)先搜索和廣度優(yōu)先搜索中，在搜索過(guò)程中所經(jīng)過(guò)的邊都稱為樹(shù)邊和回退

邊。

14、連通而且無(wú)環(huán)路的無(wú)向圖稱為開(kāi)放樹(shù)。

15、對(duì)于含有n個(gè)頂點(diǎn)e條邊的連通圖，利用Prim算法求其最小生成樹(shù)的時(shí)間復(fù)雜度為

0(n2),利用Kruscal算法求最小生成樹(shù)的時(shí)間復(fù)雜度是

O(|E|*log|E|)o

3、頂點(diǎn)表示活動(dòng)的網(wǎng)簡(jiǎn)稱為AOV；邊表示活動(dòng)的網(wǎng)簡(jiǎn)稱為

A0Eo

16、一個(gè)含有n個(gè)頂點(diǎn)的無(wú)向連通圖，其每條邊的權(quán)重都是a(a>0),則其最小生成樹(shù)的權(quán)重

等于a*(n-l)<>

17、具有n個(gè)頂點(diǎn)的有向圖，如果采用鄰接矩陣表示該圖，則求某頂點(diǎn)到其他各頂點(diǎn)的最短

路徑的Dijkstra算法的時(shí)間復(fù)雜度是;如果采用鄰接表表示該圖，則

時(shí)間復(fù)雜度為0(e)o

18、在用Dijkstra算法求單源最短路徑的過(guò)程中，將頂點(diǎn)集合V劃分為兩個(gè)集合S和V-S,

其中S中的點(diǎn)為，V-S中的點(diǎn)為從V-S中選擇頂點(diǎn)，

使D「w]的值最小并將w加入集合S中，則w的最小路徑已求出o

19、求每一對(duì)頂點(diǎn)之間的最短路徑，可以用兩種方法，一種是分別對(duì)每個(gè)頂點(diǎn)采用

算法，另一種方法是對(duì)每個(gè)邊采用算法。

20、假設(shè)有向圖的鄰接矩陣C的傳遞閉包為A,則A[i][j]=l表示(i,i)屬于

E<,

21、有向圖的中心點(diǎn)是指具有最小偏心度的結(jié)點(diǎn)o

三、已知一個(gè)無(wú)向圖如下圖所示，試給出該圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖(畫(huà)圖，分別

用矩陣和數(shù)組鏈表圖表示)，并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫(xiě)

兩種表示方法的存儲(chǔ)結(jié)構(gòu)、相關(guān)基本操作，并在主函數(shù)中創(chuàng)建該圖。

usingnamespacestd;

#definefreever'#*

#defineNumVertices6〃頂點(diǎn)個(gè)數(shù)

typedefcharVertexData;//頂點(diǎn)數(shù)據(jù)類(lèi)型

typedefintEdgeData;〃邊上權(quán)值類(lèi)型

typedefstructnode{〃邊表結(jié)點(diǎn)

intadjvex;〃鄰接點(diǎn)域（下標(biāo)）

EdgeDatacost;〃邊上的權(quán)值

structnode*nexl;〃下一邊鏈接指針

}EdgeNode;

typedefstruct{〃頂點(diǎn)表結(jié)點(diǎn)

VertexDatavertex;〃頂點(diǎn)數(shù)據(jù)域

EdgeNode*firstedge;〃邊鏈表頭指針

}VertexNode;

typedefstruct{〃圖的鄰接表

VertexNodevexlist[NumVertices+l];

intn,e;〃圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù)

}AdjGraph;

voidIniADJGraph(AdjGraph*G)

(

G->e=0;

G->n=0;

for(inti=l;i<NumVertices;i++)

(

G->vexlist[i].vertex=freever;

G->vexlist[i].firstedge=NULL;

}

)

boolNewNode(AdjGraph*G,VertexDatav)//增加一個(gè)頂點(diǎn)，成功，返回true,否則返回false

(

if(G->n<NumVertices-1)

(

for(inti=l;ivNumVertices;i++)

(

if(G->vexlist[i].vertex==freever)

(

G->vexlist[i].vertex=v;

G->vexlist[i].firstedge=NULL;

G->n++;

returntrue;

)

)

)

returnfalse;

)

boolIsEdge(AdjGraph*Gintvl,intv2)//判斷vl與v2之間是否有邊相連

(

EdgeNode*p=G->vexlist[vl].firstedge;

if(p==NULL)

returnfalse;

while(l)

(

if(p->adjvex==v2)

(

returntrue;

)

p=p->next;

if(p二二NULL)

returnfalse;

)

returnfalse;

)

voidDelSucc(AdjGraph*G,intvl,intv2)//冊(cè)除vl和v2之間的一條邊

(

if(IsEdge(G,vl,v2))

(

EdgeNode*p=G->vexlist[v1].firstedge,*pl;

if(p->adjvex==v2)

(

pl=p;

G->vexlist[v1].firstedge=p->next;

G->e—;

deletepl;

)

else

(

do

(

pl=p->next;

if(pl==NULL)

break;

if(pl->adjvex==v2)

(

p->next=pl->next;

deletepl;

G->e—;

)

p=p->next;

}while(p!=NULL);

)

p=G->vexlist[v2].firstedge;

if(p->adjvex==v1)

(

pl=p;

G->vexlist[v2].firstedge=p->next;

deletep1;

)

else

do

pl=p->next;

if(pl==NULL)

break;

if(p1->adjvex==v1)

(

p->next=pl->next;

deletepl;

)

p=p->next;

)while(p!=NULL);

voidDelNode(AdjGraph*Gintm)〃刪除第m個(gè)頂點(diǎn)

(

if(G->vexlist[m].vertex!=freever)〃如果第m個(gè)頂點(diǎn)存在

(

G->vexlist[m].vertex=freever;

EdgeNode*p=G->vexlistlm].firstedge;

while(p!=NULL)〃刪除與第m個(gè)頂點(diǎn)相連的邊

(

DelSucc(G,m,p->adjvex);

p=G->vexlistlm].firstedge;

)

G->vexlist[m].firstedge=NULL;

)

boolSetSucc(AdjGraph*Gintvl,intv2,EdgeDataw)//建立vl和v2之間的一條邊，權(quán)重

為w

(

if(G->vexlist[v1].vertex!=freever&&G->vexlist[v2].vertex!=freever)〃vl和v2都為頂

點(diǎn)

(

EdgeNode*p=G->vexlist[vl].firstedge;

if(IsEdge(G,vl,v2))〃判斷vl與v2之間是否存在邊，若存在，則刪除該邊

DelSucc(G,vl,v2);

〃為頂點(diǎn)vl增加邊

p=newEdgeNode;

p->adjvex=v2;

p->cost=w;

p->next=G->vexlist[v1].firstedge;

G->vexlist[v1].firstedge=p;

〃為頂點(diǎn)v2增加邊

p=newEdgeNode;

p->adjvex=vl;

p->cost=w;

p->next=G->vexlist[v2].firstedge;

G->vexlist[v2].firstedge=p;

G->e++；//邊數(shù)加1

returntrue;

)

returnfalse;

1

voidCreateADJGraph_directed(AdjGraph*G)

(

coutcv”輸入頂點(diǎn)數(shù)和邊數(shù):"；

cin?G->n?G->e;〃1.輸入頂點(diǎn)個(gè)數(shù)和邊數(shù)

for(inti=1;i<=G->n;i++)〃2.建立頂點(diǎn)表

(

couivv”輸入第n?i?n個(gè)頂點(diǎn)信息：”；

cin?G->vexlist[i].vertex;//2.1輸入頂點(diǎn)信息

G->vexlist[i].firstedge=NULL;//2.2邊表置為空表

)

for(i=1;i<=G->e;i++)〃3.逐條邊輸入，建立邊表

(

inttail,head;

EdgeDataweight;

cout<〈"輸入第條邊的起始點(diǎn)、終止點(diǎn)以及權(quán)重：”；

cin?tail?head?weight;//3.1輸入

EdgeNode*p=newEdgeNode;//3.2建立邊結(jié)點(diǎn)

p->adjvex=head;//3.3設(shè)置邊結(jié)點(diǎn)

p->cost=weight;

p->next=G->vexlist[tail].firstedge;//3.4鏈入第tail號(hào)鏈表的前端

G->vexlist[tail].firstedge=p;

p=newEdgeNode;

p->adjvex=tail;

p->cost=weight;

p->next=G->vexlist[head].firstedge;

G->vexlist[head].firstedge=p;

)

)//時(shí)間復(fù)雜度：O(2e+n)

voidCreateADJGraph_directed(AdjGraph*G,VertexDataV[],EdgeDataE[][NumVertices],intn)

〃從給定的圖的矩陣表示創(chuàng)建圖，n為頂點(diǎn)的個(gè)數(shù)

G->n=n;

for(inti=1;i<=n;i++)〃2.建立頂點(diǎn)表

(

G->vexlist[i].vertex=V[i-1];//2.1輸入頂點(diǎn)信息

G->vexlist[i].firstedge=NULL;//2.2邊表置為空表

)

for(i=1;i<=n;i++)〃3.逐條邊輸入，建立邊表，由于對(duì)稱性，只考慮上

半角三角形

for(intj=l;j<=n;j++)

{

if(E[i-l][j-l]!=O)

EdgeNode*p=newEdgeNode;//3.2建立邊結(jié)點(diǎn)

p->adjvex=j;//3.3設(shè)置邊結(jié)點(diǎn)

p->cost=E[i-l][j-l];

p->next=G->vexlist[i].firstedge;〃3.4鏈入第tail號(hào)鏈表的前端

G->vexlist[iJ.firstedge=p;

p=newEdgeNode;

p->adjvex=i;

p->cost=E[i-l][j-l];

p->next=G->vexlist[jJ.firstedge;

G->vexlist[j].firstedge=p;

G?>e++;

voidPrintADJ(AdjGraph*G)

(

EdgeNode*p;

inti,j;

EdgeDataresult[NumVertices][NumVertices]={O);

VertexDataver[NumVertices];

cout?,\t,;

for(i=l;i<NumVertices;i++)

cout?G->vexlist[i].vertex?,\t';

ver[i]=G->vexlistfi].vertex;

)

cout?endl;

for(i=l;i<NumVertices;i++)

(

p=G->vexlist[i].firstedge;

while(p!=NULL)

(

result[i][p->adjvex]=p->cost;

p=p->next;

)

}

for(i=l;i<NumVertices;i++)

(

cout?ver[i]?,\t,;

for(j=l;j<NumVertices;j++)

(

cout?result[i][j]?'\t';

)

cout?endl;

)

cout?endl;

)

voidmain()

(

/*

cout?*'無(wú)向圖:"<vendl;

AdjGraphG;

IniADJGraph(&G);

VertexDatav[6]=/v「，'v2','v3「v4「v5','v6'};

EdgeDatae[6][NumVertices]={{0,1,0,1,0,1},

{1,0,1,1,1,0},

(0,1,0,0,1,0),

{1,1,0,0,1,1),

(0,1,1,1,0,0),

{1,0,0,1,0,0}};

CreateADJGraph(&G,v,e,6);

cout?G.n?''?G.e?endl;

NewNode(&G,,vl,);

NewNode(&G,'v2');

NewNode(&G,*v3');

NewNode(&G,\4);

NewNode(&G,'v5');

NewNode(&G,'v6')；

cout?G.n?''?G.e?endl;

SetSucc(&G,1,2,1);

SetSucc(&G,1,4,1);

SetSucc(&G,1,5,1);

SetSucc(&G,2,3,1);

SetSucc(&G,2,4,1);

SetSucc(&G,3,4,1);

SetSucc(&G,3,5,1);

SetSucc(&G,4,5,1);

SetSucc(&G,2,4,3);

cout?G.n?',?G.e?endl;

DelSucc(&G,3,4);

cout?G.n?',?G.e?endl;

DelNode(&G,2);

cout?G.n?''?G.e?endl;

PrintADJ(&G);

*/

四、已知一個(gè)有向圖如下圖所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖（畫(huà)圖，分別用

矩陣和數(shù)組鏈表圖表示），并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫(xiě)兩

種表示方法的存儲(chǔ)結(jié)構(gòu)、相關(guān)基本操作，并在主函數(shù)中創(chuàng)建該圖。

鄰接矩陣表示：

voidIniMGraph_directed(MTGraph*G)

(

fbr(inti=0;i<NumVertices;i++)

for(intj=0;j<NumVertices;j++)

G->edge[i][j]=MaxValue;

G->n=0;

G->e=O;

voidNewNode_directed(MTGraph*GVertexDatav)

(

G->vexlist[G->n]=v;

G->n++;

)

voidDelNode_directed(MTGraph*G,intm)

(

if(G->n==0||m>=NumVertices)return;

fbr(inti=m;i<G->n-l;i++)

G->vexlist[i]=G->vexlist[i+1];

for(inti=0;i<G->n;i++)

if(G->edge[i][m]!=MaxValue)G->e—;

fbr(inti=m;i<G->n-l;i++)

for(intj=0;j<G->n;j++)

G->edge[i1[j]=G->edge[i+1皿；

for(inti=m;i<G->n-l;i++)

for(intj=0;j<G->n-l;j++)

G->edge[j][i]=G->edge[j][i+1];

G->n—;

)

boolIsEdge_directed(MTGraph*Gintvl,intv2)

(

if(v1>=0&&v1<G->n&&v2>=0&&v2<G->n&&vl!=v2)

if(G->edge[v1][v2]!=MaxValue)

returntrue;

else

returnfalse;

returnfalse;

)

voidSetSucc_directed(MTGraph*Gintvl,intv2,EdgeDataw)

(

if(!IsEdge_directed(G,v1,v2)){

G->edge[vl][v2]=w;

G->e++;

)

)

voidDelSucc_directed(MTGraph*Gintvl,intv2)

(

if(IsEdge_directed(G,vl,v2))

(

G->edge[vl][v2]=MaxValue;

G->e—;

voidCreateMGraph_directed(MTGraphVertexDataV[],EdgeDataE[][NumVertices],intn)

(

G->n=n;

for(inti=0;i<n;i++)

G->vexlist[i]=V[i];

for(inti=0;i<G->n;i++)

for(intj=O;j<G->n;j++)

G->edge[i][j]=MaxValue;

fbr(inti=0;i<n;i++)

for(intj=0;j<n;j++)

if(E[i]UJ!=O){

G->edge[i][j]=E[i][j]；

G->e++;

)

)

intmain()

(

MTGraphG;

IniMGraph_directed(&G);

VertexDatav[4]=/vr,'v27V3/v4}

EdgeDatae[4][NumVertices]={{MaxValue,1,1,MaxValue},

{MaxValue,MaxValue,MaxValue,MaxValue},

{MaxValue,MaxValue,MaxValue,1},

{1,MaxValue,MaxValue,MaxValue)};

CreateMGraph_directed(&G,v,e,4);

travel(&G);

system("pause");

return0

)

五、已知一個(gè)圖的頂點(diǎn)集為{a,b,c,d,e),其鄰接矩陣如下圖，考慮圖為無(wú)向圖和有向圖兩

種情況，分別畫(huà)出該圖。

,01001、

10010

00011

01101

<10110>

六、已知一個(gè)連通圖如下圖所示，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列

（假設(shè)從頂點(diǎn)V1出發(fā)）。并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫(xiě)相關(guān)

基本操作，并在主函數(shù)中求出深度優(yōu)先序列和廣度優(yōu)先序列。

#include<iostream>

#include<queue>

usingnamespacestd;

#defineMaxNode10

#defineMaxEdges50

#defineMax100000

classGraph

(

private:

intnodecount;

intedgecount;

inta[MaxNode];

intbfMaxNode][MaxNode];

public:

Graph(int);

intgetNodeCount();

intgetEdgeCount();

voidinsertNode(int);

voidisertEdge(int,int,int);

voiddeleteEdge(int,int);

voidprim(int);

intDFS(int);//深度優(yōu)先搜索

voidDFS(intnode,intv[],int&n);

voidBFS(int);〃廣度優(yōu)先搜索

boolisliantong。;//判斷是否連通

voidliantongfenliang。;//連通分量的數(shù)目

intgelWeighl(int,inl);〃獲得某條邊的權(quán)值

intgetFirstNeighbor(int);〃獲得所給頂點(diǎn)的第一個(gè)相鄰節(jié)點(diǎn)

intgetNextNeighbor(intjnt);〃獲得某一鄰接節(jié)點(diǎn)的下一個(gè)鄰接節(jié)點(diǎn)

Graph::Graph(ints=MaxNode)

(

for(inti=0;i<=s-1;i++)

for(intj=O;j<=s-1;j++)

b[i]Ul=O；

nodecount=0;

for(intk=0;k<=s-l;k++)

a[k]=-l;

intGraph::getNodeCount()

(

returnnodecount;

)

intGraph::getEdgeCount()

(

returnedgecount;

)

voidGraph::insertNode(intit)

(

a[it]=it;

nodecount++;

voidGraph::isertEdge(intx,inty,intw)

{

b[x][y]=w;

b[y][x]=w;

cout?Msucceed!x=u?x?"y=M?y?"weight=,'?w?endl;

edgecount++;

)

voidGraph::deleteEdge(intx,inty)

(

b[x][y]=0;

b[y][x]=0;

cout?"edge(n?x?n,"?y?u)wasdeleted!1';

edgecount";

)

voidGraph::prim(inlx)//生成最小樹(shù)

(

int*d=newint[getNodeCount()];

for(intid=0;id<=getNodeCount()-1;id++)

d[id]=O;

inte[10][10];

for(intim=0;im<=9;im++)

for(intrm=0;rm<=9;rm++)

e[im][rm]=0;

intmin;

intnode;

intl,r;

d[x]=l;

for(inti=1;i<=nodecount-1;i++)

(

min二Max;

for(intj=0;j<=nodecount-1;j++)

if(d[j]==l&&a[j]==j)

(

for(intk=0;k<=nodecount-1;k++)

if(a[k]==k&&d[k]==O&&b[j][k]>O&&b[j][k]<inin)

(

node=k;

1寸

r=k;

min=b[l][r];

1

d[node]=l;

e[l][r]=b[l][r];

)

for(intln=0;ln<=9;ln++)

for(intrn=0;rn<=9;rn+4-)

if(e[ln][rn]>0)

coutvcNvvlnvcTVvmcc”,權(quán)值為

)

voidGraph::BFS(intx)〃廣度優(yōu)先搜索

(

int*v=newint[getNodeCount()];

for(inti=0;i<=getNodeCount();i++)

v[i]=0;

cout?x?"\tn;

v[x]=l;

queue<int>q;

q.push(x);

intnext;

while(!q.empty())

(

x=q.front。；

q-pop();

next=getFirstNeighbor(x);

while(next!=-l)

{if(!v[next]&&a[next]==next)

(

cout?next?M\tH;

v[next]=1;

q.push(next);

)

next=getNextNeighbor(x,next);

)

)

delete[]v;

)

voidGraph::DFS(intnode,intv[],int&n)

(

cout?node?'*\t,*;

n++;

v[node]=l;

intnext=getFirstNeighbor(node);

while(next!=-l)

if(a[next]==next&&!v[next])

DFS(next,v,n);

next=getNextNeighbor(node,next);

)

)

intGraph::DFS(intnode)

(

intn=0;

int*v=newintlnodecountj;

for(inti=0;i<=nodecount;i++)

v[i]=0;

DFS(node,v,n);

delete[]v；

returnn;

)

boolGraph::isliantong()〃判斷是否連通

(

intn=0;

n=DFS(0);

cout?Mnodesnumber:H?nodecount?endl;

cout?"oneliantongfenliangnodesnumber:n?n?endl;

if(n==nodecount)

returntrue;

elsereturnfalse;

)

voidGraph::liantongfenliang()〃連通分量的數(shù)目

(

intn=0;

int*v=newint[nodecountj;

for(inti=0;i<=nodecount-l;i++)

v[i]=0;

for(intj=O;j<=nodecount-1;j++)

if(aU]==j&&!vU]){

coul?"(“；

DFS(j,v,n);

cout?n)H;

delete[]v;

intGraph::getWeight(intx,inty)〃獲得某條邊的權(quán)值

(

returnb[x][y];

)

intGraph::getFirstNeighbor(intx)〃獲得所給頂點(diǎn)的第一個(gè)相鄰節(jié)點(diǎn)

(

intn=-l;

if(nodecount==0)

return-1;

for(inti=0;i<=nodecount-1;i++)

if(b[x][i]!=O)

{n=a[i];

break;

)

returnn;

)

intGraph::getNextNeighbor(intx,inty)//獲得某一鄰接節(jié)點(diǎn)的下一個(gè)鄰接節(jié)點(diǎn)

(

if(y==nodecount-1)

return-1;

intn=-l;

for(inti=y+1;i<=nodecount-1;i++)

if(b[x][i]!=O)

(

n=i;break;

)

returnn;

)

intmain()

(

GraphG(10);

cout?"inputnodesnumber:"?endl;

intn;

cin?n;

cout?"inputM?n?"nodes:"?endl;

intnode;

for(inti=0;i<=n-l;i++)

cin?node;

G.insertNode(node);

)

cout?ndone!u?endl;

cout?"inputedgesnumber:"?endl;

inte;

cin?e;

cout?ninput"?e?"edges:xyw"?endl;

intx,y,w;

for(intj=O;j<=e-1;j++)

{cin?x?y?w;

G.isertEdge(x,y,w);

)

cout?nGraphicdone!n?endl;

cout?ninputthestartnode(int):n?endl;

cin?node;

cout?nDFS:",?endl;

GDFS(node);

cout?endl;

cout?,'BFS:',?endl;

G.BFS(node);

cout?endl;

system("pausen);

return0;

)

鄰接表實(shí)現(xiàn)：

#include<iostream>

usingnamespacestd;

#defineMAXSIZE30

typedefstructSidetable

(

intDataPosition;

intWeight;

Sidetable*Next;

}Side_Table;

typedefstructVertextable

charData;

Sidetable*Size_Headptr;

}Vertex_Table;

classMap

(

private:

intVisited[MAXSIZE];

intNums;

Vertex_TableDataArry[MAXSIZE];

public:

Map()

(

Nums=0;

for(inti=0;i<=MAXSIZE;i++)

(

DataArry[i].Data=>\0';

DataArry[i].Size_Headptr=NULL;

Visited[i]=0;

)

)

~Map()

(

Side_Table*p;

for(inti=1;i<=Nums;i++)

(

p=DataArry[i].Size_Headptr;

while(p)

(

DataArry[i].Size_Headptr=p->Next;

deletep;

p=DataArry[iJ.Size_Headptr;

voidSetData();

intRe_Nums(){returnNums;}

voidVisitedClear();

voidSet_Endgsrelationship();

intRe_Position(char);

voidDFS(int);

voidTheDFS();

voidBFS();

voidMap::VisitedClear()

for(inti=0;i<MAXSIZE;i++)

(

Visited[i]=0;

}

)

voidMap::SetData()

(

inti=1;

while(cin?DataArry[i].Data,DataArry[i].Data!='.')

(

i++；

Nums++;

}

)

intMap::Re_Posilion(charch)

(

inti=1;

while(i<=Nums)

{

if(DataArry[i].Data==ch)break;

i++；

)

returni;

)

voidMap::DFS(inti)

(

Side_Table*p;

cout?DataArry[i].Data?MH;

Visited[i]=1;

p=DataArryli].Size_Headptr;

while(p!=NULL)

(

if(Visited[p->DataPosition]==0)

DFS(p->DataPosition);

p=p->Next;

}

)

voidMap::TheDFS(){DFS(l);}

voidMap::Set_Endgsrelationship()

(

intposl,pos2,weight;

charchl,ch2;

Side_Table*p;

while(cin?chl?ch2?weight,ch1!=&&ch2!=

(

posl=Re_Position(chl);

pos2=Re_Position(ch2);

p=newSide_Table();

p->DataPosition=pos2;

p->Weight=weight;

p->Next=DataArry[posl].Size_Headptr;

DataArry[posl].Size_Headptr=p;

p=newSide_Table();

p->DataPosition=pos1;

p->Weight=weight;

p->Next=DataArry[pos2].Size_Headptr;

DataArry[pos2].Size_Headptr=p;

)

)

voidMap::BFS()

(

VisitedClear();

inti,queue[MAXSIZE],front=0,rear=0;

Side_Table*p;

cout?DataArry[l].Data?nu;

Visited[1]=1;

rear=rear+1;

queue[rear]=1;

while(front!=rear)

(

front=front+1;

i=queue[front];

p=DataArry[i].Size_Headptr;

while(p!=NULL)

{

if(Visited[p->DataPosition]==0)

(

cout?DataArry[p->DataPosition].Data?n

Visited[p->DataPosition]=1;

rear=rear+1;

queuefrear]=p->DataPosition;

)

p=p->Next;

intmain()

(

Mapmapl;

cout?”請(qǐng)輸入頂點(diǎn)數(shù)據(jù)(以？結(jié)束輸入):"；

mapl.SelData();

cout<〈”請(qǐng)輸入頂點(diǎn)關(guān)系及權(quán)值(以..結(jié)束輸入):yvendl;

mapl.Set_Endgsrelationship();

coutvv”深度優(yōu)先遍歷為:";

mapl.TheDFS();

cout?endl;

cout?"廣度優(yōu)先遍歷為:";

mapl.BFS();

cout?endl;

system(npause");

return0;

七、基于深度優(yōu)先搜索算法，寫(xiě)出求無(wú)向圖所有連通分量的算法。

提示：對(duì)于無(wú)向圖，從任一個(gè)頂點(diǎn)出發(fā)進(jìn)行DFS遍歷，當(dāng)本次遍歷完成后，其所訪問(wèn)的結(jié)

點(diǎn)構(gòu)成一個(gè)連通分量；如果還存在沒(méi)有訪問(wèn)過(guò)的結(jié)點(diǎn)，則從中任一個(gè)結(jié)點(diǎn)出發(fā)進(jìn)行DFS遍

歷直到所有結(jié)點(diǎn)都被訪問(wèn)。每一次調(diào)用DFS后都得到此非連通圖的一個(gè)連通分量,

調(diào)用DFS的次數(shù)就是連通分量的個(gè)數(shù)。

#include<stdlib.h>

#include<stdio.h>

structnode/*圖頂點(diǎn)結(jié)構(gòu)定義*/

(

intvertex;/*頂點(diǎn)數(shù)據(jù)信息*/

structnode*nextnode;/*指下一頂點(diǎn)的指標(biāo)*/

)；

typedefstructnode*graph;/*圖形的結(jié)構(gòu)新型態(tài)*/

structnodehead[9];/*圖形頂點(diǎn)數(shù)組*/

intvisited[9];/*遍歷標(biāo)記數(shù)組*/

intid[9];/*標(biāo)記連通分量的編號(hào)*/

intcount=0;/*連通分量編號(hào)*/

voidcreategraph(intnode[201[2],intnum)/*nuin指的是圖的邊數(shù)*/

graphnewnode;/*指向新節(jié)點(diǎn)的指針定義*/

graphptr;

intfrom;/*邊的起點(diǎn)*/

intto;/*邊的終點(diǎn)*/

inti;

for(i=0;i<num;i++)/*讀取邊線信息，插入鄰接表*/

from=node[i][0];/*邊線的起點(diǎn)*/