數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之圖的遍歷和生成樹求解

##大學(xué)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

題目：圖的遍歷和生成樹求解

院（系）：計算機工程學(xué)院

學(xué)生姓名:_____________________

班級：學(xué)號:

起迄日期：2011

指導(dǎo)教師：______________________

指導(dǎo)教師評語：成績:

簽名:

年月日

2010—2011年度第2學(xué)期

一、需求分析

1.問題描述：

圖的遍歷和生成樹求解實現(xiàn)

圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅

有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼；在樹形結(jié)構(gòu)中，

數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多

個元素（及其孩子結(jié)點）相關(guān)但只能和上一層中一個元素（即雙親結(jié)點）相關(guān)；

而在圖形結(jié)構(gòu)中，節(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都

可能相關(guān)。

生成樹求解主要利用普利姆和克雷斯特算法求解最小生成樹，只有強連通圖

才有生成樹。

2.基本功能

1）先任意創(chuàng)建一個圖；

2）圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)

3)最小生成樹(兩個算法)的實現(xiàn)，求連通分量的實現(xiàn)

4)要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲實現(xiàn)

3.輸入輸出

輸入數(shù)據(jù)類型為整型和字符型，輸出為整型和字符

二、概要設(shè)計

1.設(shè)計思路：

a.圖的鄰接矩陣存儲：根據(jù)所建無向圖的結(jié)點數(shù)n,建立n*n的矩陣，其中

元素全是無窮大(intjnax),再將邊的信息存到數(shù)組中。其中無權(quán)圖的邊用1

表示，無邊用0表示；有全圖的邊為權(quán)值表示，無邊用8表示。

b.圖的鄰接表存儲：將信息通過鄰接矩陣轉(zhuǎn)換到鄰接表中，即將鄰接矩陣的

每一行都轉(zhuǎn)成鏈表的形式將有邊的結(jié)點進行存儲。

c.圖的廣度優(yōu)先遍歷：假設(shè)從圖中的某個頂點v出發(fā)，在訪問了v之后依次

訪問v的各個未曾訪問過的鄰接點，然后再訪問此鄰接點的未被訪問的鄰接點，

并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直

至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中還有未被訪問的，

則另選未被訪問的重復(fù)以上步驟，是一個非遞歸過程。

d.圖的深度優(yōu)先遍歷：假設(shè)從圖中某頂點v出發(fā)，依依次訪問v的鄰接頂點,

然后再繼續(xù)訪問這個鄰接點的系一個鄰接點，如此重復(fù)，直至所有的點都被訪問，

這是個遞歸的過程。

e.圖的連通分量:這是對一個非強連通圖的遍歷，從多個結(jié)點出發(fā)進行搜索,

而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其連

通分量的頂點集。本程序利用的圖的深度優(yōu)先遍歷算法。

2.數(shù)據(jù)結(jié)構(gòu)設(shè)計：

