數(shù)據(jù)結(jié)構(gòu)與算法分析

第第頁(yè)數(shù)據(jù)結(jié)構(gòu)與算法分析深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)

四川高校軟件學(xué)院同學(xué)試驗(yàn)報(bào)告

試驗(yàn)名稱：數(shù)據(jù)結(jié)構(gòu)與算法分析

深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)

試驗(yàn)報(bào)告

班級(jí)__姓名學(xué)號(hào)

一、試驗(yàn)號(hào)題目:深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)二、試驗(yàn)的目的和要求:1.采納C++實(shí)現(xiàn);2.嫻熟掌控圖的應(yīng)用;

3.嫻熟掌控圖的鄰接表存儲(chǔ)結(jié)構(gòu)以及拓?fù)渑判虻幕舅枷搿?.上機(jī)調(diào)試程序,掌控查錯(cuò)、排錯(cuò)使程序能正確運(yùn)行。三、試驗(yàn)的環(huán)境:1.硬件環(huán)境:2.軟件環(huán)境:

〔1〕操作系統(tǒng)windows*PSP2?！?〕編譯系統(tǒng)Mingw322.95

C-Free開(kāi)發(fā)工具:BorlandC++Builder6.0C-Free中運(yùn)用的編譯系統(tǒng):Mingw322.95C-Free中運(yùn)用的調(diào)試系統(tǒng):GDB5.2.1C-Free中運(yùn)用的VCL組件:SynEdit1.1

〔3〕編輯軟件特點(diǎn)

運(yùn)用c-Free自帶的編輯軟件，C-Free的智能輸入功能能夠大大提高你的代碼編寫(xiě)速度，它能夠

記住你已經(jīng)輸入的全部標(biāo)識(shí)符、關(guān)鍵字，下一次輸入標(biāo)識(shí)符時(shí)，你不需要輸入全部的標(biāo)識(shí)符名稱，輸入一到二個(gè)字母，編輯窗口中會(huì)涌現(xiàn)你需要的標(biāo)識(shí)符。

四、算法描述:

深度優(yōu)先搜尋

深度優(yōu)先搜尋類似于樹(shù)的先根遍歷。假設(shè)給定圖G的初態(tài)是全部頂點(diǎn)均未訪問(wèn)過(guò)，在G中任選一頂點(diǎn)v為初始出發(fā)點(diǎn)，那么深度優(yōu)先搜尋可定義如下：首先，訪問(wèn)出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問(wèn)過(guò)，然后依次從v的未被訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中全部和v有路徑相通的頂點(diǎn)都被訪問(wèn)到；假設(shè)此時(shí)圖中還有頂點(diǎn)未被訪問(wèn)，那么另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直到圖中全部頂點(diǎn)都被訪問(wèn)到為止。

深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)

廣度優(yōu)先搜尋

廣度優(yōu)先搜尋類似于樹(shù)的按層次遍歷的過(guò)程。從圖中的某個(gè)頂點(diǎn)v0出發(fā)，在訪問(wèn)v0之后依次訪問(wèn)v0的全部未被訪問(wèn)過(guò)的鄰接點(diǎn)w1,w2,w3,…wk，然后按這些鄰接點(diǎn)被訪問(wèn)的先后次序依次從w1,w2,w3,…wk出發(fā)訪問(wèn)它們的鄰接點(diǎn)，如此下去，直至圖中全部已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn),那么另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中全部頂點(diǎn)都被訪問(wèn)到為止。

五、源程序清單:

#includeiostream.h#includestdlib.h#includestdio.h#includeassert.h#includectype.h

//Usedbythemarkarray#defineUNVISITED0#defineVISITED1

//Graphabstractclass

classGraph{public:

//Returnthenumberofvertices

深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)

virtualintn()=0;

//Returnthecurrentnumberofedgesvirtualinte()=0;

//Returntheinde*ofthefirstneigborofgivenverte*virtualintfirst(int)=0;

//Returntheinde*ofthene*tneigborofgivenverte*virtualintne*t(int,int)=0;

//StoreanedgedefinedbytwoverticesandweightvirtualvoidsetEdge(int,int,int)=0;//Deleteedgedefinedbytwovertices

virtualvoiddelEdge(int,int)=0;

//Returnweightofedgeconnectingtwovertices//Return0ifnosuchedgee*istsvirtualintweight(int,int)=0;//Getmarkvalueforaverte*virtualintgetMark(int)=0;//Setmarkvalueforaverte*virtualvoidsetMark(int,int)=0;};

classEdge{

public:

intvecte*,weight;

Edge(){vecte*=-1;weight=-1;}

Edge(intv,intw){vecte*=v;weight=w;}};

classGraphm:publicGraph{//Implementadjacencymatri*private:

intnumVerte*,numEdge;//Storenumberofvertices,edgesint**matri*;//Pointertoadjacencymatri*int*mark;//Pointertomarkarray

public:

Graphm(intnumVert){//Makegraphw/numVertverticesinti,j;

numVerte*=numVert;numEdge=0;

mark=newint[numVert];//Initializemarkarrayfor(i=0;inumVerte*;i++)mark[i]=UNVISITED;

matri*=(int**)newint*[numVerte*];//Makematri*for(i=0;inumVerte*;i++)

matri*[i]=newint[numVerte*];

for(i=0;inumVerte*;i++)//Edgesstartw/0weight

深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)

for(intj=0;jnumVerte*;j++)matri*[i][j]=0;}

