图的广度优先遍历

实验四图的广度优先遍历一、实验目的（1）掌握图的逻辑结构。（2）掌握图的邻接表存储结构。（3）验证图的邻接表存储及其遍历操作实现。二、实验内容（1）建立一个有向图的邻接表存储结构。（2）对建立的有向图进行广度优先遍历。三、算法设计定义邻接表存储的有向图类ALGraph，定义边表结点和顶点表结点，设计构造函数ALGraph（）；析构函数，定义广度优先遍历图函数voidBFSTraverse（intv）；在私有成员中定义存放顶点表的数组，定义图的顶点数vertexNum，边数arcNum。四、主要代码实现#includeiostreamusingnamespacestd;constintMaxSize=10;intvisited[MaxSize]={0};structArcNode{intadjvex;ArcNode*next;};templateclassDataTypestructVertexNode{DataTypevertex;ArcNode*firstedge;};templateclassDataTypeclassALGraph{public:ALGraph(DataTypea[],intn,inte);~ALGraph();voidBFSTraverse(intv);private:VertexNodeDataTypeadjlist[MaxSize];intvertexNum,arcNum;};templateclassDataTypeALGraphDataType::ALGraph(DataTypea[],intn,inte){ArcNode*s;inti,j,k;vertexNum=n;arcNum=e;for(i=0;ivertexNum;i++){adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL;}for(k=0;karcNum;k++){cout请输入边的两个顶点的序号：;cinij;s=newArcNode;s-adjvex=j;s-next=adjlist[i].firstedge;adjlist[i].firstedge=s;}}templateclassDataTypeALGraphDataType::~ALGraph(){ArcNode*p=NULL;for(inti=0;ivertexNum;i++){p=adjlist[i].firstedge;while(p!=NULL){adjlist[i].firstedge=p-next;deletep;p=adjlist[i].firstedge;}}}templateclassDataTypevoidALGraphDataType::BFSTraverse(intv){intQ[MaxSize];intfront=-1,rear=-1;ArcNode*p=NULL;coutadjlist[v].vertex;visited[v]=1;Q[++rear]=v;while(front!=rear){v=Q[++front];p=adjlist[v].firstedge;while(p!=NULL){intj=p-adjvex;if(visited[j]==0){coutadjlist[j].vertex;visited[j]=1;Q[++rear]=j;}p=p-next;}}}intmain(){charch[]={'A','B','C','D','E'};inti;ALGraphcharALG(ch,5,6);for(i=0;iMaxSize;i++)visited[i]=0;cout广度优先遍历序列为：;ALG.BFSTraverse(0);coutendl;return0;}五、调试过程与运行结果六、总结与心得图是一种复杂的数据结构，不仅各个顶点的度可以相差很多，而且顶点间的逻辑关系——邻接关系也错综复杂。应多动手练习。