ADTQueue{

數(shù)據(jù)對象:D={aJa(GElemSet,i=l,2,3...,n,n20}

數(shù)據(jù)關(guān)系：Rl={<ai-bai>|alba.ED,i=l,2,3,....,n}

基本操作：

InitQueue(&Q)

操作結(jié)果：構(gòu)造一個空隊列Q。

QueueEmpty(Q)

初始條件：Q為非空隊列。

操作結(jié)果：若Q為空隊列，則返回真，否則為假。

EnQueue(&Q,e)

初始條件：Q為非空隊列。

操作結(jié)果：插入元素e為Q的新的隊尾元素。

DeQueue(&Q,e)

初始條件：Q為非空隊列。

操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。

}ADTQueue

ADTGraph{

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。

數(shù)據(jù)關(guān)系R：

R={VR}

VR={〈v,W＞IV,wev且P(v,w),〈V,W〉表示從V到w的弧，

謂詞P(v.w)定義了?。紇,w＞的意義或信息}

基本操作P:

CreatGraph(&G,V,VR);

初始條件：V是圖的頂點集，VR是圖中弧的集合。

操作結(jié)果：按V和VR的定義構(gòu)造圖G。

BFSTraverse(G,visit());

初始條件：圖G存在，Visit是定點的應(yīng)用函數(shù)。

操作結(jié)果：對圖進行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點

調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失

敗，則操作失敗。

DFSTraverse(G,visit());

初始條件：圖G存在，Visit是定點的應(yīng)用函數(shù)。

操作結(jié)果：對圖進行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點

調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失

敗，則操作失敗。

DFStra_fen(G)

初始條件：圖G存在，存在圖的深度優(yōu)先遍歷算法。

操作結(jié)果：從多個頂點對圖進行深度優(yōu)先遍歷，得到連通分量。

}ADTGraph;

3.軟件結(jié)構(gòu)設(shè)計:

creatMGraph_L(G)int

creatadj(gra,G)int

Ijjzprint(G)void

adjprint(gra,G)void

BFSTraverse(gra)void

DFStra(gra)int

DFSTraverse_fen(gra)int

MiniSpanTree_PRIM(g,G.vexnum)int

MiniSpanTREE_KRUSCAL(G,gra)void

三、詳細設(shè)計

1.定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實現(xiàn)；

鄰接矩陣定義：

typedefstructArcCell

(

VRTypeadj;〃VRType是頂點關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否;

對帶權(quán)圖，則為權(quán)值類型

InfoType*info;〃該弧相關(guān)信息的指針

}ArcCell,AdjMatrix[max][max];

typedefstruct

(

VertexTypevexs[max];〃頂點向量

AdjMatrixarcs;〃鄰接矩陣

intvexnum,arcnum;〃圖的當前頂點數(shù)和弧數(shù)

}MGraph_L;

鄰接表的定義：

typedefstructArcNode〃弧結(jié)點

{

intadjvex;〃該弧指向的頂點的位置

structArcNode*nextarc;〃指向下一條弧的指針

InfoType*info;〃該弧相關(guān)信息的指針

}ArcNode;

typedefstructVNode〃鄰接鏈表頂點頭接點

(

VertexTypedata;〃頂點信息

ArcNode*firstarc;〃指向第一條依附該頂點的弧的指針

}VNode,AdjList;

typedefstruct〃圖的定義

AdjListvertices[max];

intvexnum,arcnum;〃圖的當前頂點數(shù)和弧數(shù)

}ALGraph;

隊列定義：

typedefstructQNode

(

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct

(

QueuePtrfront;〃隊頭指針

QueuePtrrear;〃隊尾指針

}LinkQueue;

2.主函數(shù)和其他函數(shù)的偽碼算法；

主函數(shù)：

intmain()

ints;

chary=，y，;

cout<<〃|innQQQQnQQnQQQQnQQ菜單QQQQQQnQQ

QQQQQQaaal|z，?endl;

cout<<z，||------------------------【0、創(chuàng)建一個無向圖

-----------------------------||〃<<endl;

cout<m------------------------11、顯示該圖的鄰接矩陣

,,

-------------------------1|?endi；

cout<r||-------------------------【2、顯示該圖的鄰接表

---------------------------1]〃<<endl;

cout?，zH------------------------13、廣度優(yōu)先遍歷

-------------------------------1|〃<<endl;

cout?"||-------------------------【4、深度優(yōu)先遍歷

-------------------------------||〃<<endl;

