数据结构与算法分析

第第页数据结构与算法分析深度优先搜寻和广度优先搜寻算法实现

四川高校软件学院同学试验报告

试验名称：数据结构与算法分析

深度优先搜寻和广度优先搜寻算法实现

试验报告

班级__姓名学号

一、试验号题目:深度优先搜寻和广度优先搜寻算法实现二、试验的目的和要求:1.采纳C++实现;2.娴熟掌控图的应用;

3.娴熟掌控图的邻接表存储结构以及拓扑排序的基本思想。4.上机调试程序,掌控查错、排错使程序能正确运行。三、试验的环境:1.硬件环境:2.软件环境:

〔1〕操作系统windows*PSP2。〔2〕编译系统Mingw322.95

C-Free开发工具:BorlandC++Builder6.0C-Free中运用的编译系统:Mingw322.95C-Free中运用的调试系统:GDB5.2.1C-Free中运用的VCL组件:SynEdit1.1

〔3〕编辑软件特点

运用c-Free自带的编辑软件，C-Free的智能输入功能能够大大提高你的代码编写速度，它能够

记住你已经输入的全部标识符、关键字，下一次输入标识符时，你不需要输入全部的标识符名称，输入一到二个字母，编辑窗口中会涌现你需要的标识符。

四、算法描述:

深度优先搜寻

深度优先搜寻类似于树的先根遍历。假设给定图G的初态是全部顶点均未访问过，在G中任选一顶点v为初始出发点，那么深度优先搜寻可定义如下：首先，访问出发点v，并将其标记为已访问过，然后依次从v的未被访问过的邻接点出发深度优先遍历图，直到图中全部和v有路径相通的顶点都被访问到；假设此时图中还有顶点未被访问，那么另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中全部顶点都被访问到为止。

深度优先搜寻和广度优先搜寻算法实现

广度优先搜寻

广度优先搜寻类似于树的按层次遍历的过程。从图中的某个顶点v0出发，在访问v0之后依次访问v0的全部未被访问过的邻接点w1,w2,w3,…wk，然后按这些邻接点被访问的先后次序依次从w1,w2,w3,…wk出发访问它们的邻接点，如此下去，直至图中全部已被访问的顶点的邻接点都被访问到。假设此时图中尚有顶点未被访问,那么另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中全部顶点都被访问到为止。

五、源程序清单:

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

//Usedbythemarkarray#defineUNVISITED0#defineVISITED1

//Graphabstractclass

classGraph{public:

//Returnthenumberofvertices

深度优先搜寻和广度优先搜寻算法实现

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

深度优先搜寻和广度优先搜寻算法实现

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;}};

深度优先搜寻和广度优先搜寻算法实现

//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

深度优先搜寻和广度优先搜寻算法实现

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

深度优先搜寻和广度优先搜寻算法实现

}

}

//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