实验7 图及图地操作实验.docx
《实验7 图及图地操作实验.docx》由会员分享，可在线阅读，更多相关《实验7 图及图地操作实验.docx（16页珍藏版）》请在冰点文库上搜索。
实验7图及图地操作实验
实验报告七图及图的操作实验
班级：
：
学号：
专业：
一、实验目的：
1、掌握图的基本概念和术语
2、掌握图的存储结构及创建算法。
3、掌握图的遍历算法（递归或非递归算法）。
二、实验容：
1、图邻接矩阵存储结构表示及基本操作算法实现
（1）邻接矩阵存储结构类定义：
自定义如下：
packageEx7.Ex7_1;
importEx5.Ex5_1.Matrix;
importEx7.Triple;
importjava.util.List;
/**
*Createdby74062on2017/5/17.
*/
publicclassMatrixGraph{
privateMatrixmatrix;
privateListvertxList;
privatestaticfinalintMAX_WEIGHT=0x0000ffff;
privateintsize;
publicMatrixGraph（Triple[]TripleArray,ListvertxList）{
this.matrix=newMatrix（vertxList.size（）,vertxList.size（））;
this.vertxList=vertxList;
for（Tripletriple:
TripleArray）{
insertEdge（triple）;
}
size=vertxList.size（）;
}
publicMatrixGraph（ListvertxList）{
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;jfor（intk=0;kmatrix.setElement（j-1,k,matrix.getElement（j,k））;
}
}
for（intj=0;jfor（intk=i+1;kmatrix.setElement（j,k-1,matrix.getElement（j,k））;
}
}
size--;
}
privateintnext（inti,intj）{
intn=vertxList.size（）;
if（i>=0&&i=-1&&j=j）{
for（intk=j+1;kif（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;ifor（intj=0;jmatrix.setElement（i,j,this.matrix.getElement（i,j））;
}
}
this.matrix=matrix;
}
Override
publicStringtoString（）{
Stringstring="";
for（inti=0;istring+=vertxList.get（i）+"";
for（intj=0;jstring+=matrix.getElement（i,j）+"";
}
string+="\n";
}
returnstring;
}
}
（2）创建邻接矩阵算法
publicMatrixGraph（Triple[]TripleArray,ListvertxList）{
this.matrix=newMatrix（vertxList.size（）,vertxList.size（））;
this.vertxList=vertxList;
for（Tripletriple:
TripleArray）{
insertEdge（triple）;
}
size=vertxList.size（）;
}
publicMatrixGraph（ListvertxList）{
this.matrix=newMatrix（vertxList.size（）,vertxList.size（））;
size=vertxList.size（）;
this.vertxList=vertxList;
}
（3）输出邻接矩阵结果算法
publicStringtoString（）{
Stringstring="";
for（inti=0;istring+=vertxList.get（i）+"";
for（intj=0;jstring+=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{
protectedLinkedMatrixadjlist;
privateListvertxList;
privatestaticfinalintMAX_WEIGHT=0x0000ffff;
privateintsize;
publicAdjListGraph（intlength）{
vertxList=newArrayList（length）;
adjlist=newLinkedMatrix（length,length）;
size=vertxList.size（）;
}
publicAdjListGraph（Triple[]TripleArray,ListvertxList）{
this.adjlist=newLinkedMatrix（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;iLinkedMatrixRowlinkedMatrixRow=adjlist.getRowLine（i）;
Iteratoriterator=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）;
Iteratorit=linkedMatrixRow.iterator（）;
while（it.hasNext（））{
Elementelement=it.next（）;
removeEdge（i,element.getColumn（））;
}
n--;
adjlist.setRow（n）;
adjlist.setColumn（n）;
for（intj=0;jLinkedMatrixRowtempLinkedMatrixRow=adjlist.getRowLine（i）;
IteratortempIt=tempLinkedMatrixRow.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=-1&&j=j）{
LinkedMatrixRowlinkedMatrixRow=adjlist.getRowLine（i）;
Iteratoriterator=linkedMatrixRow.iterator（）;
if（j==-1）
returniterator.hasNext（）?
iterator.next（）.getColumn（）:
-1;
MyList.Nodenode=linkedMatrixRow.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;
Queuequeue=newLinkedBlockingQueue（）;
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（length）;
adjlist=newLinkedMatrix（length,length）;
size=vertxList.size（）;
}
publicAdjListGraph（Triple[]TripleArray,ListvertxList）{
this.adjlist=newLinkedMatrix（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;iLinkedMatrixRowlinkedMatrixRow=adjlist.getRowLine（i）;
Iteratoriterator=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.println（）;
}
升级会员 