cout<</z||------------------------[5、最小生成樹MiniSpanTree_PRIM

算法------------1|z，?endl;

cout?/，||------------------------【6、最小生成樹

MiniSpanTree_KRUSCAL算法---------1|"Gendl;

cou^CH------------------------17、連通分量

-----------------------------------||“<<endl;

COUKCIlanaQaaaaanoaaaananaQaaaaQaaa

□□□□□□naali〃?endi；

while(y==，y')

(

cout<<”請選擇菜單："<<endl;

cin?s;

if(s==0)

(

++o;

if(o==2)

(

n=0;

1=0;

o=0;

1

}

switch(s)

(

case0:cout<X〃創(chuàng)建一個無向圖：〃<Xendl;

MGraph_LG;

creatMGraph_L(G);

ALGraphgra;

creatadj(gra,G);

break;

case1:cout<〈〃鄰接矩陣顯示如下：〃《endl;

1jjzprint(G);

break;

case2:

cout<〈〃鄰接表顯示如下：〃<<endl;

adjprint(gra,G);

break;

case3:

cout?〃廣度優(yōu)先遍歷：〃；

BFSTraverse(gra);

cout<<endl;

break;

case4:

cout<<〃深度優(yōu)先遍歷：〃；

DFStra(gra);

cout<<endl;

break;

case5:

if(n=0){cout<〈〃無權(quán)圖沒有最小生成樹〃;break;}

elseif(l〉O){cout<〈〃若該圖為非強連通圖(含有多個連通分量)時,

最小生成樹不存在〃<<endl;break;}

else

(

inti,g[max][max];

for(i=0;i!=G.vexnum;++i)

for(intj=0;j!=G.vexnum;++j)

g[i+l]Lj+1]=G.arcsEi][j].adj;

cout<<〃普利姆算法:，，<<endl;

MiniSpanTree_PRIM(g,G.vexnum);

break;

)

case6:if(n=0){cout<〈〃無權(quán)圖沒有最小生成樹〃；break;}

elseif(l>0){cout?〃該圖為非強連通圖(含有多個連通分量)，最

小生成樹不存在〃<<endl;break;}

else

(

cout<<〃克魯斯卡爾算法：〃〈Vendl;

MiniSpanTREE_KRUSCAL(G,gra);

break;

)

case7:cout<<〃連通分量：〃<<endl;

DFSTraverse_fen(gra);

break;

cout?endl<<〃是否繼續(xù)?y/n:〃；

cin?y;

if(y==，n)

break;

}

return0;

)

鄰接矩陣存儲：

intcreatMGraph_L(MGraph_L&G)〃創(chuàng)建圖用鄰接矩陣表示

(

charvl,v2;

inti,j,w;

cout?！ㄕ堓斎腠旤c和弧的個數(shù)〃<<endl;

cin>>G.vexnum?G.arcnum;

cout<X〃輸入各個頂點〃<Xendl;

for(i=0;i<G.vexnum;++i)

(

cin>>G.vexs[i];

)

for(i=0;i<G.vexnum;++i)

for(j=0;j<G.vexnum;++j)

(

G.arcs[i][j]?adj=int_max;

G.arcs[i][j].info=NULL;

)

for(intk=0;k<G.arcnum;++k)

(

cout<〈〃輸入一條邊依附的頂點和權(quán)〃〈〈endl;

cin>>vl>>v2>>w;〃輸入一條邊依附的兩點及權(quán)值

i=localvex(G,vl);〃確定頂點VI和V2在圖中的位置

j=localvex(G,v2);

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=w;

)

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj<int_max)n+=l;

)

if(n>=l)cout<〈〃這是一個有權(quán)圖〃<<endl;

elsecout<<〃這是一個無權(quán)圖〃<Xendl;

cout*〃圖G鄰接矩陣創(chuàng)建成功！〃<<endl;

returnG.vexnum;

)

鄰接矩陣的輸出：

void1jjzprint(MGraph_LG)〃鄰接矩陣的輸出

(

inti,j;

if(n==0)

(

for(i=0;i!=G.vexnum;++i)

(

for(j=0;j!=G.vexnum;++j)

(

if(G.arcs[i][j].adj==int_max){cout<<〃0〃<<〃〃;}

else{cout<<G.arcs[i][j].adj<<z，〃;}

}

cout<<endl;

)

}

else

(

for(i=0;i!=G.vexnum;++i)

(

for(j=0;j!=G.vexnum;++j)

(

if(G.arcs[i][j].adj==int_max){cout<<〃8〃<<〃〃；}

else{cout<<G.arcs[i][j].adj<<〃〃;}

)

cout?endl;

用鄰接表存儲圖：

intcreatadj(ALGraph&gra,MGraphLG)〃用鄰接表存儲圖

(

inti=0,j=0;

ArcNode*arc;//,*tem,*p;

for(i=0;i!=G.vexnum;++i)

(

gra.vertices[i].data=G.vexs[i];

gra.vertices[i].firstare=NULL;

)

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

(

if(G.arcs[i][j].adj!=int_max)

(

arc=(ArcNode*)malloc(sizeof(ArcNode));

arc->adjvex=j;

arc->nextarc=gra.vertices[i]?firstarc;

gra.vertices[i].firstarc=arc;

)

}

gra.vexnum=G.vexnum;

gra.arcnum=G.arcnum;

cout?〃圖G鄰接表創(chuàng)建成功！〃<<endl;

return1;

)

鄰接表輸出：

voidadjprint(ALGraphgra,MGraph_LG)//鄰接表輸出

(

inti;

for(i=0;i!=gra.vexnum;++i)

(

ArcNode*p;

cout?，，r?i?，，/，?G.vexs[i]?，，]，z;

p=gra.vertices[i]?firstarc;

while(p!=NULL)

cout?〃->〃<<〃[〃<<p->adjvex<<〃]〃;

p=p->nextarc;

}

cout?//->，，?，，End，z;

cout<<endl;

)

)

初始化隊列：

StatusInitQueue(LinkQueue&Q)〃初始化隊列

(

Q?front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)return0;〃存儲分配失敗

Q.front->next=NULL;

return1;

)

