项目二

• 一、需求分析
• 二、逻辑设计
• 三、物理设计
• 四、实验准备
• • 1.编程语言
  • 2.开发工具/平台

一、需求分析

【问题描述】
设计一个校园导游程序,为来访的客人提供各种信息查询服务。

【基本要求】
1) 设计你所在学校的校园平面图,所含景点不少于10个.以图中顶点表示校内各景点,存放景点名称、代号、简介 等信息；以边表示路径，存放路径长度等相关信息。
2) 为来访客人提供图中任意景点相关信息的查询。
3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

二、逻辑设计

Step1

选取校园10个景点

把10各景点抽象成图

Step2

执行下面的程序

定义一个10×3的二维数组infoOfSite用来存放各景点的名称、代号简介定义有10个顶点的无向图选择路径起点{选择路径终点{输出最短路径{if(图的遍历终点编号==二维数组中的编号){弹出菜单Menu选择以显示景点的不同信息}}}}

具体如下

输入顶点数和边数：10 13
输入顶点名称：
1 2 3 4 5 6 7 8 9 10
输入起点和终点:1 2
输入起点和终点:1 3
…
输入路径的起点：
1 5
输出：
最短路径为：
…

三、物理设计

无权图的最短路径算法(BFS)

package com.Algorithm.ShortestPath;import java.util.ArrayList;import java.util.LinkedList;import java.util.Scanner; public class ShortestPathTest { Graph g ;//构造函数public ShortestPathTest(){g = new Graph();g.buildGraph();}/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubShortestPathTest s = new ShortestPathTest();System.out.println("输入路径的起点：");Scanner input = new Scanner(System.in);String first = input.next();input.next();s.shortestPath(first);} public void shortestPath(String first){LinkedList<Vertex> queue = new LinkedList<Vertex>();Vertex firstVertex = g.v[g.findvIndex(first)];firstVertex.setIsVisted(true);int counter = 0;firstVertex.setPathlength(counter);queue.add(firstVertex);System.out.println("最短路径为：");String path;while(!queue.isEmpty()){Vertex v = queue.poll();//得到队顶的path和Counter，用于下面for循环的赋值path = v.getFrom();counter = v.getPathlength();System.out.println( v.getFrom()+"的路径长度为 "+v.getPathlength()+",上一个节点是"+v.path+" ");ArrayList<Vertex> al = g.getAdjacentVertex(v);for( Vertex vertex : al ){if(!(vertex.getIsVisted()))//没被访问过{vertex.setIsVisted(true);vertex.setPathlength(counter+1);vertex.setPath(path);queue.add(vertex);}}}}}

以此为例进行其他景点的最短路径查找

四、实验准备

1.编程语言

java

2.开发工具/平台

IDEA