武漢紡織大學(xué)《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告3

XX紡織大學(xué)《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告班級：管工類專業(yè)班XX：序號：實(shí)驗(yàn)時(shí)間：2014年5月16日指導(dǎo)教師：實(shí)驗(yàn)三：圖的基本操作與應(yīng)用一、實(shí)驗(yàn)?zāi)康模?、掌握圖的幾種主要存儲方法及基本操作、掌握圖的兩種遍歷方法、掌握利用普里姆算法和克魯斯卡爾算法求取最小生成樹的方法

、掌握求取AOE網(wǎng)關(guān)鍵路徑的方法，以實(shí)現(xiàn)項(xiàng)目時(shí)間管理二、實(shí)驗(yàn)內(nèi)容：、編寫程序，輸出圖的鄰接矩陣，輸出兩種遍歷序列，并求出最小生成樹。實(shí)驗(yàn)步驟：①、在Java語言編輯環(huán)境中新建程序，輸入頂點(diǎn)集合和邊集合，構(gòu)造一個(gè)圖7-15所示的帶權(quán)圖，可參考書本225頁示例程序；②、對該帶權(quán)圖，進(jìn)行插入頂點(diǎn)、插入邊、刪除頂點(diǎn)、刪除邊操作，并輸出操作后的鄰接矩陣，可參考書本226-228頁示例程序；③、輸出從頂點(diǎn)'A'開始的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的序列，可參考書本、240頁示例程序；可參考書本245頁示例程序。、設(shè)計(jì)一個(gè)程序求出完成整項(xiàng)工程至少需要多少時(shí)間以及整項(xiàng)工程中的關(guān)鍵活動。實(shí)驗(yàn)步驟：①、在Java語言編輯環(huán)境中新建程序，輸入如下圖所示的AOE網(wǎng)；求出各個(gè)頂點(diǎn)的最早開始時(shí)間和最遲開始時(shí)間；③、求出各個(gè)活動的最早開始時(shí)間和最遲開始時(shí)間；④、找出該AOE網(wǎng)的關(guān)鍵路徑，并計(jì)算出該項(xiàng)目的完成時(shí)間。關(guān)鍵路徑相關(guān)時(shí)間設(shè)ai由弧<j,k>(即從頂點(diǎn)j到k)表示，其持時(shí)間為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為弧尾的弧的集合。求關(guān)鍵路徑的算法：①、輸e條弧<j,k>，建立AOE網(wǎng)的存儲結(jié)；②、從起始點(diǎn)出發(fā)，令ve[0]=0，按拓?fù)漤樞蚯笃溆喔黜旤c(diǎn)的最早發(fā)時(shí)間ve[i](1<=i<=n-1)。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止，否則到步③；vn出發(fā)，令vl[n-1]=ve[n-1]發(fā)時(shí)間vl[i](n-2>=i>=0)；④、根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開始時(shí)間e(s)和最遲開始時(shí)間l(s)。若某弧滿足條，則為關(guān)鍵三、操作步：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("帶權(quán)無向圖,"+graph.toString());System.out.println("插入頂點(diǎn)F,插入邊(A,F,20),刪除頂點(diǎn)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("深度優(yōu)先遍歷序列為：");graph1.DFSTraverse(0);System.out.print("廣度優(yōu)先遍歷序列為：");graph1.BFSTraverse(0);AdjMatrixGraph<String>graph2=newAdjMatrixGraph<String>(vertices,edges);System.out.print("帶權(quán)無向圖,"+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(",最小代價(jià)為"+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="頂點(diǎn)集合："+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;}}運(yùn)行結(jié)果: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("事件的最早發(fā)生時(shí)間：");for(intw=0;w<ve.length;w++){System.out.print(ve[w]+"");}System.out.println();System.out.println("事件的最晚發(fā)生時(shí)間：");for(intw=0;w<vl.length;w++){System.out.print(vl[w]+"");}System.out.println();System.out.println("活動的最早發(fā)生時(shí)間：");for(intw=0;w<e.length;w++){System.out.print(e[w]+"");}System.out.println();System.out.println("活動的最遲發(fā)生時(shí)間：");for(intw=0;w<l.length;w++){System.out.print(l[w]+"");}System.out.println();System.out.println("關(guān)鍵活動有：");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("有回路，無法得到關(guān)鍵路徑！");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