入隊：

StatusEnQueue(LinkQueue&Q,QElemTypee)〃入隊，插入元素e為Q的新的隊

尾元素

(

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)return0;〃存儲分配失敗

p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

return1;

)

出隊：

StatusDeQueue(LinkQueue&Q,QElemType&e)〃出隊，若隊列不空，則刪除Q

的隊頭元素，用e返回，并返回真，否則假

(

QueuePtrp;

if(Q.front==Q.rear)return0;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;

free(p);

return1;

)

判斷隊為空：

StatusQueueEmpty(LinkQueueQ)〃判斷隊為空

(

if(Q.front==Q.rear)return1;

return0;

)

廣度優(yōu)先遍歷：

voidBFSTraverse(ALGraphgra)

(

inti,e;

LinkQueueq;

for(i=0;i!=gra.vexnum;++i)visited[i]=0;

InitQueue(q);

for(i=0;i!=gra.vexnum;++i)

if(!visited[i])

(

visited[i]=l;

cout<<gra.vertices[i]?data;

EnQueue(q,i);

while(!QueueEmpty(q))

(

DeQueue(q,e);

for(we=firstadjvex(gra,gra.vertices?);we>=0;we=nextadjvex(gra,g

ra.vertices[e],we))

(

if(!visited[we])

(

visited[we]=l;

cout<<gra.vertices[we],data;

EnQueue(q,we);

)

深度優(yōu)先遍歷：

intDFS(ALGraphgra,inti)

(

visited[i]=l;

intwel;

cout<<gra.vertices[i]?data;

for(we=firstadjvex(gra,gra.vertices"]);we>=0;we=nextadjvex(gra,g

ra.vertices[i],we))

(

wel=we;

if(visited[we]-O)

DFS(gra,we);

we=wel;

)

return1;

)

intDFStra(ALGraphgra)

(

inti,j;

for(i=0;i!=gra.vexnum;++i)

(

visited[i]=O;

}

for(j=0;j!=gra.vexnum;++j)

(

if(visited[j]==0)DFS(gra,j);

)

return0;

)

連通分量：

intDFSTraverse_fen(ALGraphgra)

inti,j;

for(i=0;i!=gra.vexnum;++i)

visited[i]=O;

for(j=0;j!=gra.vexnum;++j)

(

if(visited[j]==O)

(

DFS(gra,j);

cout?endl;

1++；

}

)

return0;

)

3.主要函數(shù)的程序流程圖，實現(xiàn)設(shè)計中主程序和其他子模塊的算法，以流程圖

的形式表示。

圖的鄰接矩陣存儲圖的鄰接表存儲圖的廣度優(yōu)先遍歷

<■

開始

Intlowcost[max]

Prevex[max]

IntI,j,k,min

結(jié)束

圖的普利姆算法求最小生成樹

四、調(diào)試分析

1.實際完成的情況說明；

a.先任意創(chuàng)建一個圖；

b.圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)

c.最小生成樹（兩個算法）的實現(xiàn)，求連通分量的實現(xiàn)

d.要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲實現(xiàn)

支持的數(shù)據(jù)類型：整型和字符型

2.程序的性能分析，包括時空分析；

本程序的圖的遍歷是以鄰接表做圖的存儲結(jié)構(gòu)，其時間復(fù)雜度為0（n+e）。

3.上機過程中出現(xiàn)的問題及其解決方案；

a.程序開始對無權(quán)圖和有權(quán)圖的鄰接矩陣的輸出時，無邊都用的10000（無

窮大int_max）表示的，這種表示和我們習(xí)慣上的0與8的表示有差異。所以在

程序中定義了全局變量n（初值為0）,來判斷創(chuàng)建的無向圖是有權(quán)圖還是無權(quán)圖,

n>0為有權(quán)圖，此時輸出的時候用8代替10000；n=0為無權(quán)圖，此時輸出的時

候用0代替10000.

b.程序中有的功能對某些圖是不適用的，比如無權(quán)圖沒有最小生成樹，非強

連通圖沒有最小生成樹等。所以在程序中又新增了全局變量L1>0時表示為非強

連通圖，則在求最小生成樹時報錯。

C.當程序先創(chuàng)建一個有權(quán)圖后，n的值會大于1,第二次創(chuàng)無權(quán)圖時也會被

程序認為有權(quán)圖，所以在程序中在定義全局變量。（初值為0）,來判斷創(chuàng)建了幾

次圖，當?shù)诙蝿?chuàng)建圖，即。=2時，所有全局變量在開始全歸零。

