数据结构实验七 图及图的操作实验

实验报告七图及图的操作实验班级：2010XXX姓名：HoogLe学号：2010XXXX专业：XXXX2858505197@实验目的：1、掌握图的基本概念和术语2、掌握图的存储结构及创建算法。3、掌握图的遍历算法（递归算法）。实验内容：1、图邻接矩阵存储结构表示及基本操作算法实现[实现提示]（同时可参见教材及ppt上的算法）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：（1）邻接矩阵存储结构类定义：自定义如下：#include<iostream>usingnamespacestd;constintMaxSize=12;constintINFINITY=65535;template<classT>classMgraph{public: Mgraph(Ta[],intn,inte);//构造函数，a[]表示节点数组，n表示顶点个数，e表示边数 voidprintGraph();//输出 voidBFS(intv,intvisited[]);//广度优先搜索private: Tvertex[MaxSize]; intarc[MaxSize][MaxSize]; intvertexNum,arcNum; voidcreateUG(Ta[],intn,inte);//无向图 voidcreateUW(Ta[],intn,inte);//无向网 voidcreateHG(Ta[],intn,inte);//有向图 voidcreateHW(Ta[],intn,inte);//有向网};template<classT>Mgraph<T>::Mgraph(Ta[],intn,inte){ intkind; cout<<"请输入所需创建的图的类型:"<<endl; cout<<"1.无向图"<<endl; cout<<"2.无向网"<<endl; cout<<"3.有向图"<<endl; cout<<"4.有向网"<<endl; cin>>kind; switch(kind){ case1:createUG(a,n,e);break; case2:createUW(a,n,e);break; case3:createHG(a,n,e);break; case4:createHW(a,n,e);break; default:cout<<"输入错误！"<<endl; }}（2）创建邻接矩阵算法创建无向图邻接矩阵算法：template<classT>voidMgraph<T>::createUG(Ta[],intn,inte){//创建无向图vertexNum=n;//顶点数arcNum=e;//边数inti,j,k;for(i=0;i<vertexNum;i++) vertex[i]=a[i];for(i=0;i<vertexNum;i++)//初始化邻接矩阵 for(j=0;j<vertexNum;j++) arc[i][j]=0; for(k=0;k<arcNum;k++) //依次输入每一条边，并修改邻接矩阵的相应元素 {cout<<"请输入第"<<k+1<<"条边(格式：顶点1顶点2):"; cin>>i>>j;//边依附的两个顶点的序号arc[i-1][j-1]=1;//置有边标志arc[j-1][i-1]=1; }}创建无向网邻接矩阵算法：无向网的创建：template<classT>voidMgraph<T>::createUW(Ta[],intn,inte){//创建无向网intw;//权值vertexNum=n;//顶点数arcNum=e;//边数inti,j,k; for(i=0;i<vertexNum;i++) vertex[i]=a[i]; for(i=0;i<vertexNum;i++)//初始化邻接矩阵 for(j=0;j<vertexNum;j++)arc[i][j]=INFINITY; for(k=0;k<arcNum;k++) //依次输入每一条边，并修改邻接矩阵的相应元素 {cout<<"请输入第"<<k+1<<"条边(格式：顶点1顶点2权值):"; cin>>i>>j>>w; //边依附的两个顶点的序号arc[i-1][j-1]=w;//置有边标志arc[j-1][i-1]=w; }}创建有向图邻接矩阵算法：template<classT>voidMgraph<T>::createHG(Ta[],intn,inte){//创建无向图vertexNum=n;//顶点数arcNum=e;//边数inti,j,k;for(i=0;i<vertexNum;i++) vertex[i]=a[i];for(i=0;i<vertexNum;i++)//初始化邻接矩阵 for(j=0;j<vertexNum;j++) arc[i][j]=0; for(k=0;k<arcNum;k++) //依次输入每一条边，并修改邻接矩阵的相应元素 {cout<<"请输入第"<<k+1<<"条边(格式：顶点1顶点2):"; cin>>i>>j;//边依附的两个顶点的序号arc[i-1][j-1]=1;//置有边标志 }}创建有向网邻接矩阵算法：template<classT>voidMgraph<T>::createHW(Ta[],intn,inte){//创建无向图vertexNum=n;//顶点数arcNum=e;//边数inti,j,k; intw;for(i=0;i<vertexNum;i++) vertex[i]=a[i];for(i=0;i<vertexNum;i++)//初始化邻接矩阵 for(j=0;j<vertexNum;j++) arc[i][j]=0; for(k=0;k<arcNum;k++)//依次输入每一条边，并修改邻接矩阵的相应元素 { cout<<"请输入第"<<k+1<<"条边(格式：顶点1顶点2权值):"; cin>>i>>j>>w; //边依附的两个顶点的序号arc[i-1][j-1]=w;//置有边标志 }}（3）输出邻接矩阵结果算法template<classT>voidMgraph<T>::printGraph(){//输出邻接矩阵 inti,j; for(i=0;i<vertexNum;i++) { for(j=0;j<vertexNum;j++) cout<<arc[i][j]<<ends; cout<<endl; }}测试结果粘贴如下：voidmain(){ inta[6]={1,2,3,4,5,6}; Graph<int>graph1(a,6,5); graph1.printGraph();}2、图邻接表存储结构表示及基本操作算法实现[实现提示]函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：（1）邻接表存储结构类定义：自定义如下：#include<iostream>usingnamespacestd;constintMaxSize=12;classEdge//边{public: intadjvertex;//当前结点的下标 Edge*nextarc;//下一条边 intvalue;//边的权值};template<classT>classMgraph;template<classT>classVertexNode{//节点 friendclassMgraph<T>; Tvex;//结点名 Edge*firstarc;//第一个边};template<classT>classMgraph{public: Mgraph(Ta[],intn,inte);//构造一个有E条边N个结点的图，A[]为结点矩阵 ~Mgraph();//析构函数 voidprintGraph();//输出 voidDFS(intv,intvisited[]);//深度优先遍历private: VertexNode<T>adjlist[MaxSize];//存放结点 intvertexNum,arcNum;//顶点数和边数 voidcreatGraphU(Ta[],intn,inte);//无向图 voidcreatGraphH(Ta[],intn,inte);//有向图};template<classT>Mgraph<T>::~Mgraph(){ for(inti=0;i<vertexNum;i++) { Edge*E,*q; E=adjlist[i].firstarc; while(E) { q=E; E=E->nextarc; deleteq; } }}template<classT>Mgraph<T>::Mgraph(Ta[],intn,inte){ intkind; cout<<"请输入所需创建的图类型："<<endl; cout<<"1.无向图"<<endl; cout<<"2.有向图"<<endl; cin>>kind; switch(kind){ case1:creatGraphU(a,n,e);break; case2:creatGraphH(a,n,e);break; default:cout<<"输入错误！"<<endl; }}（2）创建邻接表算法创建无向网邻接表算法：template<classT>voidMgraph<T>::creatGraphU(Ta[],intn,inte){ Edge*E; vertexNum=n; arcNum=e; for(inti=0;i<vertexNum;i++) { adjlist[i].vex=a[i]; adjlist[i].firstarc=NULL; } intj,w; for(intk=0;k<arcNum;k++) { cout<<"请输入第"<<k+1<<"条弧的信息（格式为：顶点1顶点2权值）"; cin>>i>>j>>w; E=newEdge; E->value=w; E->adjvertex=j-1; E->nextarc=adjlist[i-1].firstarc; adjlist[i-1].firstarc=E; E=newEdge; E->value=w; E->adjvertex=i-1; E->nextarc=adjlist[j-1].firstarc; adjlist[j-1].firstarc=E; }}创建有向网邻接表算法：template<classT>voidMgraph<T>::creatGraphH(Ta[],intn,inte){ Edge*E; vertexNum=n; arcNum=e; for(inti=0;i<vertexNum;i++) { adjlist[i].vex=a[i]; adjlist[i].firstarc=NULL; } intj,w; for(intk=0;k<arcNum;k++) { cout<<"请输入第"<<k+1<<"条弧的信息（格式为：起点终点权值）"; cin>>i>>j>>w; E=newEdge; E->value=w; E->adjvertex=j-1; E->nextarc=adjlist[i-1].firstarc; adjlist[i-1].firstarc=E; }}（3）输出邻接表结果算法template<classT>voidMgraph<T>::printGraph(){ for(inti=0;i<vertexNum;i++) { Edge*p; cout<<i<<""; p=adjlist[i].firstarc; while(p) { cout<<p->adjvertex<<""; p=p->nextarc; } cout<<endl; }}测试结果粘贴如下：voidmain(){ inta[5]={1,2,3,4,5}; Mgraph<int>graph1(a,5,5); graph1.printGraph(); intvisited[5]={0}; graph1.DFS(2,visited);}3、图的遍历递归算法（1）（存储结构为邻接表）深度优先遍历算法递归算法：template<classT>voidMgraph<T>::DFS(intv,intvisited[]){ if(v>vertexNum){cout<<"顶点数处错误"<<endl;exit(0);}Edge*p; intj; cout<<adjlist[v].vex<<""; visited[v]=1;p=adjlist[v].firstarc;while(p!=NULL)//依次搜索顶点v的邻接点j { j=p->adjvertex; if(visited[j]==0)DFS(j,visited); p=p->nextarc;