数据结构实习报告图.doc

数据结构课程设计实习报告 题 目：图的基本操作学 号：1210522姓 名：何厚华年 级：大二学 院：计算机与控制工程学院专 业：计算机科学与技术完成日期：2014年5月21日授课教师：辛运帏目录1.题目. 22.要求 . . . . . . . . . . . . . . . . . . . . . . . . 23.程序实现 . . . . . . . . . . . . . . . . . . . . . 3 3.1程序运行及编译环境 . . . . . . . . . . . . . . . . 3 3.2程序描述 . . . . . . . . . . . . . . . . . 3 3.3实现功能 . . . . . . . . . . . . . . . . . . 3 3.3.1子功能模块 . . . . . . . . . . . . . . . . . 4 3.3.1.1 子功能模块1 . . . . . . . . . . . . . . . 4 3.3.1.2子功能模块2. . . . . . . . . . . . . . . 5 3.3.1.3子功能模块3. . . . . . . . . . . . . . . 5 3.3.1.4子功能模块4. . . . . . . . . . . . . . 5 3.3.1.5子功能模块5. . . . . . . . . . . . . . . 5 3.3.2 数据结构. . . . . . . . . . . . . . . . . . . . 6 3.3.2.1 数据结构的操作1 . . . . . . . . . . . . . 7 3.3.2.2 数据结构的操作2 . . . . . . . . . . . . . 7 3.3.2.3 数据结构的操作3 . . . . . . . . . . . 8 3.3.3算法及程序说明. . . . . . . . . . . . . . . . . . 13 3.4运行结果 . . . . . . . . . . . . . . . . . . . 14 3.5尚未解决的问题 . . . . . . . . . . . . . . . . . . 161. 题目 图的基本操作给定N个顶点、E条边的图G，完成图的相关算法，具体要求如下：1 完成图的创建方法，即从键盘或文件输入图的信息，建立图的邻接表或是邻接矩阵存储结构。2 给出判定图的性质的算法，即能够判定图是否是有向图、无向图、有向无环图、连通图、哈密尔顿图等。3 根据输入的图的性质，实现以下算法（选择其中一两个）：l 如果图是有向无环图，则先实现图的某种遍历算法，在此基础上实现图的拓扑排序算法。l 如果图是连通图，则求出图的最大生成树（不是最小生成树，参考讲授的方法），即得到的生成树权值之和最大。l 如果图是无向图，则以第一个顶点当做源点，求出单源最短路径。l 对于哈密尔顿图，找出其哈密尔顿回路。2.要求：初始输入数据的格式由自己定义，例如，输入文件中保存的初始数据格式有以下两种：格式一3 3 2 15 解释：第一行是图中所含顶点个数m，后面是m行m列数据，对应邻接矩阵。格式二3 41 2 31 3 22 3 13 1 5解释：第一行是图中所含顶点个数m和边数e，后面是e条边的信息，如1 2 3表示顶点1到顶点2有权值为3的边。3. 程序实现 3.1程序运行及编译环境程序是用Visual Studio 2010即VS10.0 编译的。可以在windows系列的操作系统上运行。 3.2程序描述 该程序主要用于实现图的基本操作,包括：建立邻接矩阵存储结构，给出判定图的性质的算法，即能够判定图是否是有向图、无向图、有向无环图、连通图、哈密尔顿图等，然后在此基础上，如果图是连通图，则求出图的最大生成树，如果图是无向图，则以第一个顶点当做源点，求出单源最短路径。其流程如下： A).程序读取输入文件，并生成相应的数据结构a. 用二维数组来声明并存储图，完成初始化的工作b.建立图的邻接矩阵存储c.生成图的一步可达矩阵B).输出相关信息 a.判断图是否是有向图 b.判断图是否是无向图 c.判断图是否是连通图 d.判断图是否是有向无环图 e.判断图是否是哈密顿图C).编码以及译码a.如果图是连通图，则求出图的最大生成树。b.如果图是无向图，则以第一个顶点当做源点，求出单源最短路径。D).完成3.3实现功能建立邻接矩阵存储结构，给出判定图的性质的算法，即能够判定图是否是有向图、无向图、有向无环图、连通图、哈密尔顿图等，然后在此基础上，如果图是连通图，则求出图的最大生成树，如果图是无向图，则以第一个顶点当做源点，求出单源最短路径。3.3.1 子功能模块 子功能按照是否对象的方法分类：数组的处理以及树的处理；3.3.1.1 子功能模块1/*函数原型：int Pow(int x,int base=10);*函数参数：x 表示指数*函数功能：求base的幂次*/int Pow(int x,int base=10)if(x=0) return 1;return base*Pow(x-1);3.3.1.2子功能模块2/*函数原型：float Convert2Num(char* str)*函数参数：str 是文件流中的字符串*函数功能：把一个数字字符串转化为一个数字*/float Convert2Num(char* str)float num=0;int i=0,dot=0;if(*str)=I)return INF;while(*(str+i)if(dot!=0) dot+;if(*(str+i)!=.)num=10*num+*(str+i)-0;else dot=1;i+;return dot=0?num:num/Pow(dot-1);3.3.1.3子功能模块3函数功能：Mul矩阵平方放到result矩阵中Void SquareMatrix (int MulMAXNODESMAXNODES,int resultMAXNODESMAXNODES,int n) for(int k=0;kn;k+) for(int l=0;ln;l+) resultkl=0; for(int m=0;mn;m+) if(Mulkm*Mulml!=0) resultkl=1; break; 3.3.2 数据结构/*图这个数据结构的定义，从文件读入，用邻接矩阵存储NodesCount表示结点个数， AdjMatrixMAXNODESMAXNODES是邻接矩阵 ConnectMAXNODESMAXNODES表示一步可达矩阵，其中点到自身为可达*/class Graphint NodesCount;float AdjMatrixMAXNODESMAXNODES;int ConnectMAXNODESMAXNODES;public:Graph(ifstream &fin);/从文件读入图的元素，建立邻接矩阵bool IsUnDirectedGraph();/判断是否是无向图bool IsDirectedGraph();/判断是否是有向图bool IsDirectWithoutLoop();/判断是否是有向无环图bool IsConnected();/判断是否是连通图void Prim(int v);/从节点v开始，用类似prim算法的方法生成最大生成树void floyd();/用floyd算法求任意两个点之间的最短距离int GetNodesCount();/;3.3.2.1 数据结构的操作1/*函数原型：Graph:Graph(ifstream &fin)*函数参数：fin 存放图的文件*函数功能：构造函数，把一个图从文件读入*/Graph:Graph(ifstream &fin)char a MAXLENGTH;. NodesCount=0;while(!fin.eof()i=0;while(fin.get(ch). if(!NodesCount)/NodesCount有数即不再读入 NodesCount=Convert2Num(a); else num=Convert2Num(a); AdjMatrixidx/NodesCountidx%NodesCount=num;/邻接矩阵 Connectidx/NodesCountidx%NodesCount=(num=INF&(idx/NodesCount!=idx%NodesCount)?0:1);/一步可达矩阵 idx+; 3.3.2.2 数据结构的操作2/*函数原型：bool Graph:IsUnDirectedGraph()*函数参数：判断图是否是无向图*实现方法：判断邻接矩阵是否是对称的，如对称，则无向*/bool Graph:IsUnDirectedGraph() for(int k=0;k NodesCount-1;k+) for(int l=k+1;lNodesCount;l+) if(AdjMatrixkl!=AdjMatrixlk) return false; return true;3.3.2.3 数据结构的操作3/*函数原型：bool Graph:IsConnected()*实现方法：将一步可达矩阵依次平方，直到该乘积收敛得到的* 就是这个图的可达矩阵，这个算法复杂度是o(n2lgn)由于一步可达矩阵的对角线的元素全为1，而且矩阵的乘法是逻辑乘，所以，这个矩阵原来的某个位置如果为1，那么一直为1，最后一定会收敛，这里是将这个矩阵平方后再平方，加快收敛速度，从而快速判断这个图是否是连通的*/bool Graph:IsConnected()int temp1MAXNODESMAXNODES;int temp2MAXNODESMAXNODES;int temp; for(int k=0;k NodesCount;k+) for(int l=0;lNodesCount;l+) temp1kl=Connectkl;/初始化temp1矩阵 doSquareMatrix(&temp10,&temp20,NodesCount);/temp2=temp12 for(int k=0;k NodesCount;k+) for(int l=0;lNodesCount;l+) temp=temp1kl; temp1kl=temp2kl; temp2kl=temp; while(!IsSameMatrix(&temp10,&temp20,NodesCount);/直到收敛，也即temp2=temp22 cout可达矩阵如下：endl;printMatrix(&temp20,NodesCount); if(IsFull(&temp20,NodesCount)/任两点可达，图是连通的 return true; return false;3.3.2.4 数据结构的操作4/*函数原型：bool Graph:IsDirectWithoutLoop()*函数功能：判断一个图是否是有向无环图*实现方法：把一步可达矩阵对角线的元素变成0，然后这些矩阵 依次平方,直到收敛，如果是有向无环图，则对角线 上有非零的元素*/bool Graph:IsDirectWithoutLoop()if(IsUnDirectedGraph()|NodesCount=1)/单个结点或者无向图，就不是有向无环图return false;int AdjMAXNODESMAXNODES;int tempMAXNODESMAXNODES;int temp1, count=1; for(int k=0;k NodesCount;k+) for(int l=0;lNodesCount;l+) if(k!=l) Adjkl=Connectkl; else Adjkl=0;/对角元素为0 doSquareMatrix(&Adj0,&temp0,NodesCount);/temp=Adj2 count*=2; for(int k=0;k NodesCount;k+) if(tempkk!=0) return false; for(int l=0;lNodesCount;l+) temp1=tempkl; tempkl=Adjkl; Adjkl=temp1; while(count=NodesCount);/ cout如果下面矩阵对角线有非零元素，说明它是有环图endl; printMatrix(&temp0,NodesCount); for(int n=0;nNodesCount;n+) if(tempnn!=0) return false; if(!IsFull(&temp0,NodesCount,0)/如果如果这个矩阵全部是0，那么这是一个哈密顿图 cout这是一个哈密顿图！endl; return true;3.3.2.5 数据结构的操作5/*函数原型：void Graph:Prim(int v)*函数功能：仿照Prim算法，构建最大生成树*实现方法：从顶点v开始，选择剩下的顶点中与v相连的具有最小权值的边 加入到S集合中，然后不断在这两个集合里面找到两个点使得它们之间的权重是这个二分图里面最小的，直到集合S等于原来的顶点集为止*/void Graph:Prim(int v)bool IsUsedMAXNODES;/标记这个点是在哪个集合中float max=0;/记录最大权值int i,j,k,col,row;for(i=0;iNodesCount;i+)/NodesCount次循环IsUsedi=false;/初始化IsUsedv=true;for(i=1;iNodesCount;i+)max=0;for(j=0;jNodesCount;j+)for(k=0;kmax&AdjMatrixjkINF)/在两个集合里挑出两个元素，使得它们之间权值尽可能大max=AdjMatrixjk;/更新max的值row=j;col=k;IsUsedrow=IsUsedcol=true;/更新集合cout(row,col)权值为：maxendl;/输出边和权的构造过程3.3.2.6 数据结构的操作6/*函数原型：void Graph:floyd()*实现方法：弗洛伊德算法求任意两个点之间的最短距离*/void Graph:floyd()int AMAXNODESMAXNODES;int i,j,k;for(i=0;iNodesCount;i+)for(j=0;jNodesCount;j+)Aij=AdjMatrixij;for(k=0;kNodesCount;k+)for(int i=0;iNodesCount;i+)for(int j=0;j(Aik+Akj)Aij=Aik+Akj;printMatrix(&A0,NodesCount);3.3.3算法及程序说明本程序中重要的算法思想是：1. 判断一个图是否是连通图的算法，利用矩阵的特点，使得矩阵乘法的运算结果收敛从而快速判断图是否连通。2. 判断一个图是否是有向无环图，也是利用矩阵的乘法，不同的是，将对角元素置为0，当遇到对角元素为1时，说明存在了环路。3. 如果不存在环路但是其他位置有非零元素存在，则说明存在一条哈密顿通路。3.4运行结果图1. 在文本里面保存的图的数据，其中I表示无穷大（Infinite）。图2.从文本里面读入的邻接矩阵，是有向图，连通图，有向无环图，并求出了最大生成树。把这个图变成了一个无向图后，就可以求出其任意两个节点之间的最小距离了。3.5尚未解决的问题1. 多个空格一起出现在文本中，应该过滤掉后面的空格。2. Hamilton通路由于没有一个通用的解法，或者说是充要条件，只有穷举法可行，但是这是一个复杂度的方法，效率并不高，因此本程序仅仅是给出了一部分的Hamilton图，一部分还无法判断其是不是Hamilton图。3. 还有一些BUG没有修复。