数据结构实验4

南昌大学实验报告南昌大学实验报告学生姓名： 学号：—专业班级：—实验类型：口验证■综合□设计口创新实验日期： 实验成绩： 一、 实验名称用C++程序实现图的操作（采用邻接矩阵存储）二、 实验目的1．掌握图的基本概念和基本用法；2．掌握图的存储结构和图的种类等；掌握最短路径的算法和最小生成树的生成方法；能够用C++程序实现图的操作。三．实验环境PC微机DOS操作系统或Windows操作系统VisualC++程序集成环境实验内容与步骤在图的邻接矩阵存储中，用kind表示图的种类；vexNum表示图的顶点数；用一个顺序表verx来存储顶点数据值数组；arCNum表示边/弧数；另外，用邻接矩阵arcs表示顶点间的边/弧关系，邻接矩阵的元素arcs[i][j]仅表示相应的边/弧是否存在时，可定义为值为0和1的枚举类型，一般用0和1表示非边/弧及边/弧；对于网，非无穷的arcs[i][j]表示边或弧的权值。无向图的邻接矩阵是对称矩阵；某顶点的度是邻接矩阵中该顶点对应行或列中1的累加和。有向图的邻接矩阵不一定是对称矩阵；某顶点的出度是邻接矩阵中该顶点对应行1之和，入度是该顶点对应列1之和。1.输入图的邻接矩阵首先，输入图的种类，顶点数；接着输入顶点数据值；再根据图的种类，输入边/弧数；随后把邻接矩阵初始化为0，但是对于网，邻接矩阵非对角线上的元素初始化为无穷；最后，逐一输入各条边/弧，即顶点有效并且边/弧不重复。2•用普里姆（Prim）算法从某个顶点出发构造最小生成树普里姆（Prim）算法构造最小生成树的过程中使用了一个辅助数组closedge,数组的每个元素包括两个域即adjvex及lowcost。adjvex域记录每个顶点在最小生成树的双亲，即每个顶点是通过哪个顶点进入最小生成树的。对于没有进入最小生成树中的灰色顶点，lowcost域记录这些顶点与目前最小生成树的最短距离；对于进入最小生成树中的白色顶点‘lowcost域标记为0。初始时，用起始顶点邻接到的顶点的权值，即用邻接矩阵起始顶点所在行的信息初始化辅助数组closedge。辅助数组对应起始顶点元素的lowcost域置为0，表示首先选中起始顶点做为根结点，再依次执行如下操作：按权值的非递减顺序，从没有进入最小生成树的顶点，即lowcost域为非0的灰色顶点中，选择最小生成树的一条新的分支，即查找一个与目前最小生成树有最短距离的新顶点。输出查找到的新的分支。把辅助数组中此顶点对应元素的lowcost域置为0（由灰色顶点转为白色顶点），即标记新顶点为选中。扫描辅助数组，对于没有进入最小生成树中的灰色顶点，如果因为新顶点的加入，与目前最小生成树的距离更短了，则要修改辅助数组对应灰色顶点的元素，即adjvex域该为新顶点，表示其将来在最小生成树中可能的双亲顶点，lowcost域修改为新顶点到该灰色顶点的权值。用克鲁斯卡尔（Kruskal）算法构造最小生成树用克鲁斯卡尔（Kruskal）算法构造最小生成树的过程中使用了一个辅助数组set，记录了每个顶点所处集合最后一个顶点的下标，依次判断任意两顶点是否在同一个集合中，初始哈为0，表示所有顶点都在不同的子集中。首先，扫描邻接矩阵，把各边按权值由小到大排序，并把边的顶点下标和权值都存储在数组edges中。然后，从前往后逐一扫描数组edges中的每条边，根据辅助数组set，判断此边的两端点是否在同一子集中。如果不在同一子集中，则选择此边作为最小生成树的一条新的分支，并把这两个子集合并为一个子集。有向图从某个顶点出发到其余各点的最短路径（Dijkstra）该操作借助一维数组final的元素final[i]标记是否已经找到从起始点到下标为i的顶点的最短路径，初始化为零，若为非零值表示是第几个生成最短路径的顶点；一维数组shortest的元素shortest[i]记录起始顶点到下标为i的顶点的最短路径长度；二维辅助数组path的path[i]记录了起始顶点到下标为i的顶点最短路径的经过的顶点顺序，全部初始化为0。初始时，根据邻接矩阵起始点（小标为k）所在行的信息，初始化每个顶点对应的辅助数组shortest和path，具体执行如下操作：用邻接矩阵arcs[k][i]初始化辅助数组shortest对应元素shortest[i]，表示初始时，起始点到每个顶点的最短路径长度;若起始点邻接于下标为i的顶点，则把辅助数组path的元素path[i][k]在修改为1，表示起始点到下标为i的顶点的最短路径第1个包含了起始顶点。再按照如下步骤生成从起始顶点出发到其余各点的最短路径。首先，认为已经找到起始点自身到自身的长度为0的最短路径，标记辅助数组shortest，final和path的相应单元。然后根据辅助数组final和shortest，从没有生成最短路径的顶点中，选择具有最短路径的新顶点vmini，并在辅助数组final对应元素final[min_i]上标记已经找到其最短路径。由于顶点vmin）的加入，对于没有生成最短路径的顶点Vj,如果距离起始顶点的最短路径更短了，则修改其数组shortest中的对应值shortest[j]，并且把path数组新顶点行的信息path[min_i]复制到path[j]上，表示从起始点到新顶点最短的路径上的顶点，可能也是顶点Vj将来最短路径上的顶点。最后，显示起始点到各顶点的最短路径的生成顺序，及每条最短路径上的顶点顺序及最短路径长度。有向图各对顶点之间的最短路径（Floyd）该操作借助二维数组sp，该数组元素sp[i][j]的node域记录了顶点对viv.之间的最短路径上包含的顶点，sp[i][j]的distance域记录了顶点对viv.之间的最短路径长度。初始时，用各顶点对之间的距离，即邻接矩阵初始化数组sp。接着，判断两顶点如果因为经过其他顶点有更短的路径，则修改它们之间最短路径上包含的顶点及最短路径的长度。最后，输出各顶点对之间的最短路径及其长度。五、实验数据及处理结果源程序：//头文件一些常量的定义#defineNULL0#defineOK1#defineERROR0#defineOVERFLOW-1typedefboolStatus;//MGraph.h#include<iostream>#defineMAX_VERTEX_NUM20#defineINFINITY10000#ifndefMYHEAD_H#defineMYHEAD_H#include"MYHEAD.h"#endif//定点之间最短路径信息的类型定义classShortestPathInformationpublic:boolnode[MAX_VERTEX_NUM];intdistance;};〃图(采用邻接矩阵存储)数据结构C++类定义(基类)template<typenameElemType1,typenameElemType2>classMGraph{public://判断图是否为空boolisEmpty();//功能：输入有向图voidInputGraph();〃功能：有向网从某个顶点出发到其余各点的最短路径(Dijkstra)voidShortestPath_DIJ(ElemType1begin_vertex);〃有向网各对顶点之间的最短路径(Floyd)void shortestPath_FLOYD(ShortestPathInformationsp[MAX_VERTEX_NUM][MAX_VERTEX_NUM],intdisplay=1);protected:intkind; 〃图的种类(有向图kind=0，有向网kind=1,无向图kind=2,无向网kind=3)intvexNum; //图的顶点数ElemType1verxs[MAX_VERTEX_NUM]; //顶点的数据值数组intarcNum; //图的边/弧数//邻接矩阵,对图其元素用1或0表示两顶点是否相邻；对网络,则表示两顶点间的权值ElemType2arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];};//MGraph类的实现//功能：判断图是否为空template<typenameElemType1,typenameElemType2>boolMGraph<ElemType1,ElemType2>::isEmpty()return!vexNum;}//功能：输入有向图template<typenameElemType1,typenameElemType2>voidMGraph<ElemType1,ElemType2>::InputGraph(){coutvv"PleaseInputthegraph:(有向图kind=O，有向网kind=l,无向图kind=2,无向网kind=3)"<<endl;cin>>kind;coutvv"Pleaseinputthenumberofvertex(图的顶点数):"vvendl;cin>>vexNum;coutvv"Pleaseinputthenumberofarcnum(图的边/弧数):"vvendl;cin>>arcNum;//初始化数组for(inti=0;i<vexNum;i++)for(intj=0;j<vexNum;j++){arcs[i][j]=INFINITY;}//输入顶点信息coutvv"请输入顶点信息:"vvendl;for(intk=0;k<vexNum;k++)cin>>verxs[k];//输入各顶点权值信息coutvv"Pleaseinputtheinformationofvertex(输入各顶点权值信息):"vvendl;//coutvv"Pleaseinput'-l'toquit:"vvendl;//intvalue=0;for(intx=0;xvarcNum;x++){coutvv"Pleaseinput"vvx+lvv"valueofvertex:"vvendl;inti,j;cin>>i;cin>>j;cin>>arcs[i-1][j-1];}〃功能：有向网各对顶点之间的最短路径(Floyd)template<typenameElemType1,typenameElemType2>voidMGraph<ElemType1,ElemType2>::shortestPath_FLOYD(ShortestPathInformationsp[MAX_VERTEX_NUM][MAX_VERTEX_NUM],intdisplay){//用各对顶点之间的距离，即邻接矩阵初始化数组spfor(inti=0;i<vexNum;i++)for(intj=0;j<vexNUm;++j){for(intw=0;w<vexNum;++w)sp[i][j].node[w]=false;sp[i][j].distance=arcs[i][j];if(sp[i][j].distance<INFINITY){//如果下标i的顶点到下标j的顶点有弧，则在最短路径上标记此弧的两个端点sp[i][j].node[i]=sp[i][j].node[j]=true;}}//两顶点如果因为经过其他顶点有更短的路径，则修改它们之间的最短路径及最短路径的长度for(intk=0;k<vexNum;++k)for(i=0;i<vexNum;i++)for(intj=0;j<vexNum;++j)if(sp[i][k].distance+sp[k][j].distance<sp[i][j].distance)sp[i][j].distance=sp[i][k].distance+sp[k][j].distance;〃获取最短路径for(intw=0;w<vexNum;++w)sp[i][j].node[w]=sp[i][k].node[w]||sp[k][j].node[w];}if(display){coutvv"各顶点对之间的最短路径及其长度如下所示："vvendl;for(i=0;i<vexNum;i++){if(iv10)coutvv"\t["vvivv"]";elsecoutvv"\t["vvivv"]";}coutvvendl;for(i=0;ivvexNum;++i){if(iv10)coutvv"["vvivv"]";elsecoutvv"["vvivv"]";//输出最短路径上的顶点for(intj=0;jvvexNum;++j){coutvv"\t";for(intlength=0,k=0;kvvexNum;++k)if(sp[i][j].node[k])coutvvk;}coutvvendl;//输出最短路径的长度for(j=0;j<vexNum;++j){cout<<"\t";if(sp[i][j].distance==INFINITY)cout<<"**";elsecout<<sp[i][j].distance;}cout<<endl;}}}〃功能：有向网从某个顶点出发到其余各点的最短路径(Dijkstra)template<typenameElemType1,typenameElemType2>voidMGraph<ElemType1,ElemType2>::ShortestPath_DIJ(ElemType1begin_vertex){intorder=1;intstep=1;intk;intmin_i,min_shortest;intfinal[MAX_VERTEX_NUM]={0};intshortest[MAX_VERTEX_NUM];intpath[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={0};while(1){for(k=0;k<vexNum&&verxs[k]!=begin_vertex;++k);if(k==vexNum)coutvv"\n顶点"vvbegin_vertexvv"不存在，请重新输入！"vvendl;coutvv"请输入一个顶点"；cin>>begin_vertex;continue;}break;}for(inti=0;i<vexNum;++i){shortest[i]=arcs[k][i];for(intj=0;j<vexNum;++j)path[i][j]=0;if(arcs[k][i])path[i][k]=step;}shortest[k]=0;final[k]=order;path[k][k]=step;for(i=1;i<vexNum;++i){min_shortest=INFINITY;for(intj=0;j<vexNum;++j)if(!final[j]&&shortest[j]<min_shortest){min_i=j;min_shortest=shortest[j];}if(!path[min_i][min_i])path[min_i][min_i]=++step;elsestep=path[min_i][min_i];final[min_i]=++order;for(j=0;j<vexNum;++j)if(!final[j]&&(min_shortest+arcs[min_i][j]<shortest[j])){shortest[j]=min_shortest+arcs[min_i][j];for(intl=0;l<vexNum;++l)path[j][l]=path[min_i][l];path[j][j]=path[min_i][min_i]+l;}}cout<<endl;coutvv"顶点"vvbegin_vertexvv"到其余各顶点的最短路径上的顶点"vvendl;cout<<"\t";for(i=0;ivvexNum;i++)coutvv""vvverxs[i]vv"";coutvvendl;coutvv"\t";for(i=0;ivvexNum;i++){if(iv10)coutvv"["vvivv"]";elsecoutvv"["vvivv"]";}coutvv"最短路径";coutvvendl;for(i=0;ivvexNum;++i){coutvv""vvfinal[i]vv":"vvverxs[i]vv"";if(iv10)coutvv"["vvivv"]";elsecoutvv"["vvivv"]";for(intj=0;jvvexNum;++j)cout.width(4);cout.fill('');cout.setf(ios::right,ios::adjustfield);cout<<path[i][j];}if(shortest[i]==INFINITY)coutvv" °°";