4.程序中可以改進的地方說明；

當建立一個圖時先得求其連通分量，從而確定全局變量1的值，從而才能判斷該

圖是否有最小生成樹。

五、測試結(jié)果

創(chuàng)建一個無權(quán)圖:

c:"E:\VC6\lyProjects\^^c4\Debug\test.exe

-------------------------日：顯示該由的穗廨---------------------------

-------------------------【2、顯示該圖的鄰接表-----------------------------

---------------------------------------------13、廣度優(yōu)先遍歷---------------------------------

---------------------------------------------14、深度機先遍歷---------------------------------

---------------------------------------------15、桂箍分量-------------------------------------

---------------------------------------------16、曩個生成忡iniSpanTreeJPRIM算法--------------

-------------------------【7、最小生成樹MiniSpanTree_KRUSCAL算法-----------

在求最小生成樹前請先求連通分量?

請選擇菜單：

創(chuàng)建一個無向圖：

請輸入頂點和弧的個數(shù)

全i入各個頂點

abcdefg

輸入一條邊依附的頂點和權(quán)

ab1

輸入一條邊依附的頂點和權(quán)

ac1

輸入一條邊依附的頂點和權(quán)

bd1

輸入一條邊依附的頂點和權(quán)

be1

輸入一條邊依附的頂點和權(quán)

de1

輸入一條邊依附的頂點和權(quán)

fa1

逡是一個無權(quán)圖

圖G鄰黃矩陣創(chuàng)建成功！

圖G鄰鬟表創(chuàng)建成功！

是否繼續(xù)？i1/n：

03否繼續(xù)？y/n：y

青選擇菜單:

，ji讖續(xù)？y/n：y

郵接矩陣顯示如下:鄰接表顯示如下請選擇菜單：

[0,aJ->[2J->Cl]->End

31100003

[l,b]->[4]->[3J->[0]->End

L00100L度優(yōu)先遍歷：acbedfg

[2,c]->[0]->End

L000000

[3,d]->E4]->riJ->End

3100100是否繼續(xù)？y/n：y

[4,e]->[3]->Ll]->End

3101000請選擇菜單：

L5,f]->[6]->End

3000001

彳000010[6,g]->[5]->End深度優(yōu)先遍歷：acbedfg

是否繼續(xù)？“n：

創(chuàng)建一個費強連通的有權(quán)圖:

歆,E:\VC6\IyProjects\^4\：

習(xí)"E:\VC6\?yPrejects'課設(shè)

請輸入頂點和弧的個數(shù)

55

輸入各個頂點

abede

輸入一條邊依附的頂點和權(quán)

ab2

輸入一條邊依附的頂點和權(quán)

ac3

輸入一條邊依附的頂點和權(quán)

bd1

輸入一條邊依附的頂點和權(quán)

he3

輸入一條邊依附的頂點和權(quán)

de4

這是一個有權(quán)圖

圖G鄰樓矩陣創(chuàng)建成功！

圖G鄰馨表創(chuàng)建成功！

是否繼續(xù)？y/n：y

F選擇菜單：

連通分量：

acbed

是否繼續(xù)？y/n：y

通選擇菜單：

署利拇算法：

<0,1>2

<0,2>3

<1,4>3

是否繼續(xù)？y/n：y

事選擇菜單：

■魯斯卡爾算法:

<0,1>2

<0,2>3

<1,4〉3

是否繼續(xù)？y/n：

六、用戶手冊

c'"E:\￥C6\?yProjects\課設(shè)4\Debug\test.exe"BISE

I

!-------------------------加、創(chuàng)建一無向圖-------------------------------

1---------------------------------------------------0顯示該圖的鄰言矩陣---------------------------：i

1---------------------------------------------------12、顯示該圖的鄰馨表-----------------------------1

!-------------------------【3、匚哪先瀛歷---------------------------------!

?14、深度優(yōu)先遍歷?

；西、他通分里：!

1---------------------------------------------------【6、蜃小生成科MiniSpanTreeJPRIM算法--------------1

最小生,成樹算法-----------

