實驗7 圖及圖的操作實驗

1、實驗報告七 圖及圖的操作實驗班級： 姓名： 學號： 專業(yè)： 一、 實驗目的：1、掌握圖的基本概念和術(shù)語2、掌握圖的存儲結(jié)構(gòu)及創(chuàng)建算法。3、掌握圖的遍歷算法（遞歸或非遞歸算法）。二、 實驗內(nèi)容：1、圖鄰接矩陣存儲結(jié)構(gòu)表示及基本操作算法實現(xiàn)（1）鄰接矩陣存儲結(jié)構(gòu)類定義：自定義如下：package Ex7.Ex7_1;import Ex5.Ex5_1.Matrix;import Ex7.Triple;import java.util.List;/* * Created by 74062 on 2017/5/17. */public class MatrixGraph private Matrix m

2、atrix; private List vertxList; private static final int MAX_WEIGHT = 0x0000ffff; private int size; public MatrixGraph(Triple TripleArray, List vertxList ) this.matrix = new Matrix(vertxList.size(),vertxList.size(); this.vertxList = vertxList; for(Triple triple:TripleArray) insertEdge(triple); size =

3、 vertxList.size(); public MatrixGraph(List vertxList) this.matrix = new Matrix(vertxList.size(),vertxList.size(); size = vertxList.size(); this.vertxList = vertxList; public void insertEdge(int i,int j, int weight) if(i=j) throw new IllegalArgumentException(不能插入自身環(huán)); if(weightMAX_WEIGHT) weight = MA

4、X_WEIGHT; this.matrix.setElement(i,j,weight); public void insertEdge(Triple triple) insertEdge(triple.getRow(),triple.getColumn(),triple.getweigth(); public void insertVertex(E x) this.vertxList.add(x); if(size = matrix.getRow() ExtendMatrix(); for(int j=0;j=size;j+) matrix.setElement(size,j,MAX_WEI

5、GHT); matrix.setElement(j,size,MAX_WEIGHT); size+; public void removeEdge(int i,int j) if(i=j) throw new IllegalArgumentException(i不能等于j); this.matrix.setElement(i,j,MAX_WEIGHT); public void removeVertex(int i) if(i=vertxList.size() throw new IllegalArgumentException(i超出范圍); int n= vertxList.size();

6、 vertxList.remove(i); for(int j=i+1;jn;j+) for(int k=0;kn;k+) matrix.setElement(j-1,k,matrix.getElement(j,k); for(int j=0;jn;j+) for(int k=i+1;k=0&i=-1&jn&i!=j) for(int k=j+1;k0&matrix.getElement(i,k)MAX_WEIGHT) return k; return -1; private void ExtendMatrix() Matrix matrix = new Matrix(this.matrix.

7、getRow()+4,this.matrix.getRow()+4); for(int i=0;ithis.matrix.getRow();i+) for(int j=0;jthis.matrix.getColumn();j+) matrix.setElement(i, j, this.matrix.getElement(i,j); this.matrix = matrix; Override public String toString() String string = ; for(int i=0;isize;i+) string += vertxList.get(i)+ ; for(in

8、t j=0;jsize;j+) string += matrix.getElement(i,j)+ ; string +=n; return string; （2）創(chuàng)建鄰接矩陣算法public MatrixGraph(Triple TripleArray, List vertxList ) this.matrix = new Matrix(vertxList.size(),vertxList.size(); this.vertxList = vertxList; for(Triple triple:TripleArray) insertEdge(triple); size = vertxLis

9、t.size();public MatrixGraph(List vertxList) this.matrix = new Matrix(vertxList.size(),vertxList.size(); size = vertxList.size(); this.vertxList = vertxList;（3）輸出鄰接矩陣結(jié)果算法public String toString() String string = ; for(int i=0;isize;i+) string += vertxList.get(i)+ ; for(int j=0;jsize;j+) string += matr

10、ix.getElement(i,j)+ ; string +=n; return string;測試結(jié)果粘貼如下：2、圖鄰接表存儲結(jié)構(gòu)表示及基本操作算法實現(xiàn)（1）鄰接表存儲結(jié)構(gòu)類定義：自定義如下：package Ex7.Ex7_2;import Ex2.Ex2_1.MyList;import Ex5.Ex5_2.Element;import Ex5.Ex5_2.LinkedMatrix;import Ex5.Ex5_2.LinkedMatrixRow;import Ex7.Triple;import java.util.ArrayList;import java.util.Iterator;i

11、mport java.util.List;import java.util.Queue;import java.util.concurrent.LinkedBlockingQueue;/* * Created by 74062 on 2017/5/31. */public class AdjListGraph protected LinkedMatrix adjlist; private List vertxList; private static final int MAX_WEIGHT = 0x0000ffff; private int size; public AdjListGraph(

12、int length) vertxList = new ArrayList(length); adjlist = new LinkedMatrix(length,length); size = vertxList.size(); public AdjListGraph(Triple TripleArray, List vertxList ) this.adjlist = new LinkedMatrix(vertxList.size(),vertxList.size(); this.vertxList = vertxList; for(Triple triple:TripleArray) in

13、sertEdge(triple.getRow(),triple.getColumn(),triple.getweigth(); size = vertxList.size(); public void insertEdge(int i,int j,int weight) if(i=j) throw new IllegalArgumentException(i,j不能相等); if(weight=MAX_WEIGHT) weight=0; adjlist.setElement(i,j,weight); public void insertVertex(E x) vertxList.add(x);

14、 int i = vertxList.size(); if(vertxList.size()adjlist.getRow() adjlist.setRow(i+1); adjlist.setColumn(i+1); adjlist.addLine(); size+; public void removeEdge(int i,int j) if(i=j) throw new IllegalArgumentException(i,j不能相等); adjlist.setElement(i,j,0); Override public String toString() StringBuffer str

15、ingBuffer = new StringBuffer(); for(int i=0;ivertxList.size();i+) LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i); Iterator iterator = linkedMatrixRow.iterator(); stringBuffer.append(vertxList.get(i)+ ); while (iterator.hasNext() Element element = iterator.next(); stringBuffer.append(+i+,) .

16、append(element.getColumn()+,).append(element.getValue()+); stringBuffer.append(n); return stringBuffer.toString(); public void removeVertex(int i) if(ivertxList.size() throw new IllegalArgumentException(i超出范圍); int n = vertxList.size(); LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i); Iterat

17、or it = linkedMatrixRow.iterator(); while (it.hasNext() Element element = it.next(); removeEdge(i,element.getColumn(); n-; adjlist.setRow(n); adjlist.setColumn(n); for(int j=0;jadjlist.getRow();j+) LinkedMatrixRow tempLinkedMatrixRow = adjlist.getRowLine(i); Iterator tempIt = tempLinkedMatrixRow.ite

18、rator(); while (tempIt.hasNext() Element element = it.next(); removeEdge(i,element.getColumn(); vertxList.remove(i); size-; private int next(int i,int j) int n = vertxList.size(); if(i=0&i=-1&jn&i!=j) LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i); Iterator iterator = linkedMatrixRow.iterat

19、or(); if(j=-1) return iterator.hasNext()?iterator.next().getColumn():-1; MyList.Node node = linkedMatrixRow.getNodeByColumn(j); if(node!=null) node = node.next; if(node!=null) return node.data.getColumn(); return -1; public void DFSTraverse(int i) boolean visited = new booleanvertxList.size(); int j

20、=i; do if(!visitedj) System.out.print(); this.depthfs(j,visited); System.out.print(); j = (j+1)%vertxList.size(); while (j!=i); System.out.println(); private void depthfs(int i,boolean visited) System.out.print(vertxList.get(i)+ ); visitedi = true; int j = this.next(i,-1); while (j!=-1) if(!visitedj

21、) depthfs(j,visited); j=this.next(i,j); public void BFSTraverse(int i) boolean visited = new booleanvertxList.size(); int j = i; do if(!visitedj) System.out.print(); breadthfs(j,visited); System.out.print(); j = (j+1)%vertxList.size(); while (j!=i); System.out.println(); public void breadthfs(int i,

22、 boolean visited) System.out.print(vertxList.get(i)+ ); visitedi = true; Queue queue = new LinkedBlockingQueue(); queue.add(i); while (!queue.isEmpty() i = queue.poll(); for(int j=next(i,-1);j!=-1;j=next(i,j) if(!visitedj) System.out.print(vertxList.get(j)+ ); visitedj = true; queue.add(j); （2）創(chuàng)建鄰接表

23、算法public AdjListGraph(int length) vertxList = new ArrayList(length); adjlist = new LinkedMatrix(length,length); size = vertxList.size();public AdjListGraph(Triple TripleArray, List vertxList ) this.adjlist = new LinkedMatrix(vertxList.size(),vertxList.size(); this.vertxList = vertxList; for(Triple t

24、riple:TripleArray) insertEdge(triple.getRow(),triple.getColumn(),triple.getweigth(); size = vertxList.size();（3）輸出鄰接表結(jié)果算法Overridepublic String toString() StringBuffer stringBuffer = new StringBuffer(); for(int i=0;ivertxList.size();i+) LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i); Iterato

25、r iterator = linkedMatrixRow.iterator(); stringBuffer.append(vertxList.get(i)+ ); while (iterator.hasNext() Element element = iterator.next(); stringBuffer.append(+i+,) .append(element.getColumn()+,).append(element.getValue()+); stringBuffer.append(n); return stringBuffer.toString();測試結(jié)果粘貼如下：3、圖的遍歷遞歸算法（1）（存儲結(jié)構(gòu)為鄰接表）深度優(yōu)先遍歷算法遞歸算法：public void DFSTraverse(int i) boolean visited = new booleanvertxList.size(); int j=i; do if(!visitedj) System.out.print(); this.depthfs(j,visited); System.out.print(); j = (j+1)%vertxList.siz