【数据结构课程设计报告】路径规划系统（Java实现）

数据结构课程设计报告

一、需求分析

问题描述：路径规划系统的业务活动包括：路径信息的添加、以邻接矩阵方式显示路径信息、最短路径的两种规划方式（1.Dijkstra 2.Floyd）等，需对指定内容进行分析设计利用计算机加以实现。

路径所涉及的信息有：顶点数即地点数、边数即路径数、所有顶点信息、每条路径的两个端点信息和每条路径的权值。

系统能够实现的功能与操作如下：
1.添加路径信息：根据用户依次输入的内容（顶点数、边数、顶点信息、每条路径的两个端点信息和权值），对所需添加的路径进行相应存储。
2.查看邻接矩阵：根据用户输入的路径信息绘制以权值为主的相应邻接矩阵。
3.规划方式：根据用户选择的规划方式（1.Dijkstra 2.Floyd）若选择1，待用户输入需要查询的顶点下标后使用Dijkstra算法，计算输入顶点与其他顶点之间的最短路径并显示；若选择2，待用户输入需要查询的两个端点信息后使用Floyd算法，计算两个端点之间的最短路径并显示。
4.退出系统：退出当前界面。

输出界面：有主菜单、分菜单可对上述所说2的内容进行用户的相应选择和呈现，以达到系统的交互性。
编译环境：win10；eclipse;
所使用的编译语言：Java语言

二、系统功能划分及设计

1.存储结构设计

系统存储结构设计采用有向图的邻接矩阵存储结构。运用两个数组，一个是一维数组存储图中顶点信息，另一个是二维数组即矩阵，存储顶点之间边的信息。

2.系统的功能架构设计

系统功能架构流程设计如图所示，主函数调用菜单函数进行菜单选择(1-4)。

1. 当用户选择1时，调用添加路径信息，待用户依次输入顶点数，边数，顶点信息，每条路径的两个端点信息和权值，如输入信息类型格式无误则可添加成功。
2. 当用户选择2时，调用查询邻接矩阵，如此时未添加路径信息，需添加路径信息才可查看相应邻接矩阵。
3. 当用户选择3时，调用规划方式菜单选择(1-3)，1代表以Dijkstra算法为主的最短路径查询，2代表以Floyd算法为主的最短路径查询， 3返回主菜单。
4. 退出系统。

3.模块设计

如上图所示为系统所涉及到各类的属性、方法及各类之间的关系图。

3.代码实现

public class Graph<T> {protected final int MAXSIZE = 20; // 邻接矩阵可以表示的最大顶点数protected final int MAX = 9999; // 在网中，表示没有联系（权值无穷大）protected T[] V;// 顶点信息protected int[][] arcs;// 邻接矩阵protected int e;// 边数protected int n;// 顶点数protected boolean[] visited; // 访问标志数组static String elementAll;// 用户输入的顶点元素public Graph() {V = (T[]) new Object[MAXSIZE];arcs = new int[MAXSIZE][MAXSIZE];visited = new boolean[MAXSIZE];}// 1：在图中查找顶点v，找到后返回其在顶点数组中的索引号// 若不存在，返回-1public int LocateVex(T v) {int i;for (i = 0; i < n; i++)if (V[i] == v)return i;return -1;}// 2:在屏幕上显示图G的邻接矩阵表示public void DisplayAdjMatrix() {int i, j;for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {System.out.print(arcs[i][j] + "\t");}System.out.println();}}// 3：创建有向图的邻接矩阵public void CreateAdj() {int i, j, k;T v1, v2;Scanner sc = new Scanner(System.in);System.out.print("请输入图的顶点数：n=");if (sc.hasNextInt()) {n = sc.nextInt();System.out.print("请输入图的边数：e=");if (sc.hasNextInt()) {e = sc.nextInt();System.out.print("请输入图的顶点信息：");String str = sc.next();elementAll = str;if (str.toCharArray().length == n) {for (i = 0; i < n; i++)V[i] = (T) (Object) str.charAt(i);// 构造顶点信息for (i = 0; i < n; i++)for (j = 0; j < n; j++)arcs[i][j] = MAX;// 初始化for (k = 0; k < e; k++) {// 建立有向网的邻接矩阵int w;System.out.print