1i-u----a---n----n----u----u----u----n----Q-----Q------u----u----u[7u,nunuunMninaiSQpannTrneeu_KQRUnSCnAuLuunuriuni1

在求最小生成樹前請先求連通分量，

哥選擇菜單：

a.先選0創(chuàng)建一個圖。b.選擇y繼續(xù)操作。c.按照菜單編碼選擇操作。

七、體會與自我評價

在做這個程序的時候你首先必須知道圖的一些概念，圖是一種較線性表和樹

更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個數(shù)據(jù)元素

只有一個直接前驅(qū)和一個直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層

次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素（及其孩子結(jié)點）相

關(guān)但只能和上一層中一個元素（即雙親結(jié)點）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點之間

的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。

當我們拿到一個圖時，我們對該圖的遍歷就要有一些方法，所以有了深度優(yōu)

先遍歷和廣度優(yōu)先遍歷，我們要明白這兩種遍歷是怎么實現(xiàn)的，然后根據(jù)我們?nèi)?/p>

腦中的方法把它寫成電腦算法。

對一個圖我們還定義了連通分量，所以將圖存到電腦中時，我們對連通分量

得有個算法。

求圖的最小生成樹有兩種算法，普利姆是從結(jié)點出發(fā)尋找權(quán)最小的邊，知道

所有結(jié)點都練通了；而克魯斯卡爾算法則是從邊出發(fā)，尋找使圖連通的權(quán)值最小

邊的方法。

算法的實現(xiàn)從人腦到電腦的轉(zhuǎn)變是比較復(fù)雜的一件事，要求做到具體到實現(xiàn)

該方法的每一個步驟，然后再將每一個步驟通過代碼實現(xiàn)。

這要求我們要明確各個數(shù)據(jù)元素和個元素之間的關(guān)系，然后才能明確使用算

法去調(diào)用這些數(shù)據(jù)。

通過本次的課程設(shè)計，我對數(shù)據(jù)結(jié)構(gòu)有了一定的認識，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)

據(jù)，數(shù)據(jù)關(guān)系，及對其操作的方法。但同時也發(fā)現(xiàn)在自己有很多的不足，在使用

語言和如何精煉語言需要進行更多的訓(xùn)練。

源代碼:

#include<iostream>

#include<malloc.h>

usingnamespacestd;

#defineint_max10000〃最大值

staticintn=0;〃全局變量，判斷有權(quán)圖和無權(quán)圖

staticinto=0;〃全局變量，清除BUG

staticini1=0;〃全局變量，清除BUG

#defineinf9999〃最小值的最大值

#definemax20〃最大頂點個數(shù)

typedefintVRType,QElemType,Status;

typedefcharInfoType,VertexType;

//miiiiiiiiiiiwiiiii鄰接矩陣iiiiiuiiiiiiiuiiiiiiiiiiw

//------------------鄰接矩陣定義------------------

typedefstructArcCell

(

VRTypeadj;//VRType是頂點關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖,

則為權(quán)值類型

InfoType求info;〃該弧相關(guān)信息的指針

}ArcCell,AdjMatrix[max][max];

typedefstruct

(

VertexTypevexs|max];〃頂點向量

AdjMatrixarcs;〃鄰接矩陣

intvexnum,arcnum;〃圖的當前頂點數(shù)和弧數(shù)

}MGraph_L;

//--------------------------------------------------------------------

intlocalvex(MGraph_LG,charv)〃返回V的位置

(

inti=0;

while(G.vexs[i]!=v)++i;

returni;

)

intcreatMGraph_L(MGraph_L&G)//創(chuàng)建圖用鄰接矩陣表示

(

charvl,v2;

inti,j,w;

coutvv"請輸入頂點和弧的個數(shù)"v<endl;

cin?G.vexnum?G.arcnum;

coutvv"輸入各個頂點"vvendl;

for(i=0;i<Gvexnum;++i)

(

cin?G.vexs[i];

fbr(i=0;i<Gvexnum;4-+i)

for(j=0;j<Gvexnum;++j)

(

Garcs[i][j].adj=int_max;

Garcs[i][j].info=NULL;

)

for(intk=O;k<G.arcnum;++k)

(

cout?"輸入一條邊依附的頂點和權(quán)"vvendl;

cin?v1?v2?w;〃輸入一條邊依附的兩點及權(quán)值

i二k)calvex(G,vl);〃確定頂點VI和V2在圖中的位置

j=localvex(G,v2);

Garcs[i][j].adj=w;

Garcs[j][i].adj=w;

)

for(i=0;i!=Gvexnum;+4-i)

for(j=0;j!=Gvexnum;++j)

(

if(G.arcs[i][j].adj!=l&&G.arcs[i][j].adj<int_max)n+=l;

)

if(n>=l)cout?”這是一個有權(quán)圖”《endl;

elsecout<<"這是一個無權(quán)圖"<<endl;

cout<<”圖G鄰接矩陣創(chuàng)建成功！"《endl;

returnGvexnum;

)

