实验7 图及图的操作实验.docx
- 文档编号:13076534
- 上传时间:2023-06-10
- 格式:DOCX
- 页数:17
- 大小:70.13KB
实验7 图及图的操作实验.docx
《实验7 图及图的操作实验.docx》由会员分享,可在线阅读,更多相关《实验7 图及图的操作实验.docx(17页珍藏版)》请在冰点文库上搜索。
实验7图及图的操作实验
实验报告七图及图的操作实验
班级:
姓名:
学号:
专业:
一、实验目的:
1、掌握图的基本概念和术语
2、掌握图的存储结构及创建算法。
3、掌握图的遍历算法(递归或非递归算法)。
二、实验内容:
1、图邻接矩阵存储结构表示及基本操作算法实现
(1)邻接矩阵存储结构类定义:
自定义如下:
packageEx7。
Ex7_1;
importEx5.Ex5_1。
Matrix;
importEx7。
Triple;
importjava.util。
List;
/**
*Createdby74062on2017/5/17.
*/
publicclassMatrixGraph〈E>{
privateMatrixmatrix;
privateList
privatestaticfinalintMAX_WEIGHT=0x0000ffff;
privateintsize;
publicMatrixGraph(Triple[]TripleArray,List〈E〉vertxList){
this.matrix=newMatrix(vertxList.size(),vertxList。
size());
this。
vertxList=vertxList;
for(Tripletriple:
TripleArray){
insertEdge(triple);
}
size=vertxList.size();
}
publicMatrixGraph(List
this.matrix=newMatrix(vertxList。
size(),vertxList。
size());
size=vertxList。
size();
this.vertxList=vertxList;
}
publicvoidinsertEdge(inti,intj,intweight){
if(i==j){
thrownewIllegalArgumentException("不能插入自身环");
}
if(weight〈0||weight>MAX_WEIGHT)
weight=MAX_WEIGHT;
this。
matrix.setElement(i,j,weight);
}
publicvoidinsertEdge(Tripletriple){
insertEdge(triple。
getRow(),triple。
getColumn(),triple.getweigth());
}
publicvoidinsertVertex(Ex){
this.vertxList。
add(x);
if(size==matrix。
getRow()){
ExtendMatrix();
}
for(intj=0;j<=size;j++){
matrix.setElement(size,j,MAX_WEIGHT);
matrix。
setElement(j,size,MAX_WEIGHT);
}
size++;
}
publicvoidremoveEdge(inti,intj){
if(i==j){
thrownewIllegalArgumentException(”i不能等于j”);
}
this。
matrix.setElement(i,j,MAX_WEIGHT);
}
publicvoidremoveVertex(inti){
if(i〈0||i〉=vertxList。
size()){
thrownewIllegalArgumentException(”i超出范围");
}
intn=vertxList.size();
vertxList。
remove(i);
for(intj=i+1;j〈n;j++){
for(intk=0;k〈n;k++){
matrix。
setElement(j-1,k,matrix.getElement(j,k));
}
}
for(intj=0;j〈n;j++){
for(intk=i+1;k matrix.setElement(j,k—1,matrix。 getElement(j,k)); } } size--; } privateintnext(inti,intj){ intn=vertxList.size(); if(i>=0&&i =j){ for(intk=j+1;k if(matrix.getElement(i,k)>0&&matrix。 getElement(i,k) returnk; } } return—1; } privatevoidExtendMatrix(){ Matrixmatrix=newMatrix(this.matrix。 getRow()+4,this.matrix.getRow()+4); for(inti=0;i getRow();i++){ for(intj=0;j〈this。 matrix.getColumn();j++){ matrix。 setElement(i,j,this.matrix.getElement(i,j)); } } this。 matrix=matrix; } @Override publicStringtoString(){ Stringstring="”; for(inti=0;i〈size;i++){ string+=vertxList。 get(i)+""; for(intj=0;j string+=matrix。 getElement(i,j)+""; } string+="\n"; } returnstring; } } (2)创建邻接矩阵算法 publicMatrixGraph(Triple[]TripleArray,List〈E〉vertxList){ this。 matrix=newMatrix(vertxList。 size(),vertxList.size()); this。 vertxList=vertxList; for(Tripletriple: TripleArray){ insertEdge(triple); } size=vertxList.size(); } publicMatrixGraph(List〈E>vertxList){ this。 matrix=newMatrix(vertxList.size(),vertxList。 size()); size=vertxList.size(); this。 vertxList=vertxList; } (3)输出邻接矩阵结果算法 publicStringtoString(){ Stringstring=""; for(inti=0;i〈size;i++){ string+=vertxList.get(i)+""; for(intj=0;j string+=matrix。 getElement(i,j)+"”; } string+=”\n”; } returnstring; } 测试结果粘贴如下: 2、图邻接表存储结构表示及基本操作算法实现 (1)邻接表存储结构类定义: 自定义如下: packageEx7.Ex7_2; importEx2。 Ex2_1。 MyList; importEx5。 Ex5_2。 Element; importEx5。 Ex5_2。 LinkedMatrix; importEx5.Ex5_2。 LinkedMatrixRow; importEx7.Triple; importjava。 util.ArrayList; importjava。 util。 Iterator; importjava。 util。 List; importjava。 util.Queue; importjava。 util.concurrent.LinkedBlockingQueue; /** *Createdby74062on2017/5/31。 */ publicclassAdjListGraph〈E>{ protectedLinkedMatrix privateList privatestaticfinalintMAX_WEIGHT=0x0000ffff; privateintsize; publicAdjListGraph(intlength){ vertxList=newArrayList〈E〉(length); adjlist=newLinkedMatrix(length,length); size=vertxList。 size(); } publicAdjListGraph(Triple[]TripleArray,List this。 adjlist=newLinkedMatrix〈Element>(vertxList.size(),vertxList。 size()); this.vertxList=vertxList; for(Tripletriple: TripleArray){ insertEdge(triple.getRow(),triple。 getColumn(),triple.getweigth()); } size=vertxList。 size(); } publicvoidinsertEdge(inti,intj,intweight){ if(i==j){ thrownewIllegalArgumentException("i,j不能相等”); } if(weight<0||weight〉=MAX_WEIGHT) weight=0; adjlist.setElement(i,j,weight); } publicvoidinsertVertex(Ex){ vertxList.add(x); inti=vertxList.size(); if(vertxList。 size()>adjlist.getRow()){ adjlist。 setRow(i+1); adjlist。 setColumn(i+1); } adjlist。 addLine(); size++; } publicvoidremoveEdge(inti,intj){ if(i==j){ thrownewIllegalArgumentException("i,j不能相等"); } adjlist。 setElement(i,j,0); } @Override publicStringtoString(){ StringBufferstringBuffer=newStringBuffer(); for(inti=0;i size();i++){ LinkedMatrixRowlinkedMatrixRow=adjlist。 getRowLine(i); Iterator Element〉iterator=linkedMatrixRow.iterator(); stringBuffer。 append(vertxList.get(i)+””); while(iterator。 hasNext()){ Elementelement=iterator。 next(); stringBuffer.append(”(”+i+”,”) 。 append(element.getColumn()+”,")。 append(element.getValue()+")"); } stringBuffer。 append("\n”); } returnstringBuffer.toString(); } publicvoidremoveVertex(inti){ if(i<0||i〉vertxList。 size()){ thrownewIllegalArgumentException("i超出范围”); } intn=vertxList.size(); LinkedMatrixRowlinkedMatrixRow=adjlist。 getRowLine(i); Iterator〈Ex5.Ex5_2.Element〉it=linkedMatrixRow。 iterator(); while(it。 hasNext()){ Elementelement=it。 next(); removeEdge(i,element。 getColumn()); } n-—; adjlist.setRow(n); adjlist.setColumn(n); for(intj=0;j getRow();j++){ LinkedMatrixRowtempLinkedMatrixRow=adjlist.getRowLine(i); Iterator iterator(); while(tempIt。 hasNext()){ Elementelement=it.next(); removeEdge(i,element.getColumn()); } } vertxList。 remove(i); size——; } privateintnext(inti,intj){ intn=vertxList。 size(); if(i〉=0&&i〈n&&j>=—1&&j =j){ LinkedMatrixRowlinkedMatrixRow=adjlist。 getRowLine(i); Iterator iterator(); if(j==-1) returniterator。 hasNext()? iterator。 next()。 getColumn(): -1; MyList.Node getNodeByColumn(j); if(node! =null){ node=node.next; if(node! =null) returnnode。 data。 getColumn(); } } return—1; } publicvoidDFSTraverse(inti){ boolean[]visited=newboolean[vertxList.size()]; intj=i; do{ if(! visited[j]){ System。 out.print(”{”); this。 depthfs(j,visited); System.out。 print("}"); } j=(j+1)%vertxList.size(); }while(j! =i); System。 out.println(); } privatevoiddepthfs(inti,boolean[]visited){ System。 out.print(vertxList。 get(i)+””); visited[i]=true; intj=this.next(i,-1); while(j! =-1){ if(! visited[j]) depthfs(j,visited); j=this.next(i,j); } } publicvoidBFSTraverse(inti){ boolean[]visited=newboolean[vertxList.size()]; intj=i; do{ if(! visited[j]){ System。 out。 print("{"); breadthfs(j,visited); System。 out.print("}"); } j=(j+1)%vertxList。 size(); }while(j! =i); System.out。 println(); } publicvoidbreadthfs(inti,boolean[]visited){ System。 out.print(vertxList.get(i)+”"); visited[i]=true; Queue〈Integer〉queue=newLinkedBlockingQueue〈Integer>(); queue。 add(i); while(! queue.isEmpty()){ i=queue.poll(); for(intj=next(i,-1);j! =—1;j=next(i,j)){ if(! visited[j]){ System。 out。 print(vertxList.get(j)+””); visited[j]=true; queue.add(j); } } } } } (2)创建邻接表算法 publicAdjListGraph(intlength){ vertxList=newArrayList adjlist=newLinkedMatrix(length,length); size=vertxList.size(); } publicAdjListGraph(Triple[]TripleArray,List〈E>vertxList){ this.adjlist=newLinkedMatrix〈Element〉(vertxList。 size(),vertxList.size()); this.vertxList=vertxList; for(Tripletriple: TripleArray){ insertEdge(triple。 getRow(),triple。 getColumn(),triple。 getweigth()); } size=vertxList。 size(); } (3)输出邻接表结果算法 @Override publicStringtoString(){ StringBufferstringBuffer=newStringBuffer(); for(inti=0;i〈vertxList.size();i++){ LinkedMatrixRowlinkedMatrixRow=adjlist.getRowLine(i); Iterator〈Ex5.Ex5_2.Element>iterator=linkedMatrixRow。 iterator(); stringBuffer.append(vertxList。 get(i)+""); while(iterator。 hasNext()){ Elementelement=iterator。 next(); stringBuffer.append("(”+i+”,") .append(element.getColumn()+",").append(element。 getValue()+”)”); } stringBuffer.append("\n"); } returnstringBuffer。 toString(); } 测试结果粘贴如下: 3、图的遍历递归算法 (1)(存储结构为邻接表)深度优先遍历算法 递归算法: publicvoidDFSTraverse(inti){ boolean[]visited=newboolean[vertxList。 size()]; intj=i; do{ if(! visited[j]){ System。 out.print("{"); this.depthfs(j,visited); System.out。 print(”}”); } j=(j+1)%vertxList.size(); }while(j! =i); System。 out.println(); } privatevoiddepthfs(inti,boolean[]visited){ System.out。 print(vertxList.get(i)+"”); visited[i]=true; intj=this.next(i,-1); while(j! =-1){ if(! visited[j]) depthfs(j,visited); j=this。 next(i,j); } } 测试结果粘贴如下: (2)广度优先遍历算法 非递归算法 publicvoidBFSTraverse(inti){ boolean[]visited=newboolean[vertxList。 size()]; intj=i; do{ if(! visited[j]){ System。 out。 print(”{"); breadthfs(j,visited); System.out.print("}"); } j=(j+1)%vertxList.size(); }while(j! =i); System。 out。 print
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验7 图及图的操作实验 实验 操作
![提示](https://static.bingdoc.com/images/bang_tan.gif)