图的广度优先遍历.doc

《图的广度优先遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四图的广度优先遍历一、实验目的（1）掌握图的逻辑结构。（2）掌握图的邻接表存储结构。（3）验证图的邻接表存储及其遍历操作实现。二、实验内容（1）建立一个有向图的邻接表存储结构。（2）对建立的有向图进行广度优先遍历。三、算法设计定义邻接表存储的有向图类ALGraph，定义边表结点和顶点表结点，设计构造函数ALGraph（）；析构函数，定义广度优先遍历图函数voidBFSTraverse（intv）；在私有成员中定义存放顶点表的数组，定义图的顶点数vertexNum，边数arcNum。四、主要代

2、码实现#includeusingnamespacestd;constintMaxSize=10;intvisited[MaxSize]={0};structArcNode{intadjvex;ArcNode*next;};templatestructVertexNode{DataTypevertex;ArcNode*firstedge;};templateclassALGraph{public:ALGraph(Dat

3、aTypea[],intn,inte);~ALGraph();voidBFSTraverse(intv);private:VertexNodeadjlist[MaxSize];intvertexNum,arcNum;};templateALGraph::ALGraph(DataTypea[],intn,inte){ArcNode*s;inti,j,k;vertexNum=n;arcNum=e;for(i=0;i

4、um;i++){adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL;}for(k=0;k>i>>j;s=newArcNode;s->adjvex=j;s->next=adjlist[i].firstedge;adjlist[i].firstedge=s;}}templateALGraph::~ALGraph(){ArcNod

5、e*p=NULL;for(inti=0;inext;deletep;p=adjlist[i].firstedge;}}}templatevoidALGraph::BFSTraverse(intv){intQ[MaxSize];intfront=-1,rear=-1;ArcNode*p=NULL

6、;cout<adjvex;if(visited[j]==0){cout<next;}}}intmain(){charch[]={'A','B','C','D

7、','E'};inti;ALGraphALG(ch,5,6);for(i=0;i