数据结构实验报告6

武汉纺织大学《数据结构》实验报告

班级： 信管 专业 班 姓名 序号：

实验时间： 2016 年 4 月 29 日 指导教师： 宋泽源

实验六：图的存储与基本操作

一、实验目的：

1、掌握图的几种主要存储方法及基本操作 2、掌握图的两种遍历方法

3、掌握利用普里姆算法和克鲁斯卡尔算法求取最小生成树的方法

二、实验内容：

1、编写程序，输出图的邻接矩阵结构，输出两种遍历序列，并输出最小生成树。

实验步骤： ①、新建程序，输入书本P256 图7-42 带权无向图G8（书本P214 图7.40 带权无向图G7）；

②、运行程序，输出邻接矩阵；

③、输出深度优先遍历和广度优先遍历的序列； ④、输出运用普里姆算法求出的最小生成树。

注意：参考程序中，深度优先搜索算法可参考书本P238/198 DFSTraverse；广度优先遍历算法可参考书本P240、200 BFSTraverse；普利姆算法可参考书本P245/205 miniSpan_Tree_prim。

三、操作步骤：

实验结果：

package graph;

public class WeightedUndiGraph {

public static void main(String[] args){

String[] vertices={\,\,\,\,\,\,\,\}; Edge edges[]={new Edge(0,1,12),new Edge(0,2,31),new

new Edge(1,3,23),new Edge(2,0,31),new new Edge(3,2,15),new Edge(3,4,11),new new Edge(4,3,11),new Edge(4,5,5),new

Edge(1,0,12),

Edge(2,3,15),new Edge(3,1,23), Edge(3,5,4),

Edge(4,6,27),

};

AdjMatrixGraph graph = new

System.out.println(\带权无向图G8， \+graph.toString());

System.out.println(\深度优先遍历：\); graph.DFSTraverse(0); System.out.println();

System.out.println(\广度优先遍历：\); graph.BFSTraverse(0); System.out.println();

graph.minSpanTree_prim(); System.out.println();

new Edge(5,3,4),new Edge(5,4,5),new new Edge(6,4,27),new Edge(6,5,63),new new Edge(7,5,17),new Edge(7,6,18),

Edge(5,6,63),new Edge(5,7,17), Edge(6,7,18),

AdjMatrixGraph(vertices,edges);

System.out.println(\插入顶点I，插入边(A,I,20),删除顶点C，删除边(D,E)\); }

}

int i = graph.insertVertex(\); graph.insertEdge(0,i,20); graph.insertEdge(i,0,20); graph.removeVertex(2); graph.removeEdge(2,3); graph.removeEdge(3,2);

System.out.println(graph.toString());