实验7图及图的操作实验Word版

传播优秀Word版文档 ，希望对您有帮助，可双击去除！实验报告七 图及图的操作实验班级： 姓名： 学号： 专业： 一、 实验目的：1、掌握图的基本概念和术语2、掌握图的存储结构及创建算法。3、掌握图的遍历算法（递归或非递归算法）。二、 实验内容：1、图邻接矩阵存储结构表示及基本操作算法实现（1）邻接矩阵存储结构类定义：自定义如下：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 matrix; 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 = vertxList.size(); public MatrixGraph(List vertxList) this.matrix = new Matrix(vertxList.size(),vertxList.size(); size = vertxList.size(); this.vertxList = vertxList; 传播优秀Word版文档 ，希望对您有帮助，可双击去除！public void insertEdge(int i,int j, int weight) if(i=j) throw new IllegalArgumentException(不能插入自身环); if(weightMAX_WEIGHT) weight = MAX_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_WEIGHT); 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(); 传播优秀Word版文档 ，希望对您有帮助，可双击去除！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.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 传播优秀Word版文档 ，希望对您有帮助，可双击去除！public String toString() String string = ; for(int i=0;isize;i+) string += vertxList.get(i)+ ; for(int j=0;jsize;j+) string += matrix.getElement(i,j)+ ; string +=n; return string; （2）创建邻接矩阵算法public MatrixGraph(Triple TripleArray, List vertxList ) this.matrix = new Matrix(vertxList.size(),vertxList.size(); this.vertxList = vertxList; for(Triple triple:TripleArray) insertEdge(triple); size = vertxList.size();public MatrixGraph(List vertxList) this.matrix = new Matrix(vertxList.size(),vertxList.size(); size = vertxList.size(); this.vertxList = vertxList;（3）输出邻接矩阵结果算法public String toString() String string = ; for(int i=0;isize;i+) string += vertxList.get(i)+ ; 传播优秀Word版文档 ，希望对您有帮助，可双击去除！for(int j=0;jsize;j+) string += matrix.getElement(i,j)+ ; string +=n; return string;测试结果粘贴如下：2、图邻接表存储结构表示及基本操作算法实现（1）邻接表存储结构类定义：传播优秀Word版文档 ，希望对您有帮助，可双击去除！自定义如下：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;import 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(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) insertEdge(triple.getRow(),triple.getColumn(),triple.getweigth(); 传播优秀Word版文档 ，希望对您有帮助，可双击去除！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); 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 stringBuffer = new StringBuffer(); for(int i=0;ivertxList.size();i+) LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i); Iterator iterator = linkedMatrixRow.iterator(); stringBuffer.append(传播优秀Word版文档 ，希望对您有帮助，可双击去除！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(); public void removeVertex(int i) if(ivertxList.size() throw new IllegalArgumentException(i超出范围); int n = vertxList.size(); LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i); Iterator 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.iterator(); while (tempIt.hasNext() Element element = it.next(); removeEdge(i,element.getColumn(); 传播优秀Word版文档 ，希望对您有帮助，可双击去除！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.iterator(); 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=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(); 传播优秀Word版文档 ，希望对您有帮助，可双击去除！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) 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, 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); 传播优秀Word版文档 ，希望对您有帮助，可双击去除！（2）创建邻接表算法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 triple:TripleArray) insertEdge(triple.getRow(),triple.getColumn(),triple.getweigth(); size = vertxList.size();（3）输出邻接表结果算法Overridepublic String toString() StringBuffer stringBuffer = 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+,) .append(element.getColumn()+,).append(element.getValue()+); stringBuffer.append(传播优秀Word版文档 ，希望对您有帮助，可双击去除！n); return stringBuffer.toString();测试结果粘贴如下：3、图的遍历递归算法（1）（存储结构为邻接表）深度优先遍历算法递归算法：public void DFSTraverse(int i) boolean visited = new booleanvertxList.size(); 传播优秀Word版文档 ，希望对您有帮助，可双击去除！int j=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) depthfs(j,visited); j=this.next(i,j); 测试结果粘贴如下：（2）广度优先遍历算法非递归算法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();传播优秀Word版文档 ，希望对您有帮助，可双击去除！public void breadthfs(int i, 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); 测试结果粘贴如下：三、 实验心得（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得）四、 五、 六、七、 八、九、