武汉纺织大学《数据结构》实验报告3

武汉纺织大学《数据结构》实验报告班级：管工类专业班姓名：序号：实验时间：2014年5月16日指导教师：实验三：图的基本操作与应用一、实验目的：1、掌握图的几种主要存储方法及基本操作2、掌握图的两种遍历方法3、掌握利用普里姆算法和克鲁斯卡尔算法求取最小生成树的方法4、掌握求取AOE网关键路径的方法，以实现项目时间管理二、实验内容：1、编写程序，输出图的邻接矩阵，输出两种遍历序列，并求出最小生成树。实验步骤：①、在Java语言编辑环境中新建程序，输入顶点集合和边集合，构造一个图7-15所示的带权图，可参考书本225页示例程序；②、对该带权图，进行插入顶点、插入边、删除顶点、删除边操作，并输出操作后的邻接矩阵，可参考书本226-228页示例程序；③、输出从顶点'A'开始的深度优先遍历和广度优先遍历的序列，可参考书本238、240页示例程序；④、输出运用普里姆算法求出的最小生成树，可参考书本245页示例程序。2、设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。实验步骤：①、在Java语言编辑环境中新建程序，输入如下图所示的AOE网；②、按照关键路径求取步骤，求出各个顶点的最早开始时间和最迟开始时间；③、求出各个活动的最早开始时间和最迟开始时间；④、找出该AOE网的关键路径，并计算出该项目的完成时间。关键路径相关时间知识点：设活动ai由弧j,k(即从顶点j到k)表示，其持续时间记为dut(j,k),则：e(i)=ve(j)l(i)=vl(k)-dut(j,k)求ve(i)和vl(j)分两步：（1）.从ve(1)=0开始向前递推ve(j)=Max{ve(i)+dut(i,j)}i,j∈T,2=j=n，其中，T是所有以j为弧头的弧的集合。（2）.从vl(n)=ve(n)开始向后递推vl(i)=Min{vl(j)-dut(i,j)}i,j∈S,1=i=n-1，其中，S是所有以i为弧尾的弧的集合。求关键路径的算法：①、输入e条弧j,k，建立AOE网的存储结构；②、从起始点出发，令ve[0]=0，按拓扑顺序求其余各顶点的最早发生时间ve[i](1=i=n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止，否则转到步骤③；③、从终结点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑顺序求其余各顶点的最迟发生时间vl[i](n-2=i=0)；④、根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某弧满足条件e(s)=l(s)，则为关键活动。三、操作步骤：Test1代码：Graph1.javapackageFrist;publicclassGraph1{publicstaticvoidmain(String[]args){String[]vertices={A,B,C,D,E};Edgeedges[]={newEdge(0,1,5),newEdge(0,3,2),newEdge(1,0,5),newEdge(1,2,7),newEdge(1,3,6),newEdge(2,1,7),newEdge(2,3,8),newEdge(2,4,3),newEdge(3,0,2),newEdge(3,1,6),newEdge(3,2,8),newEdge(3,4,9),newEdge(4,2,3),newEdge(4,3,9)};AdjMatrixGraphStringgraph=newAdjMatrixGraphString(vertices,edges);System.out.println(带权无向图,+graph.toString());System.out.println(插入顶点F,插入边(A,F,20),删除顶点C,删除边(D,E));inti=graph.insertVertex(F);graph.insertEdge(0,i,20);graph.insertEdge(i,0,20);graph.removeVertex(2);graph.removeEdge(2,3);graph.removeEdge(3,2);System.out.println(graph.toString());AdjMatrixGraphStringgraph1=newAdjMatrixGraphString(vertices,edges);System.out.print(深度优先遍历序列为：);graph1.DFSTraverse(0);System.out.print(广度优先遍历序列为：);graph1.BFSTraverse(0);AdjMatrixGraphStringgraph2=newAdjMatrixGraphString(vertices,edges);System.out.print(带权无向图,+graph2.toString());graph2.minSpanTree_prim();}}LList.javapackageFrist;publicinterfaceLListT{booleanisEmpty();intlength();Tget(inti);voidset(inti,Tx);voidinsert(inti,Tx);Tremove(inti);voidremoveAll();}QQueue.javapackageFrist;publicinterfaceQQueueT{booleanisEmpty();voidenqueue(Tx);Tdequeue();}SeqList.javapackageFrist;publicclassSeqListTimplementsLListT{privateObject[]element;privateintlen;publicSeqList(intsize){this.element=newObject[size];this.len=0;}publicSeqList(){this(64);}publicbooleanisEmpty(){returnthis.len==0;}publicintlength(){returnthis.len;}publicTget(inti){if(i=0&&ithis.len)return(T)this.element[i];returnnull;}publicvoidset(inti,Tx){if(x==null)return;if(i=0&&ithis.len)this.element[i]=x;elsethrownewIndexOutOfBoundsException(i+);}publicStringtoString(){Stringstr=(;if(this.len0)str+=this.element[0].toString();for(inti=1;ithis.len;i++)str+=,+this.element[i].toString();returnstr+);}publicvoidinsert(inti,Tx){if(x==null)return;if(this.len==element.length){Object[]temp=this.element;this.element=newObject[temp.length*2];for(intj=0;jtemp.length;i++)this.element[i]=temp[j];}if(i0)i=0;if(ithis.len)i=this.len;for(intj=this.len-1;j=i;j--)this.element[j+1]=this.element[j];this.element[i]=x;this.len++;}publicvoidappend(Tx){insert(this.len,x);}publicTremove(inti){if(this.len==0||i0||i=this.len)returnnull;Told=(T)this.element[i];for(intj=i;jthis.len-1;j++)this.element[j]=this.element[j+1];this.element[this.len-1]=null;this.len--;returnold;}publicvoidremoveAll(){this.len=0;}}SeqQueue.javapackageFrist;publicclassSeqQueueTimplementsQQueueT{privateObjectelement[];privateintfront,rear;publicSeqQueue(intlength){if(length64)length=64;this.element=newObject[Math.abs(length)];this.front=this.rear=0;}publicSeqQueue(){this(64);}publicbooleanisEmpty(){returnthis.front==this.rear;}publicvoidenqueue(Tx){if(x==null)return;if(this.front==(this.rear+1)%this.element.length){Object[]temp=this.element;this.element=newObject[temp.length*2];inti=this.front,j=0;while(i!=this.rear){this.element[j]=temp[i];i=(i+1)%temp.length;j++;}this.front=0;this.rear=j;}this.element[this.rear]=x;this.rear=(this.rear+1)%this.element.length;}publicTdequeue(){if(isEmpty())returnnull;Ttemp=(T)this.element[this.front];this.front=(this.front+1)%this.element.length;returntemp;}publicStringtoString(){Stringstr=(;if(!isEmpty()){str+=this.element[this.front].toString();inti=(this.front+1)%this.element.length;while(i!=this.rear){str+=,+this.element.length;}}returnstr+);}}GGraph.javapackageFrist;publicinterfaceGGraphT{publicstaticfinalintMAX_WEIGHT=99999;intvertexCount();Tget(inti);intgetWeight(inti,intj);intinsertVertex(Tx);voidinsertEdge(inti,intj,intweight);voidremoveEdge(inti,intj);voidremoveVertex(inti);intgetNextNeighbor(inti,intj);voidDFSTraverse(inti);voidBFSTraverse(inti);}AbstractGraph.javapackageFrist;publicabstractclassAbstractGraphTimplementsGGraphT{publicabstractintvertexCount();publicabstractTg