图的遍历生成树.doc

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

1、实验项目：图的先深、先广遍历生成树实验目的：1、学会把图转化为程序能识别的邻接矩阵2、透彻理解图的两种遍历方法及对应的生成树。涉及的知识点：图的表示法、生成树的概念、图的深度优先、广度优先遍历算法实验内容：该程序是对树进行先深、先广遍历，请在此基础上，改为处理指定图，求该图从指定结点出发的先深、先广遍历生成树。 //AdjMWGraph.h:Definestheentrypointfortheconsoleapplication.#include"SeqList.h"#include"SeqQueue.h"constintMaxVertices

2、=10;constintMaxWeight=10000; //表示无穷大classAdjMWGraph{private: SeqListVertices;//顶点信息的线性表 intEdge[MaxVertices][MaxVertices];//边的权信息矩阵 intnumOfEdges;//当前的边数public: AdjMWGraph(constintsz=MaxVertices);//构造函数，参数是顶点数目 intGraphEmpty()const { returnVertices.ListEmpty();} intNumOfVert

3、ices(void)//当前结点个数 { returnVertices.ListSize();} intNumOfEdges(void)//边数 { returnnumOfEdges;} VerTGetValue(constinti);//取结点i的值 intGetWeight(constintv1,constintv2);//取弧的权重; //插入顶点vertex voidInsertVertex(constVerT&vertex); //插入弧，权为weight voidInsertEdge(constintv1,consti

4、ntv2,intweight); //删除与顶点i及关联的边 voidDeleteVertex(constinti); //删除弧 voidDeleteEdge(constintv1,constintv2); //取顶点i的第一条邻接边，返回邻接点的下标，否则返回-1 intGetFirstNeighbor(constintv); //取顶点v1与邻接边的下一条邻接边，返回邻接点，否则返回-1 intGetNextNeighbor(constintv1,constintv2); //对连通图从顶点v开始用visit(

5、)先深访问 voidDepthFirstSearch(constintv,intvisited[],voidvisit(VerTitem)); //对连通图从顶点v开始用visit()先广访问 voidBroadFirstSearch(constintv,intvisited[],voidvisit(VerTitem)); //对非连通图用visit()先深访问 voidDepthFirstSearch(voidvisit(VerTitem)); //对非连通图用visit()先广访问 voidBroadFirstSearch(voidvisi

6、t(VerTitem));};//构造函数，参数是顶点数目AdjMWGraph::AdjMWGraph(constintsz){ for(inti=0;i

7、

8、i>Vertices.ListSize()) {  cerr<<"参

9、数越界出错！"<

10、

11、v1>Vertices.ListSize()

12、

13、v2<0

14、

15、v2>Vertices.ListSize()) {  cerr<<"参数越界出错！"<

16、idAdjMWGraph::InsertVertex(constVerT&vertex){ //在顶点线性表Vertices的当前表尾ListSize