數(shù)據(jù)結構與算法分析

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

四川高校軟件學院同學試驗報告

試驗名稱：數(shù)據(jù)結構與算法分析

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

試驗報告

班級__姓名學號

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

3.嫻熟掌控圖的鄰接表存儲結構以及拓撲排序的基本思想。4.上機調(diào)試程序,掌控查錯、排錯使程序能正確運行。三、試驗的環(huán)境:1.硬件環(huán)境:2.軟件環(huán)境:

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

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

〔3〕編輯軟件特點

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

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

四、算法描述:

深度優(yōu)先搜尋

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

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

廣度優(yōu)先搜尋

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

五、源程序清單:

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

//Usedbythemarkarray#defineUNVISITED0#defineVISITED1

//Graphabstractclass

classGraph{public:

//Returnthenumberofvertices

深度優(yōu)先搜尋和廣度優(yōu)先搜尋算法實現(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)先搜尋算法實現(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)先搜尋算法實現(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)先搜尋算法實現(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)先搜尋算法實現(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