图的遍历生成树

实验项目：图的先深、先广遍历生成树实验目的：1、学会把图转化为程序能识别的邻接矩阵2、透彻理解图的两种遍历方法及对应的生成树。涉及的知识点：图的表示法、生成树的概念、图的深度优先、广度优先遍历算法实验内容：该程序是对树进行先深、先广遍历，请在此基础上，改为处理指定图，求该图从指定结点出发的先深、先广遍历生成树。//AdjMWGraph.h:Definestheentrypointfortheconsoleapplication.#includeSeqList.h#includeSeqQueue.hconstintMaxVertices=10;constintMaxWeight=10000;//表示无穷大classAdjMWGraph{private:SeqListVertices;//顶点信息的线性表intEdge[MaxVertices][MaxVertices];//边的权信息矩阵intnumOfEdges;//当前的边数public:AdjMWGraph(constintsz=MaxVertices);//构造函数，参数是顶点数目intGraphEmpty()const{returnVertices.ListEmpty();}intNumOfVertices(void)//当前结点个数{returnVertices.ListSize();}intNumOfEdges(void)//边数{returnnumOfEdges;}VerTGetValue(constinti);//取结点i的值intGetWeight(constintv1,constintv2);//取弧的权重;//插入顶点vertexvoidInsertVertex(constVerT&vertex);//插入弧v1,v2，权为weightvoidInsertEdge(constintv1,constintv2,intweight);//删除与顶点i及关联的边voidDeleteVertex(constinti);//删除弧v1,v2voidDeleteEdge(constintv1,constintv2);//取顶点i的第一条邻接边，返回邻接点的下标，否则返回-1intGetFirstNeighbor(constintv);//取顶点v1与v1,v2邻接边的下一条邻接边，返回邻接点，否则返回-1intGetNextNeighbor(constintv1,constintv2);//对连通图从顶点v开始用visit()先深访问voidDepthFirstSearch(constintv,intvisited[],voidvisit(VerTitem));//对连通图从顶点v开始用visit()先广访问voidBroadFirstSearch(constintv,intvisited[],voidvisit(VerTitem));//对非连通图用visit()先深访问voidDepthFirstSearch(voidvisit(VerTitem));//对非连通图用visit()先广访问voidBroadFirstSearch(voidvisit(VerTitem));};//构造函数，参数是顶点数目AdjMWGraph::AdjMWGraph(constintsz){for(inti=0;isz;i++)for(intj=0;jsz;j++){if(i==j)Edge[i][j]=0;elseEdge[i][j]=MaxWeight;}numOfEdges=0;//边数初始为0}//取顶点i的值VerTAdjMWGraph::GetValue(constinti){if(i0||iVertices.ListSize()){cerr参数越界出错！endl;exit(1);}//使用线性表的GetData(i)成员函数返回顶点i的值returnVertices.GetData(i);}//取弧的权重intAdjMWGraph::GetWeight(constintv1,constintv2){if(v10||v1Vertices.ListSize()||v20||v2Vertices.ListSize()){cerr参数越界出错！endl;exit(1);}returnEdge[v1][v2];}//插入顶点vertexvoidAdjMWGraph::InsertVertex(constVerT&vertex){//在顶点线性表Vertices的当前表尾ListSize()插入顶点vertexVertices.Insert(vertex,Vertices.ListSize());}//插入弧v1,v2，权为weightvoidAdjMWGraph::InsertEdge(constintv1,constintv2,intweight){if(v10||v1Vertices.ListSize()||v20||v2Vertices.ListSize()){cerr参数越界出错！endl;exit(1);}Edge[v1][v2]=weight;Edge[v2][v1]=weight;//选做，无向边变成有向边numOfEdges++;}//删除与顶点v及关联的边voidAdjMWGraph::DeleteVertex(constintv){for(inti=0;iVertices.ListSize();i++)for(intj=0;jVertices.ListSize();j++)if((i==v||j==v)&&(Edge[i][j]0&&Edge[i][j]MaxWeight)){Edge[i][j]=MaxWeight;numOfEdges--;}Vertices.Delete(v);}//删除弧v1,v2voidAdjMWGraph::DeleteEdge(constintv1,constintv2){if(v10||v1Vertices.ListSize()||v20||v2Vertices.ListSize()){cerr参数越界出错！endl;exit(1);}Edge[v1][v2]=MaxWeight;numOfEdges--;}//取顶点i的第一条邻接边，返回邻接点的下标，否则返回-1intAdjMWGraph::GetFirstNeighbor(constintv){if(v0||vVertices.ListSize()){cerr参数越界出错！endl;exit(1);}for(intcol=0;col=Vertices.ListSize();col++)if(Edge[v][col]0&&Edge[v][col]MaxWeight)returncol;return-1;}//取顶点v1与v1,v2邻接边的下一条邻接边，返回邻接点，否则返回-1intAdjMWGraph::GetNextNeighbor(constintv1,constintv2){if(v10||v1Vertices.ListSize()||v20||v2Vertices.ListSize()){cerr参数越界出错！endl;exit(1);}for(intcol=v2+1;col=Vertices.ListSize();col++)if(Edge[v1][col]0&&Edge[v1][col]MaxWeight)returncol;return-1;}//对连通图从顶点v开始用visit()先深访问voidAdjMWGraph::DepthFirstSearch(constintv,intvisited[],voidvisit(VerTitem)){visited[v]=1;intw=GetFirstNeighbor(v);while(w!=-1){if(!visited[w]){visit(GetValue(v));cout----GetValue(w)endl;//递归输出DepthFirstSearch(w,visited,visit);}w=GetNextNeighbor(v,w);}}//对连通图从顶点v开始用visit()先广访问voidAdjMWGraph::BroadFirstSearch(constintv,intvisited[],voidvisit(VerTitem)){VerTu,w;SeqQueuequeue;//定义队列queuevisited[v]=1;queue.QInsert(v);while(!queue.QueueEmpty()){u=queue.QDelete();w=GetFirstNeighbor(u);while(w!=-1){if(!visited[w]){visit(GetValue(u));cout----GetValue(w)endl;//递归输出visited[w]=1;queue.QInsert(w);}w=GetNextNeighbor(u,w);}}}//对非连通图用visit()先深访问voidAdjMWGraph::DepthFirstSearch(voidvisit(VerTitem)){int*visited=newint[NumOfVertices()];for(inti=0;iNumOfVertices();i++)visited[i]=0;intcount=0;for(i=0;iNumOfVertices();i++)if(!visited[i]){count++;DepthFirstSearch(i,visited,visit);}delete[]visited;coutendl连通分支数=countendl;}//对非连通图用visit()先广访问voidAdjMWGraph::BroadFirstSearch(voidvisit(VerTitem)){int*visited=newint[NumOfVertices()];for(inti=0;iNumOfVertices();i++)visited[i]=0;intcount=0;for(i=0;iNumOfVertices();i++)if(!visited[i]){count++;BroadFirstSearch(i,visited,visit);}delete[]visited;coutendl连通分支数=countendl;}//GraphLib.hstructRowColWeight{introw;intcol;intweight;};//建立图G，所建立的图G有n个顶点V[0]……V[n-1]，有e条边E[0]...E[e-1]voidCreatGraph(AdjMWGraph&G,DatatypeV[],intn,RowColWeightE[],inte){for(inti=0;in;i++)G.InsertVertex(V[i]);for(intk=0;ke;k++)G.InsertEdge(E[k].row,E[k].col,E[k].weight);}voidPrintchar(charitem){coutitem;}//Graph.cpptypedefcharVerT;typedefcharDatatype;#includeAdjMWGraph.h#includeGraphLib.hvoidmain(void){AdjMWGraphg;chara[]={'1','2','3','4','5','6','7','8'};RowColWeightrow[]={{0,1,1},{0,2,1},{1,0,1},{1,3,1},{1,4,1},{2,0,1},{2,5,1},{2,6,1},{3,