实验7 图与图的操作实验
《实验7 图与图的操作实验》由会员分享，可在线阅读，更多相关《实验7 图与图的操作实验（12页珍藏版）》请在装配图网上搜索。
1、 .wd.实验报告七图及图的操作实验班级：姓名：学号： 专业：一、 实验目的：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 ma
2、trix; 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(不能插入自身环); if(weightMAX_WEIGHT) weight = MAX
4、_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_WEIG
5、HT); 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.g
7、etRow()+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(int
8、 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.s
9、ize();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)+ ; for(int j=0;jsize;j+) string += matrix.ge
10、tElement(i,j)+ ; string +=n; return string;测试结果粘贴如下：2、图邻接表存储构造表示及 根本操作算法实现1邻接表存储构造类定义：自定义如下：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
11、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 le
12、ngth) 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) insertEd
13、ge(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); int i
14、 = 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 stringBuf
15、fer = 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
16、(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
17、= 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(
18、); 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.iterator();
19、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
20、 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) dept
21、hfs(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, boole
22、an 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创立邻接表算法public
23、 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:Tr
24、ipleArray) 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
25、 = 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();测试结果粘贴如下：3、图的遍历递归算法1存储构造为邻
26、接表深度优先遍历算法递归算法：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();private void depthfs(int i,boolean visited) System.ou
27、t.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,vi
28、sited); 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); 测试结果粘贴如下：三、 实验心得含上机中所遇问题的解决方法，所使用到的编程技巧、创新点及编程的心得
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