~Graphm(){//Destructor

delete[]mark;//Returndynamicallyallocatedmemoryfor(inti=0;inumVerte*;i++)delete[]matri*[i];delete[]matri*;}

intn(){returnnumVerte*;}//Numberofverticesinte(){returnnumEdge;}//Numberofedges

intfirst(intv){//Returnv'sfirstneighborinti;

for(i=0;inumVerte*;i++)if(matri*[v][i]!=0)returni;returni;//Returnnifnone}

intne*t(intv1,intv2){//Getv1'sneighborafterv2inti;

for(i=v2+1;inumVerte*;i++)if(matri*[v1][i]!=0)returni;returni;}

//Setedge(v1,v2)towgt

voidsetEdge(intv1,intv2,intwgt){Assert(wgt0,Illegalweightvalue);if(matri*[v1][v2]==0)numEdge++;matri*[v1][v2]=wgt;}

voiddelEdge(intv1,intv2){//Deleteedge(v1,v2)if(matri*[v1][v2]!=0)numEdge--;matri*[v1][v2]=0;}

intweight(intv1,intv2){returnmatri*[v1][v2];}intgetMark(intv){returnmark[v];}voidsetMark(intv,intval){mark[v]=val;}};

深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)

//Abstractqueueclass

templateclassElemclassQueue{public:

//Reinitializethequeue.Theuserisresponsiblefor//reclaimingthestorageusedbythestackelements.virtualvoidclear()=0;

//Placeanelementattherearofthequeue.Return//trueifsuccessful,falseifnot(ifqueueisfull).virtualboolenqueue(constElem)=0;

//Removetheelementatthefrontofthequeue.Return//trueifsuccesful,falseifqueueisempty.

//Theelementremovedisreturnedinthefirstparameter.virtualbooldequeue(Elem)=0;//RemoveElemfromfront//Returninfirstparameteracopyofthefrontelement.//Returntrueifsuccesful,falseifqueueisempty.virtualboolfrontValue(Elem)const=0;//Returnthenumberofelementsinthequeue.virtualintlength()const=0;};

//Array-basedqueueimplementation

templateclassElemclassAQueue:publicQueueElem{private:

intsize;//Ma*imumsizeofqueueintfront;//Inde*offrontelementintrear;//Inde*ofrearelement

Elem*listArray;//Arrayholdingqueueelementspublic:

AQueue(intsz=DefaultListSize){//Constructor

//Makelistarrayonepositionlargerforemptyslotsize=sz+1;

rear=0;front=1;listArray=newElem[size];}

~AQueue(){delete[]listArray;}//Destructorvoidclear(){front=rear;}boolenqueue(constElemit){

if(((rear+2)%size)==front)returnfalse;//Fullrear=(rear+1)%size;//CircularincrementlistArray[rear]=it;returntrue;

}

booldequeue(Elemit){

if(length()==0)returnfalse;//Empty

深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)

it=listArray[front];

front=(front+1)%size;//Circularincrementreturntrue;}

boolfrontValue(Elemit)const{if(length()==0)returnfalse;//Emptyit=listArray[front];returntrue;}

virtualintlength()const

{return((rear+size)-front+1)%size;}};

voidPreVisit(Graph*G,intv){

coutPreVisitverte*v\n;}

voidPostVisit(Graph*G,intv){

coutPostVisitverte*v\n;}

voidDFS(Graph*G,intv){//DepthfirstsearchPreVisit(G,v);//TakeappropriateactionG-setMark(v,VISITED);

for(intw=G-first(v);wG-n();w=G-ne*t(v,w))if(G-getMark(w)==UNVISITED)

DFS(G,w);PostVisit(G,v);//Takeappropriateaction}

voidBFS(Graph*G,intstart,Queueint*Q){intv,w;

Q-enqueue(start);//InitializeQG-setMark(start,VISITED);

while(Q-length()!=0){//ProcessallverticesonQQ-dequeue(v);

PreVisit(G,v);//Takeappropriateactionfor(w=G-first(v);wG-n();w=G-ne*t(v,w))if(G-getMark(w)==UNVISITED){G-setMark(w,VISITED);

Q-enqueue(w);}

PostVisit(G,v);//Takeappropriateaction

深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實(shí)現(xiàn)

}

}

//TestDepthFirstSearchandBreadthFirstSearchintmain(intargc,char*argv[]){

Graph*g=newGraphm(6);//Initializeagraphmgintchance;g-setEdge(0,2,1);g-setEdge(2,0,1);g-setEdge(2,1,1);g-setEdge(1,2,1);g-setEdge(1,5,1);g-setEdge(5,1,1);g-setEdge(2,5,1);g-setEdge(5,2,1);g-setEdge(3,5,1);g-setEdge(5,3,1);g-setEdg