实验7-图及图的操作实验.doc

实验报告七 图及图的操作实验
班级： 姓名： 学号： 专业：
一、 实验目的：
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;
}

public void insertEdge(int i,int j, int weight){
if(i==j){
throw new IllegalArgumentException("不能插入自身环");
}

if(weight<0||weight>MAX_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<0||i>=vertxList.size()){
throw new IllegalArgumentException("i超出范围");
}

int n= vertxList.size();

vertxList.remove(i);

for(int j=i+1;jsetElement(j,k-1,matrix.getElement(j,k));
}
}

size--;

}

private int next(int i,int j){
int n = vertxList.size();
if(i>=0&&i=-1&&j0&&matrix.getElement(i,k)int j=0;j string += vertxList.get(i)+" ";
for(int j=0;j 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;ix.getElement(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 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(),triplegetweigth());
}

size = vertxList.size();
}

public void insertEdge(int i,int j,int weight){
if(i==j){
throw new IllegalArgumentException("i,j不能相等");
}

if(weight<0||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;i 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);
}

public void removeVertex(int i){
if(i<0||i>vertxList.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;j LinkedMatrixRow tempLinkedMatrixRow = adjlist.getRowLine(i);
Iterator tempIt = tempLinkedMatrixRow.iterator();

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&&j 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 boolean[vertxList.size()];
int j=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();

}

private void depthfs(int i,boolean[] visited){
System.out.print(vertxList.get(i)+" ");
visited[i] = true;
int j = this.next(i,-1);
while (j!=-1){
if(!visited[j])
depthfs(j,visited);
j=this.next(i,j);
}
}

public void BFSTraverse(int i){
boolean[] visited = new boolean[vertxList.size()];
int j = 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();
}

public void breadthfs(int i, boolean[] visited){
System.out.print(vertxList.get(i)+" ");
visited[i] = 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(!visited[j]){
System.out.print(vertxList.get(j)+" ");
visited[j] = true;
queue.add(j);
}
}
}
}
}

（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）输出邻接表结果算法
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();

for(int i=0;i 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();
}

测试结果粘贴如下：

3、图的遍历递归算法
（1）（存储结构为邻接表）深度优先遍历算法
递归算法：
public void DFSTraverse(int i){
boolean[] visited = new boolean[vertxList.size()];
int j=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();

}

private void depthfs(int i,boolean[] visited){
System.out.print(vertxList.get(i)+" ");
visited[i] = true;
int j = this.next(i,-1);
while (j!=-1){
if(!visited[j])
depthfs(j,visited);
j=this.next(i,j);
}
}

测试结果粘贴如下：

（2）广度优先遍历算法
非递归算法
public void BFSTraverse(int i){
boolean[] visited = new boolean[vertxList.size()];
int j = 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();
}

public void breadthfs(int i, boolean[] visited){
System.out.print(vertxList.get(i)+" ");
visited[i] = 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(!visited[j]){
System.out.print(vertxList.get(j)+" ");
visited[j] = true;
queue.add(j);
}
}
}
}

测试结果粘贴如下：

三、 实验心得（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得）