下载文档原格式
实验项目：图的先深、先广遍历生成树
实验目的：
1、学会把图转化为程序能识别的邻接矩阵
2、透彻理解图的两种遍历方法及对应的生成树。
涉及的知识点：图的表示法、生成树的概念、图的深度优先、广度优先遍历算法
实验内容：
该程序是对树进行先深、先广遍历，请在此基础上，改为处理指定图，求该图从指定结点出发的先深、先广遍历生成树。
// AdjMWGraph.h : Defines the entry point for the console application.
#include "SeqList.h"
#include "SeqQueue.h"
const int MaxVertices=10;
const int Max Weight=10000; //表示无穷大
class AdjMWGraph
{
private:
SeqList Vertices; // 顶点信息的线性表
int Edge[MaxVertices][MaxVertices]; //边的权信息矩阵
int numOf E dges; //当前的边数
public:
AdjMWGraph(const int sz=MaxVertices);//构造函数，参数是顶点数目
int GraphEmpty()const
{ return Vertices.ListEmpty(); }
int NumOfVertices(void)//当前结点个数
{ return Vertices.ListSize(); }
int NumOf E dges(void)//边数
{ return numOf E dges; }
VerT GetValue(const int i); //取结点i的值
int GetWeight(const int v1, const int v2); //取弧的权重;
//插入顶点vertex
void InsertVertex(const VerT &vertex);
//插入弧
void InsertE dge(const int v1,const int v2,int w eight);
//删除与顶点i及关联的边
void DeleteVertex(const int i);
//删除弧
void DeleteEdge(const int v1,const int v2);
//取顶点i的第一条邻接边，返回邻接点的下标，否则返回-1
int GetFirstNeighbor(const int v);
//取顶点v1与
//对连通图从顶点v开始用visit()先深访问
void DepthFirstSearch(const int v, int visited[],void visit(VerT item));
//对连通图从顶点v开始用visit()先广访问
void BroadFirstSearch(const int v, int visited[],void visit(VerT item));
//对非连通图用v isit()先深访问
void DepthFirstSearch(void visit(VerT item));
//对非连通图用v isit()先广访问
void BroadFirstSearch(void visit(VerT item));
};
//构造函数，参数是顶点数目
AdjMWGraph::AdjMWGraph(const int sz)
{
for(int i=0;i for (int j=0;j { if(i==j)Edge[i][j]=0; else Edge[i][j]=MaxWeight; } numOf E dges=0; //边数初始为0 } //取顶点i的值 VerT AdjMWGraph::GetValue(const int i) { if(i<0||i>Vertices.ListSize()) { cerr<<"参数越界出错！"< exit(1); } //使用线性表的GetData(i)成员函数返回顶点i的值 return Vertices.GetData(i); } //取弧的权重 int AdjMWGr aph::GetWeight(const int v1,const int v2) { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) { cerr<<"参数越界出错！"< exit(1); } return Edge[v1][v2]; } //插入顶点vertex void AdjMWGraph::InsertVertex(const VerT &vertex) { //在顶点线性表Vertices的当前表尾ListSize()插入顶点vertex Vertices.Insert(vertex,Vertices.ListSize()); } //插入弧 void AdjMWGraph::InsertEdge(const int v1,const int v2,int w eight) { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) { cerr<<"参数越界出错！"< exit(1); } E dge[v1][v2]=w eight; E dge[v2][v1]=w eight;//选做，无向边变成有向边 numOf E dges++; } //删除与顶点v及关联的边 void AdjMWGraph::DeleteVertex(const int v) { for(int i=0;i for(int j=0;j if((i==v||j==v)&&(Edge[i][j]>0&&Edge[i][j] { E dge[i][j]=MaxWeight; numOf E dges--; } Vertices.Delete(v); } //删除弧 void AdjMWGraph::DeleteEdge(const int v1,const int v2) { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) { cerr<<"参数越界出错！"< exit(1); } E dge[v1][v2]=MaxWeight; numOf E dges--; } //取顶点i的第一条邻接边，返回邻接点的下标，否则返回-1 int AdjMWGr aph::GetFirstNeighbor(const int v)