voidljjzprint(MGraph_LG)//鄰接矩陣的輸出

(

inti,j;

if(n==0)

(

fbr(i=O;i!=Gvexnum;++i)

(

for(j=0;j!=Gvexnum;++j)

(

if(G.arcs[i][j].adj==int_max){cout?nO"?nn;}

else{cout?G.arcs[i]fj].adj?,'

}

cout?endl;

)

)

else

{

fbr(i=O;i!=Gvexnum;++i)

for(j=0;j!=Gvexnum;++j)

if(Garcs[i][j].adj-int_max)(cout?"°°"?"";}

else{cout?Garcs[i][j].adj?"";}

)

cout?endl;

)

)

I

//llllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

//-----------------鄰接表的定義----------------

lypedefstructArcNode//弧結(jié)點

(

intadjvex;〃該弧指向的頂點的位置

structArcNode*nextarc;〃指向下一條弧的指針

InfoType*info;〃該弧相關(guān)信息的指針

}ArcNode;

typedefstructVNode〃鄰接鏈表頂點頭接點

(

VertexTypedata;//頂點信息

ArcNode*firstarc;〃指向第一條依附該頂點的弧的指針

(VNode,AdjList;

typedefstruct//圖的定義

(

AdjListvertices!max];

intvexnum,arcnum;〃圖的當前頂點數(shù)和弧數(shù)

}ALGraph;

intcreatadj(ALGraph&gra,MGraph_LG)〃用鄰接表存儲圖

(

inti=0,j=0;

ArcNode*arc;

for(i=0;i!=G.vexnum;++i)

{

gra.vertices[i].data=G.vexs[i];

gra.vertices[i].firstarc=NULL;

)

fdr(i=O;i!=Gvexnum;++i)

for(j=0;j!=G.vexnum;+4j)

(

if(Garcs[i][j].adj!=int_max)

(

arc=(ArcNode*)malloc(sizeof(ArcNode));

arc->adjvex=j;

arc->nextarc=gra.vertices[i].firstarc;

gra.vertices[i].firstarc=arc;

)

gra.vexnum=G.vexnum;

gra.arcnum=G.arcnum;

cout?nSG鄰接表創(chuàng)建成功!n?endl;

return1;

)

voidadjprint(ALGraphgra,MGraph_LG)〃鄰接表輸出

(

inti;

fbr(i=O;i!=gra.vexnum;++i)

(

ArcNode*p;

coutv<”["vvivv",”<vGvexs[i]<v"「；

p=gra.vertices[i].firstarc;

while(p!=NULL)

(

coutvv”->“v<"[“<vp->adjvex<<”『；

p=p->nextarc;

)

cout?',->',?uEnd,';

cout?endl;

)

)

//IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIN

//----------------隊列定義-----------------

typedefstructQNode

(

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct

(

QueuePtrfront;〃隊頭指針

QueuePtrrear;//隊尾指針

(LinkQueue;

//------------------------------------------------------------

StatusInitQueue(LinkQueue&Q)〃初始化隊列

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)retum0;〃存儲分配失敗

Q.front->next=NULL;

return1;

)

StatusEnQueue(LinkQueue&Q,QElemTypee)〃入隊，插入元素e為Q的新的隊尾元素

(

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)return0;//存儲分配失敗

p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

return1;

}

StatusDeQueue(LinkQueue&Q,QElemType&e)〃出隊，若隊列不空，則刪除Q的隊頭元素,

用e返回，并返回真，否則假

(

QueuePtrp;

if(Q.front==Q.rear)return0;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;

free(p);

return1;

)

StatusQueueEmpty(LinkQueueQ)〃判斷隊為空

(

if(Q.front==Q.rear)return1;

return0;

)

//-------------------圖的遍歷-------------------

intvisited|max];〃訪問標記

intwe;

intfirstadjvex(ALGraphgra,VNodev)〃返回依附頂點V的第一個點

〃即以V為尾的第一個結(jié)點

(

if(v.firstarc!=NULL)returnv.firstarc->adjvex;

)

intnextadjvex(ALGraphgra,VNodev,intw)〃返回依附頂點V的相對于W的下一個頂點

ArcNode*p;

p=v.firstarc;

while(p!=NULL&&p->adjvex!=w)

p=p->nextarc;

)

if(p->adjvex==w&&p->nextarc!=NULL)

(

p=p->nextarc;

returnp->adjvex;

)

if(p->adjvex==w&&p->nextarc==NULL)

return-10;

)

