20192328牛梓萌 2019-2020-1 《数据结构与面向对象程序设计》实验九报告
课程：《程序设计与数据结构》
班级： 1923
姓名：牛梓萌
学号：20192328
实验教师：王志强
实验日期：2020年12月17日
必修/选修： 必修
1.实验内容
图
(1) 初始化：根据屏幕提示（例如：输入1为无向图，输入2为有向图）初始化无向图和有向图（可用邻接矩阵，也可用邻接表），图需要自己定义（顶点个数、边个数，建议先在草稿纸上画出图，然后再输入顶点和边数）（2分）
(2) 图的遍历：完成有向图和无向图的遍历（深度和广度优先遍历）（4分）
(3) 完成有向图的拓扑排序，并输出拓扑排序序列或者输出该图存在环（3分）
(4) 完成无向图的最小生成树（Prim算法或Kruscal算法均可），并输出（3分）
(5) 完成有向图的单源最短路径求解（迪杰斯特拉算法）（3分）
2. 实验过程及结果
(1) 初始化：根据屏幕提示（例如：输入1为无向图，输入2为有向图）初始化无向图和有向图（可用邻接矩阵，也可用邻接表），图需要自己定义（顶点个数、边个数，建议先在草稿纸上画出图，然后再输入顶点和边数）
import java.util.Scanner;
/*
* 图类，在构造方法中完成图的构造
*/
public class Graph {
int verNum;
int edgeNum;
Vertex[] verArray;
/*
* Graph类的构造方法，依次读取节点、边等信息，完成图的构建。
*/
public Graph() {
Scanner scan = new Scanner(System.in);
System.out.println("请选择你想要构建有向图还是，无向图（0 or 1）： ");
int choose = scan.nextInt();
System.out.println("请输入节点个数和边的个数：");
verNum = scan.nextInt();
edgeNum = scan.nextInt();
verArray = new Vertex[verNum];
System.out.println("请依次输入节点的名称:");
for (int i=0;i<verNum;i++){
Vertex vertexmem = new Vertex();
vertexmem.verName = scan.next();
vertexmem.edgeLink = null;
verArray[i] = vertexmem;
}
System.out.println("请按 '头节点 尾节点 回车’的形式依次输入边的信息");
for (int i=0;i<edgeNum;i++){
String preName = scan.next();
String folName = scan.next();
Vertex preV = getVertex(preName);
Vertex folV = getVertex(folName);
if (preV == null || folV == null){
System.out.println("输入错误！请重新输入");
i--;
continue;
}
Edge edge = new Edge();
edge.tailName = folName;
edge.broEdge = preV.edgeLink;
preV.edgeLink = edge;
if(choose==1){
Edge edgeelse = new Edge();
edgeelse.tailName = preName;
edgeelse.broEdge = folV.edgeLink;
folV.edgeLink = edgeelse;}
}
}
public Vertex getVertex(String verName){
for (int i=0;i<verNum;i++){
if (verArray[i].verName.equals(verName))
return verArray[i];
}
return null;
}
}
(2) 图的遍历：完成有向图和无向图的遍历（深度和广度优先遍历）
import java.util.*;
/*
* 使用java实现图的图的广度优先 和深度优先遍历算法。
*/
public class GraphLoopTest {
private Map<String, List<String>> graph = new HashMap<String, List<String>>();
/*
* 初始化图数据：使用邻居表来表示图数据。
*/
public void initGraphData() {
// 图结构如下
// 9
// /
// 8 1
// / /
// 4 5 6
// | /
// 7
graph.put("9", Arrays.asList("8", "1"));
graph.put("8", Arrays.asList("9", "4", "5"));
graph.put("1", Arrays.asList("9", "6"));
graph.put("4", Arrays.asList("8", "7"));
graph.put("5", Arrays.asList("8", "7"));
graph.put("6", Arrays.asList("1", "7"));
graph.put("7", Arrays.asList("4", "5", "6"));
}
/*
* 宽度优先搜索(BFS, Breadth First Search)
*/
private Queue<String> queue = new LinkedList<String>();
private Map<String, Boolean> status = new HashMap<String, Boolean>();
public void BFSSearch(String startPoint) {
//1.把起始点放入queue；
queue.add(startPoint);
status.put(startPoint, false);
bfsLoop();
}
private void bfsLoop() {
String currentQueueHeader = queue.poll();
status.put(currentQueueHeader, true);
System.out.print(currentQueueHeader);
List<String> neighborPoints = graph.get(currentQueueHeader);
for (String poinit : neighborPoints) {
if (!status.getOrDefault(poinit, false)) {
if (queue.contains(poinit)) continue;
queue.add(poinit);
status.put(poinit, false);
}
}
if (!queue.isEmpty()) {
bfsLoop();
}
}
/*
* 深度优先搜索(DFS, Depth First Search)
*/
private Stack<String> stack = new Stack<String>();
public void DFSSearch(String startPoint) {
stack.push(startPoint);
status.put(startPoint, true);
dfsLoop();
}
private void dfsLoop() {
if (stack.empty()) {
return;
}
String stackTopPoint = stack.peek();
List<String> neighborPoints = graph.get(stackTopPoint);
for (String point : neighborPoints) {
if (!status.getOrDefault(point, false)) {
stack.push(point);
status.put(point, true);
dfsLoop();
}
}
String popPoint = stack.pop();
System.out.print(popPoint);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("请选择深度,还是广度遍历（1 or 2）");
int choose = scan.nextInt();
GraphLoopTest test = new GraphLoopTest();
test.initGraphData();
if (choose == 2) {
System.out.println("广度优先遍历 ：");
test.BFSSearch("1");
}
if (choose == 1) {
System.out.println("深度优先遍历： ");
test.DFSSearch("1");
}
}
}
(3) 完成有向图的拓扑排序，并输出拓扑排序序列或者输出该图存在环
import java.io.*;
public class TestTopoSort {
public static void main(String[] args) throws IOException {
DirectedGraph directedGraph = new DirectedGraph();
try{
directedGraph.topoSort();
}catch(Exception e){
System.out.println("graph has circle");
e.printStackTrace();
}
}
}
(4) 完成无向图的最小生成树（Prim算法或Kruscal算法均可），并输出
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/*
* 图的最小树生成算法
*
*/
public class Prim {
/*
* 求图最小生成树的PRIM算法
*/
public static void PRIM(int [][] graph,int start,int n){
int [][] mins=new int [n][2];
for(int i=0;i<n;i++){
if(i==start){
mins[i][0]=-1;
mins[i][1]=0;
}else if( graph[start][i]!=-1){
mins[i][0]=start;
mins[i][1]= graph[start][i];
}else{
mins[i][0]=-1;
mins[i][1]=Integer.MAX_VALUE;
}
}
for(int i=0;i<n-1;i++){
int minV=-1,minW=Integer.MAX_VALUE;
for(int j=0;j<n;j++){
if(mins[j][1]!=0&&minW>mins[j][1]){
minW=mins[j][1];
minV=j;
}
}
mins[minV][1]=0;
System.out.println("第"+i+"条最小边=<"+(mins[minV][0]+1)+","+(minV+1)+">，权重="+minW);
for(int j=0;j<n;j++){
if(mins[j][1]!=0){
if( graph[minV][j]!=-1&& graph[minV][j]<mins[j][1]){
mins[j][0]=minV;
mins[j][1]= graph[minV][j];
}
}
}
}
}
public static void main(String [] args){
int [][] tree={
{1,3,1,5,-1,-1},
{3,-1,5,-1,6,-1},
{1,5,-1,5,2,4},
{5,-1,5,-1,-1,2},
{-1,6,4,-1,-1,4},
{-1,-1,4,2,6,-1}
};
Prim.PRIM(tree, 0, 6);
}
}
(5) 完成有向图的单源最短路径求解（迪杰斯特拉算法）
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
public class DijstraAlgorithm {
public static void main(String[] args) {
int vertexNum = 5;
char[] vertexs = new char[] { 'N', 'Z', 'M', 'A', 'B' };
int[][] matrix = new int[][] { { 0, 1, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 3 },
{ Integer.MAX_VALUE / 2, 0, 8, Integer.MAX_VALUE / 2, 9 },
{ Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 0, 5, Integer.MAX_VALUE / 2 },
{ 7, Integer.MAX_VALUE / 2, 9, 0, Integer.MAX_VALUE / 2 },
{ Integer.MAX_VALUE / 2, 1, 2, 3, 0 } };
// matrix[i][j]为0表示i==j,matrix[i][j]为Integer.MAX_VALUE/2表示两个顶点不是图的边,否则表示边的权值
Graph g = new Graph(vertexNum, vertexs, matrix);
Scanner sc = new Scanner(System.in);
int srcIndex;
do{
System.out.print("请输入源点索引(0~4):");
srcIndex = sc.nextInt();
}while(srcIndex < 0 || srcIndex > 4);
System.out.println(g.vertexs[srcIndex] + "作为源点");
Info info = dijkstra(g, srcIndex);
for(int i : info.pathSerials){
System.out.print(g.vertexs[i] + " ");
}
System.out.println();
int index = 0;
for(int[] path : info.paths){
for(int i : path){
System.out.print(g.vertexs[i]);
}
System.out.println(": " + info.distances[index++]);
}
sc.close();
}
public static Info dijkstra(Graph g, int srcIndex) {
if(srcIndex < 0 || srcIndex >= g.vertexNum){
return null;
}
int[] pathSerials = new int[g.vertexNum];
int[] path = new int[g.vertexNum];
int index = 0;
pathSerials[index] = srcIndex;
g.visited[srcIndex] = true;
Arrays.fill(path, -1);
int[] distances = new int[g.vertexNum];
for (int i = 0; i < g.vertexNum; i++) {
distances[i] = g.matrix[srcIndex][i];
}
int minIndex = srcIndex;
while (minIndex != -1) {
index++;
for (int i = 0; i < g.vertexNum; i++) {
if (!g.visited[i]) {
distances[i] = Math.min(distances[i], distances[minIndex] + g.matrix[minIndex][i]);
if(distances[i] == distances[minIndex] + g.matrix[minIndex][i] && distances[i] != Integer.MAX_VALUE / 2){ // distances[i] != Integer.MAX_VALUE / 2表示仍不可达，就没有前驱
path[i] = minIndex;
}
}
}
minIndex = indexOf(g, distances);
if(minIndex == -1){
break;
}
pathSerials[index] = minIndex;
g.visited[minIndex] = true;
}
return new Info(distances, pathSerials, getPathOfAll(path, pathSerials));
}
public static int indexOf(Graph g, int[] distances) {
int min = Integer.MAX_VALUE / 2;
int minIndex = -1;
for(int i = 0; i < g.vertexNum; i++){
if(!g.visited[i]){
if(distances[i] < min){
min = distances[i];
minIndex = i;
}
}
}
return minIndex;
}
public static int[] getPath(int[] path, int i){
Stack<Integer> s = new Stack<Integer>();
s.push(i);
int pre = path[i];
while(pre != -1){
s.push(pre);
pre = path[pre];
}
int size = s.size();
int[] pathOfVertex = new int[size];
while(!s.isEmpty()){
pathOfVertex[size - s.size()] = s.pop();
}
return pathOfVertex;
}
public static ArrayList<int[]> getPathOfAll(int[] path, int[] pathSerials){
ArrayList<int[]> paths = new ArrayList<int[]>();
for(int i = 0; i < pathSerials.length; i++){
paths.add(getPath(path, i));
}
return paths;
}
public static class Graph{
private int vertexNum;
private char[] vertexs;
private int[][] matrix;
private boolean visited[];
public Graph(int vertexNum, char[] vertexs, int[][] matrix){
this.vertexNum = vertexNum;
this.vertexs = vertexs;
this.matrix = matrix;
visited = new boolean[vertexNum];
}
}
public static class Info{
private int[] distances;
private int[] pathSerials;
private ArrayList<int[]> paths;
public Info(int[] distances, int[] pathSerials, ArrayList<int[]> paths) {
this.distances = distances;
this.pathSerials = pathSerials;
this.paths = paths;
}
}
}
码云：https://gitee.com/besti1923/niu-zimeng-20192328/tree/master/src/Graph
其他（感悟、思考等）
图的实验还是有很大难度的，作为本课程的最后一个实验，在这次的实践中又加深了对图的认识。
参考资料
《Java程序设计与数据结构教程（第二版）》
《Java程序设计与数据结构教程（第二版）》学习指导