实验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<E> {
private Matrix matrix;
private List<E> vertxList;
private static final int MAX_WEIGHT = 0x0000ffff;
private int size;

public MatrixGraph(Triple[] TripleArray, List<E> vertxList ) {
this.matrix = new Matrix(vertxList.size(),vertxList.size());
this.vertxList = vertxList;

for(Triple triple:TripleArray){
insertEdge(triple);
}

size = vertxList.size();
}

public MatrixGraph(List<E> 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;j<n;j++){
for(int k=0;k<n;k++){
matrix.setElement(j-1,k,matrix.getElement(j,k));
}
}

for(int j=0;j<n;j++){
for(int k=i+1;k<n;k++){
matrix.setElement(j,k-1,matrix.getElement(j,k));
}
}

size--;

}

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

return string;
}
}

（2）创建邻接矩阵算法
public MatrixGraph(Triple[] TripleArray, List<E> vertxList ) {
this.matrix = new Matrix(vertxList.size(),vertxList.size());
this.vertxList = vertxList;

for(Triple triple:TripleArray){
insertEdge(triple);
}

size = vertxList.size();
}

public MatrixGraph(List<E> 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;i<size;i++){
string += vertxList.get(i)+" ";
for(int j=0;j<size;j++){
string += matrix.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<E> {
protected LinkedMatrix<Element> adjlist;
private List<E> vertxList;
private static final int MAX_WEIGHT = 0x0000ffff;
private int size;

public AdjListGraph(int length){
vertxList = new ArrayList<E>(length);

adjlist = new LinkedMatrix(length,length);

size = vertxList.size();
}

public AdjListGraph(Triple[] TripleArray, List<E> vertxList ) {
this.adjlist = new LinkedMatrix<Element>(vertxList.size(),vertxList.size());
this.vertxList = vertxList;

for(Triple triple:TripleArray){
insertEdge(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<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<vertxList.size();i++){
LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i);
Iterator<Ex5.Ex5_2.Element> 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<Ex5.Ex5_2.Element> 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<adjlist.getRow();j++){
LinkedMatrixRow tempLinkedMatrixRow = adjlist.getRowLine(i);
Iterator<E> 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<n&&j>=-1&&j<n&&i!=j){
LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i);
Iterator<Element> iterator = linkedMatrixRow.iterator();

if(j==-1)
return iterator.hasNext()?iterator.next().getColumn():-1;

MyList.Node<Element> 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<Integer> queue = new LinkedBlockingQueue<Integer>();
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<E>(length);

adjlist = new LinkedMatrix(length,length);

size = vertxList.size();
}

public AdjListGraph(Triple[] TripleArray, List<E> vertxList ) {
this.adjlist = new LinkedMatrix<Element>(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<vertxList.size();i++){
LinkedMatrixRow linkedMatrixRow = adjlist.getRowLine(i);
Iterator<Ex5.Ex5_2.Element> 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<Integer> queue = new LinkedBlockingQueue<Integer>();
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);
}
}
}
}

测试结果粘贴如下：

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