//-------------------廣度優(yōu)先遍歷-------------------

voidBFSTraverse(ALGr叩hgra)

(

inti,e;

LinkQueueq;

fbr(i=O;i!=gra.vexnum;++i)visited[i]=0;

InitQueue(q);

for(i=O;i!=gra.vexnum;++i)

if(!visitedfi])

(

visited[i]=l;

cout?gra.vertices[i].data;

EnQueue(q,i)；

while(!QueueEmpty(q))

(

DeQueue(q,e);

fbr(we=firstadjvex(gra,gra.vertices[e]);we>=O;we=nextadjvex(gra,gra.vertices[e],we))

(

if(!visited[we])

(

visited[we]=l;

cout?gra.vertices[we].data;

EnQueue(q,we);

)

)

)

)

)

//----------------------深度優(yōu)先遍歷----------------------

intDFS(ALGraphgra,inti)

visited[i]=l;

intwel;

cout?gra.vertices[i].data;

for(we=firstadjvex(gra,gra.vertices[i]);we>=O;we=nextadjvex(gra,gra.vertices[i],we))

(

wel=we;

if(visited[we]==O)

DFS(gra,we);

we=wel;

)

return1;

)

intDFStra(ALGraphgra)

(

inti,j;

fbr(i=O;i!=gra.vexnum;++i)

(

visited[i]=O;

)

fbr(j=O;j!=gra.vexnum;++j)

(

if(visited|j]==O)DFS(gra,j);

)

return0;

)

//-------------------求連通分量...............——

intDFSTraverse_fen(ALGraphgra)

(

inti,j;

for(i=0;i!=gra.vexnum;++i)

visited[i]=0;

for(j=0;j!=gra.vexnum;++j)

(

if(visited[jl==0)

{

DFS(gra,j);

coul?endl;

1++；

)

)

return0;

)

//--------------------最小生成樹的普利姆算法--------------------

typedefstruct

intadjvex;

intlowcost;

Jclosedge;

intMiniSpanTree_PRIM(intg[][max],intn)

(

intlowcost[max],prevex[max];//lowcost口存儲當前集合分別到剩余結(jié)點的最小權(quán)值

//prevex口存儲最短路徑的前一個結(jié)點

inti,j,k,min;

for(i=2;i<=n;i++)//n個頂點，n?l條邊

(

k)wcost[i]=g[l][i];//初始化

prevex[i]=l;//頂點未加入到最小生成樹中

)

lowcost[l]=0;〃標志頂點1加入U集合

for(i=2;iv=n;i++)〃形成n-1條邊的生成樹

(

min=inf;

k=0;

for(j=2;j<=n;j++)//尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊

if((lowcost[j]<min)&&(lowcost[j]!=0))

(

min=lowcost|j];

k=j；

)

cout?,'(',?prevex[k]-1?",M?k-1?,,),'?min;

lowcosl[k]=0;//頂點k加入U

for(j=2;jv=n;j++)〃修改由頂點k到其他頂點邊的權(quán)值

if(g[k][j]<lowcost[j])

(

lowcost[j]=g[k][j];

prevex|j]=k;

)

cout?endl;

}

return0;

}

//-----------------最小生成樹的克魯斯卡爾算法-------------------

intacrvisitedfmax];〃克魯斯卡爾弧標記數(shù)組

intfind(intacrvisited[],intf)

(

while(acrvisited[f]>O)f=acrvisited[f];

returnf;

typedefstructacr

intpre;〃弧的一結(jié)點

intbak;〃弧另一結(jié)點

intweight;〃弧的權(quán)

}edg;

voidMiniSpanTREE_KRUSCAL(MGraph_LQALGraphgra)

(

edgedgs[max];

inti,j,k=O;

for(i=O;i!=Gvexnum;++i)

for(j=i;j!=G.vexnum;++j)

(