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

XX纺织大学《数据结构》实验报告班级：管工类专业班XX：序号：实验时间：2014年5月16日指导教师：实验三：图的基本操作与应用一、实验目的：、掌握图的几种主要存储方法及基本操作、掌握图的两种遍历方法、掌握利用普里姆算法和克鲁斯卡尔算法求取最小生成树的方法

、掌握求取AOE网关键路径的方法，以实现项目时间管理二、实验内容：、编写程序，输出图的邻接矩阵，输出两种遍历序列，并求出最小生成树。实验步骤：①、在Java语言编辑环境中新建程序，输入顶点集合和边集合，构造一个图7-15所示的带权图，可参考书本225页示例程序；②、对该带权图，进行插入顶点、插入边、删除顶点、删除边操作，并输出操作后的邻接矩阵，可参考书本226-228页示例程序；③、输出从顶点'A'开始的深度优先遍历和广度优先遍历的序列，可参考书本、240页示例程序；可参考书本245页示例程序。、设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。实验步骤：①、在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为弧头的弧的集合。（）.从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)。若某弧满足条，则为关键三、操作步：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)};AdjMatrixGraph<String>graph=newAdjMatrixGraph<String>(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());AdjMatrixGraph<String>graph1=newAdjMatrixGraph<String>(vertices,edges);System.out.print("深度优先遍历序列为：");graph1.DFSTraverse(0);System.out.print("广度优先遍历序列为：");graph1.BFSTraverse(0);AdjMatrixGraph<String>graph2=newAdjMatrixGraph<String>(vertices,edges);System.out.print("带权无向图,"+graph2.toString());graph2.minSpanTree_prim();}}LList.javapackageFrist;publicinterfaceLList<T>{booleanisEmpty();intlength();Tget(inti);voidset(inti,Tx);voidinsert(inti,Tx);Tremove(inti);voidremoveAll();}QQueue.javapackageFrist;publicinterfaceQQueue<T>{booleanisEmpty();voidenqueue(Tx);Tdequeue();}SeqList.javapackageFrist;publicclassSeqList<T>implementsLList<T>{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&&i<this.len)return(T)this.element[i];returnnull;}publicvoidset(inti,Tx){if(x==null)return;if(i>=0&&i<this.len)this.element[i]=x;elsethrownewIndexOutOfBoundsException(i+"");}publicStringtoString(){Stringstr="(";if(this.len>0)str+=this.element[0].toString();for(inti=1;i<this.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;j<temp.length;i++)this.element[i]=temp[j];}if(i<0)i=0;if(i>this.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||i<0||i>=this.len)returnnull;Told=(T)this.element[i];for(intj=i;j<this.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;publicclassSeqQueue<T>implementsQQueue<T>{privateObjectelement[];privateintfront,rear;publicSeqQueue(intlength){if(length<64)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;publicinterfaceGGraph<T>{publicstaticfinalint99999;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;publicabstractclassAbstractGraph<T>implementsGGraph<T>{publicabstractintvertexCount();publicabstractTget(inti);publicabstractintgetNextNeighbor(inti,intj);publicvoidDFSTraverse(inti){boolean[]visited=newboolean[this.vertexCount()];intj=i;do{if(!visited[j]){System.out.print("{");this.depthfs(j,visited);System.out.print("}");}j=(j+1)%this.vertexCount();}while(j!=i);System.out.println();}privatevoiddepthfs(inti,boolean[]visited){System.out.print(this.get(i)+"");visited[i]=true;intj=this.getNextNeighbor(i,-1);while(j!=-1){if(!visited[j])depthfs(j,visited);j=this.getNextNeighbor(i,j);}}publicvoidBFSTraverse(inti){boolean[]visited=newboolean[this.vertexCount()];intj=i;do{if(!visited[j]){System.out.print("{");breadthfs(j,visited);System.out.print("}");}j=(j+1)%this.vertexCount();}while(j!=i);System.out.println();}privatevoidbreadthfs(inti,boolean[]visited){System.out.print(this.get(i)+"");visited[i]=true;SeqQueue<Integer>que=newSeqQueue<Integer>(this.vertexCount());que.enqueue(newInteger(i));while(!que.isEmpty()){i=que.dequeue().intValue();intj=this.getNextNeighbor(i,-1);while(j!=-1){if(!visited[j]){System.out.print(this.get(j)+"");visited[j]=true;que.enqueue(newInteger(j));}j=this.getNextNeighbor(i,j);}}}publicabstractintgetWeight(inti,intj);publicvoidminSpanTree_prim(){Edge[]mst=newEdge[vertexCount()-1];for(inti=0;i<mst.length;i++)mst[i]=newEdge(0,i+1,this.getWeight(0,i+1));for(inti=0;i<mst.length;i++){intminweight=intmin=i;for(intj=i;j<mst.length;j++)if(mst[j].weight<minweight){minweight=mst[j].weight;min=j;}Edgetemp=mst[i];mst[i]=mst[min];mst[min]=temp;inttv=mst[i].dest;for(intj=i+1;j<mst.length;j++){intv=mst[j].dest;if(this.getWeight(tv,v)<mst[j].weight){mst[i].weight=this.getWeight(tv,v);mst[j].start=tv;}}}System.out.print("\n最小生成树边的集合:");intmincost=0;for(inti=0;i<mst.length-1;i++){System.out.print(mst[i]+"");mincost+=mst[i].weight;}System.out.print(",最小代价为"+mincost);}}AdjMatrixGraph.javapackageFrist;publicclassAdjMatrixGraph<T>extendsAbstractGraph<T>{protectedSeqList<T>vertexlist;protectedint[][]adjmatrix;privatefinalint99999;publicAdjMatrixGraph(intsize){size=size<10?10:size;this.vertexlist=newSeqList<T>(size);this.adjmatrix=newint[size][size];for(inti=0;i<size;i++)for(intj=0;j<size;j++)this.adjmatrix[i][j]=(i==j)?0:}publicAdjMatrixGraph(T[]vertices,Edge[]edges){this(vertices.length);if(vertices==null)return;for(inti=0;i<vertices.length;i++)insertVertex(vertices[i]);if(edges!=null)for(intj=0;j<edges.length;j++)insertEdge(edges[j]);}publicvoidinsertEdge(inti,intj,intweight){intn=this.vertexCount();if(i>0&&i<n&&j>=0&&j<n&&i!=j&&this.adjmatrix[i][j]==this.adjmatrix[i][j]=weight;}publicvoidinsertEdge(Edgeedge){this.insertEdge(edge.start,edge.dest,edge.weight);}publicintinsertVertex(Tx){this.vertexlist.append(x);if(this.vertexCount()>this.adjmatrix.length){inttemp[][]=adjmatrix,i,j;this.adjmatrix=newint[temp.length*2][temp.length*2];for(i=0;i<temp.length;i++){for(j=0;j<temp.length;j++)this.adjmatrix[i][j]=temp[i][j];for(j=temp.length;j<temp.length*2;j++)this.adjmatrix[i][j]=}for(i=temp.length;i<temp.length*2;i++)for(j=0;j<temp.length*2;j++)this.adjmatrix[i][j]=(i==j)?0:}returnthis.vertexlist.length()-1;}publicintvertexCount(){returnthis.vertexlist.length();}publicTget(inti){returnthis.vertexlist.get(i);}publicintgetWeight(inti,intj){returnthis.adjmatrix[i][j];}publicStringtoString(){Stringstr="顶点集合："+this.vertexlist.toString()+"\n邻接矩阵：\n";intn=this.vertexCount();for(inti=0;i<n;i++){for(intj=0;j<n;j++)str+=this.adjmatrix[i][j]=="∞":""+this.adjmatrix[i][j];str+="\n";}returnstr;}publicvoidremoveEdge(inti,intj){if(i>=0&&i<vertexCount()&&j>=0&&j<vertexCount()&&i!=j)this.adjmatrix[i][j]=}publicvoidremoveVertex(inti){intn=this.vertexCount();if(i<0||i>n)return;this.vertexlist.remove(i);for(intj=0;j<i;j++)for(intk=i+1;k<n;k++)this.adjmatrix[j][k-1]=this.adjmatrix[j][k];for(intj=i+1;j<n;j++)for(intk=0;k<i;k++)this.adjmatrix[j-1][k]=adjmatrix[j][k];for(intj=i+1;j<n;j++)for(intk=i+1;k<n;k++)this.adjmatrix[j-1][k-1]=this.adjmatrix[j][k];}@OverridepublicintgetNextNeighbor(inti,intj){intn=this.vertexCount();if(i>=0&&i<n&&j>=-1&&j<n&&i!=j)for(intk=j+1;k<n;k++)if(this.adjmatrix[i][k]>0&&this.adjmatrix[i][k]<returnk;return-1;}}Edge.javapackageFrist;publicclassEdgeimplementsComparable<Edge>{publicintstart,dest,weight;publicEdge(intstart,intdest,intweight){super();this.start=start;this.dest=dest;this.weight=weight;}publicStringtoString(){return"("+start+","+dest+","+weight+")";}publicintcompareTo(Edgee){if(this.start!=e.start)returnthis.start=e.start;returnthis.dest=e.dest;}}运行结果:Test2代码;GraphT2.javapackageSecond;publicclassGraphT2{publicstaticvoidmain(String[]args){Graphgraph=newGraph(9);graph.add("1");graph.add("2");graph.add("3");graph.add("4");graph.add("5");graph.add("6");graph.add("7");graph.add("8");graph.add("9");graph.addEdge(0,1,6);graph.addEdge(0,2,4);graph.addEdge(0,3,5);graph.addEdge(1,4,1);graph.addEdge(2,4,1);graph.addEdge(3,5,2);graph.addEdge(4,6,9);graph.addEdge(4,7,7);graph.addEdge(5,7,4);graph.addEdge(6,8,2);graph.addEdge(7,8,4);if(graph.topo()){graph.calculate();int[]e=graph.getE();int[]l=graph.getL();int[]key=graph.getKey();int[]ve=graph.getVE();int[]vl=graph.getVl();System.out.println("事件的最早发生时间：");for(intw=0;w<ve.length;w++){System.out.print(ve[w]+"");}System.out.println();System.out.println("事件的最晚发生时间：");for(intw=0;w<vl.length;w++){System.out.print(vl[w]+"");}System.out.println();System.out.println("活动的最早发生时间：");for(intw=0;w<e.length;w++){System.out.print(e[w]+"");}System.out.println();System.out.println("活动的最迟发生时间：");for(intw=0;w<l.length;w++){System.out.print(l[w]+"");}System.out.println();System.out.println("关键活动有：");for(intw=0;w<graph.getKNum();w++){System.out.print(key[w]+"");}System.out.println();}}}Graph.javapackageSecond;publicclassGraph{privateVertex[]vertexs;privateLink[]adjTab;privateintpos=-1;privateStackstack;privateStackrestack;privateStackbackstack;privateintvertexNum;privateNodestart;privateintedgeCount;privateintprivateint[]ve;privateint[]vl;privateint[]e;privateint[]l;privateint[]key;publicintcacuTotalTime(){NodecurrNode=adjTab[0].head();intcurrNodeNum=0;booleanisSameLink=false;intcurrKeyNum=0;inttotalTime=0;for(intcurrLink=0;currLink<adjTab.length-1;){currNode=currNode.getNext();if(key[currKeyNum]==currNodeNum&&(!isSameLink)){totalTime+=currNode.getWeight();currKeyNum++;isSameLink=true;if((Integer)currNode.getData()==(adjTab.length-1))break;}elseif(key[currKeyNum]==currNodeNum&&isSameLink){currKeyNum++;}currNodeNum++;if(currNode.getNext()==null){currLink++;if(currLink<adjTab.length-1){currNode=adjTab[currLink].head();isSameLink=false;}}}returntotalTime;}publicStringgetVertexValue(inti){return(String)vertexs[i].value();}publicGraph(intsize){vertexNum=size;vertexs=newVertex[size];adjTab=newLink[size];stack=newStack(size);restack=newStack(size);backstack=newStack(size);for(inti=0;i<size;i++){adjTab[i]=newLink(i);}ve=newint[size];vl=newint[size];for(intd=0;d<size;d++){vl[d]=-1;}edgeCount=0;}voidadd(Objectobj){assertpos<vertexs.length;vertexs[++pos]=newVertex(obj);}voidaddEdge(intfrom,intto,intweight){adjTab[from].addtail(to,weight);vertexs[to].in++;edgeCount++;}booleantopo(){intcount=0;for(inti=0;i<vertexNum;i++){if(vertexs[i].in==0){stack.push(i);start=adjTab[i].head();}}while(!stack.isEmpty()){restack.push(stack.peek());intj=stack.pop();count++;Nodep=adjTab[j].head();Nodeearlyest=p;intpreweight=ve[j];while(p!=null){intk=((Integer)p.getData()).intValue();vertexs[k].in--;if(vertexs[k].in==0)stack.push(k);p=p.getNext();if(p!=null){inttemp=((Integer)p.getData()).intValue();if(p.getWeight()+preweight>ve[temp]){ve[temp]=p.getWeight()+preweight;}}}}if(count<vertexNum){System.out.println("有回路，无法得到关键路径！");returnfalse;}returntrue;}publicvoidcalculate(){ints=0;intt=0;e=newint[edgeCount];l=newint[edgeCount];key=newint[edgeCount];backstack.push(restack.peek());intz=restack.pop();vl[z]=ve[z];while(!restack.isEmpty()){backstack.push(restack.peek());intq=restack.pop();Nodevertex=adjTab[q].head();for(intk=0;k<backstack.getCount();k++){Nodever=vertex;while(ver.getNext()!=null){if(((Integer)ver.getNext().getData()).intValue()==backstack.getElement(k)){intyuanxian=vl[((Integer)vertex.getData()).intValue()];intjiangyao=vl[backstack.getElement(k)]-ver.getNext().getWeight();if(jiangyao<yuanxian||yuanxian==-1){vl[((Integer)vertex.getData()).intValue()]=vl[backstack.getElement(k)]-ver.getNext().getWeight();}}ver=ver.getNext();}}}for(inth=0;h<vertexNum;h++){Nodebegin=adjTab[h].head();Nodebackbegin=begin;if(begin!=null){while(begin.getNext()!=null){e[s++]=ve[((Integer)backbegin.getData()).intValue()];l[t++]=vl[((Integer)begin.getNext().getData()).intValue()]-begin.getNext().getWeight();begin=begin.getNext();}}}kNum=0;for(intw=0;w<e.length;w++){if(l[w]-e[w]<=0){key[=w;}}}publicint[]getVE(){returnve;}publicint[]getVl(){returnvl;}publicint[]getE(){returne;}publicint[]getL(){returnl;}publicint[]getKey(){returnkey;}publicintgetKNum(){return}}Link.javapackageSecond;publicclassLink{privateNodehead;privateintlength;publicLink(intindex){head=newNode(index,null,0);length=0;}publicvoidaddhead(Objectitem,intweight){Nodenode=newNode(item,null,weight);node.setNext(head.getNext());head.setNext(node);length++;}publicvoidaddtail(Objectitem,intweight){Nodenode=newNode(item,null,weight);Nodetemp=head;while(null!=temp.getNext()){temp=temp.getNext();}temp.setNext(node);length++;}publicNodehead(){returnhead;}publicvoidfind(intindex){if(index<1||index>length){System.out.print("此位置空！");}Nodetemp=head;for(inti=0