校园导游系统-Java实现

一. 题目

设计一个校园导游系统。设计学校的校园平面图，选取若干个具有代表性的景点抽象成一个无向带权图，以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。存放景点代号、名称、简介等信息供用户查询。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点之间的问路查询。可以为校园平面图增加或删除景点或边，修改边上的权值。主要功能如下：

（1）景点介绍：系统能输出学校全部景点信息，包括景点编号，景点名称及景点介绍。

（2）线路浏览：采用迪杰斯特拉算法，根据用户输入的其实景点编号，求出从该景点到其他景点之间的最短路径及距离。

（3）查询景点间最短路径：根据用户输入的起始景点及目的景点编号，查询任意两个景点之间的最短路径线路及距离。

（4）景点信息查询：根据用户输入的景点编号输出该景点相关信息。

（5）查询景点间可行路径：任意两个景点之间的路径可能有很多条，求出两景点间所有可行路径中，限制只输出路径长度不超过N个景点的路线。

二、需求分析、功能要求及功能模块图

1.功能要求

(1)景点介绍：系统能输出学校全部景点信息，包括景点编号，景点名称及景点介绍。

(2)线路浏览：采用迪杰斯特拉算法，根据用户输入的其实景点编号，求出从该景点到其他景点之间的最短路径及距离。

(3)查询景点间最短路径：根据用户输入的起始景点及目的景点编号，查询任意两个景点之间的最短路径线路及距离。

(4)景点信息查询：根据用户输入的景点编号输出该景点相关信息。

(5)查询景点间可行路径：任意两个景点之间的路径可能有很多条，求出两景点间所有可行路径中，限制只输出路径长度不超过N个景点的路线。

2.需求分析

??(1)先创建顶点类，包括景点编号，景点名称及景点介绍。

??(2)再创建边类，包括边的终点和边的权重(此题指的是距离)

??(3)创建SystemService类，具体实现3种查询路径功能。

第一种是指定地点到指定地点，

第二种是指定地点到多个地点，

第三种是多个地点到多个地点。

第一种和第二种均可以用迪杰斯特拉算法解决，因为迪杰斯特拉是单源最短路径算法。

第三种可以用弗洛伊德算法解决，因为弗洛伊德是多源最短路径算法。

??(4)创建SystemView类，创建无向图邻接表，对SystemService具体的功能加以调用，同时打印菜单，接收用户输入

??(5)创建CampusTourGuide类，实例化SystemView对象，打印菜单

3.功能模块图

三、设计思想

1.先分层 ?-> 有哪些类 ， 类与类直接的调用关系

2.明确哪些功能在哪个类

3.确定功能后，分析功能

4.具体实现功能

5.重复3,4步

四.? 代码实现

//Vertex类

public class Vertex {
    String id;          //编号
    String name;        //名称
    List<Edge> edges;   //点的邻边
    int dist = Integer.MAX_VALUE;       //距离
    Vertex prev;        //点的前驱
    String detail;      //景点的描述

    public Vertex(String id, String name, String detail) {
        this.id = id;
        this.name = name;
        this.detail = detail;
    }

    @Override
    public String toString() {
        return "景点{" +
                "编号='" + id + '\'' +
                ", 名称='" + name + '\'' +
                ", 介绍='" + detail + '\'' +
                '}';
    }
}

//Edge类
public class Edge {
    Vertex linked;      //边的终点
    int weight;         //边的权重

    public Edge(Vertex linked, int weight) {
        this.linked = linked;
        this.weight = weight;
    }
}

//SystemView 类


public class SystemView {
    SystemService systemService = new SystemService();
    Scanner myScanner = new Scanner(System.in);
    //2个静态属性，存放对应顶点的下标
    static int input01;
    static int input02;




    //1.创建顶点
    Vertex v1 = new Vertex("v1","西门","西侧入口");
    Vertex v2 = new Vertex("v2","操场","锻炼,看比赛");
    Vertex v3 = new Vertex("v3","宿舍","休息");
    Vertex v4 = new Vertex("v4","食堂","吃饭");
    Vertex v5 = new Vertex("v5","东门","东侧入口");
    Vertex v6 = new Vertex("v6","教学楼","教学");
    List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);

    //2.顶点添加边
    public void addEdges(){
        v1.edges = List.of(new Edge(v3,9)
                ,new Edge(v2,7)
                ,new Edge(v6,14));
        v2.edges = List.of(new Edge(v4,15)
                ,new Edge(v1,7));
        v3.edges = List.of(new Edge(v4,11)
                ,new Edge(v6,2)
                ,new Edge(v1,9));
        v4.edges = List.of(new Edge(v5,6)
                ,new Edge(v3,11)
                ,new Edge(v2,15));
        v5.edges = List.of(new Edge(v4,6)
                ,new Edge(v6,9));
        v6.edges = List.of(new Edge(v5,9)
                ,new Edge(v1,14)
                ,new Edge(v3,2));
    }


    //3.用户输入,并将输入的字符串编号转为Vertex类型的编号
    public Vertex returnVertex(){
        String v = myScanner.next();
        Vertex vertex = null;
        switch (v){
            case "v1":
                vertex = v1;
                input01 = 0;
                input02 = 0;
                break;
            case "v2":
                vertex = v2;
                input01 = 1;
                input02 = 1;
                break;
            case "v3":
                vertex = v3;
                input01 = 2;
                input02 = 2;
                break;
            case "v4":
                vertex = v4;
                input01 = 3;
                input02 = 3;
                break;
            case "v5":
                vertex = v5;
                input01 = 4;
                input02 = 4;
                break;
            case "v6":
                vertex = v6;
                input01 = 5;
                input02 = 5;
                break;
            default:
                System.out.println("不存在该景点");
        }
        return vertex;
    }




    //5.景点介绍：系统能输出学校全部景点信息，包括景点编号，景点名称及景点介绍。
    public void printDeatil_(){
        System.out.println("景点介绍 ");
        systemService.printDetail(graph);
    }

    //6.线路浏览：采用迪杰斯特拉算法，根据用户输入的其实景点编号，
    // 求出从该景点到其他景点之间的最短路径及距离。
    @Test
    public void OneToOther(){
        System.out.println("请输入起始景点编号");
        //用户输入,并将输入的字符串编号转为Vertex类型的编号
        Vertex vertex = returnVertex();

        systemService.dijkstra(vertex,graph);
        //打印最短路径
        systemService.printPath(graph);   //打印起始点 到所有终点
    }


    //7.查询景点间最短路径：根据用户输入的起始景点及目的景点编号，
    // 查询任意两个景点之间的最短路径线路及距离。
    public void OneToOne(){
        System.out.println("请输入起始景点编号");
        //用户输入,并将输入的字符串编号转为Vertex类型的编号
        Vertex vertex = returnVertex();
        systemService.dijkstra(vertex,graph);

        System.out.println("请输入终点景点编号");
        //用户输入,并将输入的字符串编号转为Vertex类型的编号
        vertex = returnVertex();
        systemService.printPath(vertex);   //打印起始点 到指定的一个终点


    }



    //8.景点信息查询：根据用户输入的景点编号输出该景点相关信息。
    public void seekVertexDetail(){
        System.out.println("请输入查询的景点编号");
        //用户输入,并将输入的字符串编号转为Vertex类型的编号
        Vertex vertex = returnVertex();
        System.out.println(vertex);
    }


    //9.查询景点间可行路径：任意两个景点之间的路径可能有很多条，求出两景点间所有可行路径中，限制只输出路径长度不超过N个景点的路线。
    public void restrictedPath(){

        System.out.println("请输入限制的长度");
        int restrictedLength = myScanner.nextInt();

        //弗洛伊德算法
        systemService.folydWarshall(graph,restrictedLength);

    }

//9.查询景点间可行路径：任意两个景点之间的路径可能有很多条，求出两景点间所有可行路径中，限制只输出路径长度不超过N个景点的路线。
//    public void restrictedPath(){
//        System.out.println("请输入起始景点编号");
//        //用户输入,并将输入的字符串编号转为Vertex类型的编号
//        Vertex start = returnVertex();
//        int i = input01;
//        System.out.println("请输入终点景点编号");
//        //用户输入,并将输入的字符串编号转为Vertex类型的编号
//        Vertex destination = returnVertex();
//        int j = input02;
//        System.out.println("请输入限制的长度");
//        int restrictedLength = myScanner.nextInt();
//
//        //弗洛伊德算法
//        systemService.folydWarshall(graph,start,destination,restrictedLength,i,j);
//
//    }



    //10.打印界面
    public void print(){
        //添加边
        addEdges();

       boolean judge = true;
        while (judge){
            System.out.println("**********       校园导游系统            **********");
            System.out.println("**********       1.景点介绍             **********");
            System.out.println("**********       2.该景点到其他景点路线   **********");
            System.out.println("**********       3.该景点到指定景点路线   **********");
            System.out.println("**********       4.查询景点相关信息      **********");
            //System.out.println("**********       5.查询路指定景点径长度不超过N个景点的路线  **********");
            System.out.println("**********       5.查询所有景点路径长度不超过N个景点的路线  **********");
            System.out.println("**********       6.退出系统             **********");
            System.out.println("请选择");
            int choice = myScanner.nextInt();

            switch (choice){
                case 1:
                    printDeatil_();
                    break;
                case 2:
                    OneToOther();
                    break;
                case 3:
                    OneToOne();
                    break;
                case 4:
                    seekVertexDetail();
                    break;
                case 5:
                    restrictedPath();
                    break;
                case 6:
                    judge = false;
                    System.out.println("退出系统");
                    break;
                default:
                    System.out.println("选择错误,请重新选择");
            }
            System.out.println();
        }
    }

}

//SystemService类



public class SystemService {

    @Test

    //1.景点介绍：系统能输出学校全部景点信息，包括景点编号，景点名称及景点介绍。
    public void printDetail(List<Vertex> graph){
        ArrayList<Vertex> v = new ArrayList<>(graph);
        for (int i = 0; i < v.size(); i++) {
            System.out.println(v.get(i));
        }
    }

    //2.线路浏览：采用迪杰斯特拉算法，根据用户输入的其实景点编号，
    // 求出从该景点到其他景点之间的最短路径及距离。

    public void dijkstra(Vertex v,List<Vertex> graph){
        //1.创建一个存储未访问顶点的集合
        ArrayList<Vertex> list = new ArrayList<>(graph);
        //2.将所有顶点的入度设置为无穷大,其中起点设置为0
        v.dist = 0;
        while (!list.isEmpty()) {
            //3.从集合中选取距离最小的,最为当前顶点
            Vertex curr = chooseMinDistVertex(list);
            //4.访问当前顶点的邻居，若距离小于邻居，则更新
            updataNeighbourDist(list,curr);
            //5.删除当前顶点
            list.remove(curr);
        }
    }

    private void updataNeighbourDist(ArrayList<Vertex> list, Vertex curr) {
        for (Edge edge : curr.edges) {
            Vertex linked = edge.linked;
            if(list.contains(linked)){
                int tempDist = curr.dist + edge.weight;
                if(tempDist < linked.dist){
                    linked.dist = tempDist;
                    linked.prev = curr;
                }
            }
        }
    }




    private Vertex chooseMinDistVertex(ArrayList<Vertex> list) {
        //先假设一个最小顶点
        Vertex min = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if(list.get(i).dist < min.dist){
                min = list.get(i);
            }
        }
        return min;
    }

    //打印最短路径    打印起始点 到所有终点
    public void printPath(List<Vertex> graph) {
        //1.存储所有顶点
        ArrayList<Vertex> list = new ArrayList<>(graph);
        //2.存储路线顶点
        ArrayList<Vertex> shortRoute = new ArrayList<>();
        Vertex temp;
        for (int i = 0; i < list.size(); i++) {
            //3.将目的地节点，作为当前起点
            temp = list.get(i);
            //4.将目的地节点装入路径图，从目的地开始倒推到起点
            shortRoute.add(temp);
            //5.如果当前节点还有上一个节点
            while (temp.prev != null){
                //将上一节点装入路径图
                shortRoute.add(temp.prev);
                //上一节点变成当前节点，供下一次循环使用
                temp = temp.prev;
            }
            //6.因为我们是反向求路径的，所以将路径图逆序
            Collections.reverse(shortRoute);

            //7.打印最短路径图标题
            System.out.println(shortRoute.get(0).name + " 到 " + shortRoute.get(shortRoute.size()-1).name);
            System.out.println("最短距离为 " + shortRoute.get(shortRoute.size()-1).dist + "米");
            //8.打印最短路径图
            System.out.print("最短路径为 ");
            for (int j = 0; j < shortRoute.size(); j++) {
                System.out.print(shortRoute.get(j).name + " ");
            }
            shortRoute.clear();
            System.out.println();
        }
    }


    //3.查询景点间最短路径：根据用户输入的起始景点及目的景点编号，
    //     查询任意两个景点之间的最短路径线路及距离。

    //打印最短路径    打印起始点 到指定终点
    public void printPath(Vertex vertex) {
        //1.用于存储路径的集合
        ArrayList<Vertex> shortRoute = new ArrayList<>();
        //2.将目的地节点，作为当前起点
        Vertex temp = vertex;
        //3.将目的地节点装入路径图，从目的地开始倒推到起点
        shortRoute.add(temp);
        //4.如果当前节点还有上一个节点
        while (temp.prev != null) {
            //将上一节点装入路径图
            shortRoute.add(temp.prev);
            //上一节点变成当前节点，供下一次循环使用
            temp = temp.prev;
        }
        //5.因为我们是反向求路径的，所以将路径图逆序
        Collections.reverse(shortRoute);
        //6.打印最短路径图标题
        System.out.println(shortRoute.get(0).name + " 到 " + shortRoute.get(shortRoute.size() - 1).name);
        System.out.println("最短距离为 " + shortRoute.get(shortRoute.size() - 1).dist + "米");
        //7.打印最短路径图
        System.out.print("最短路径为 ");
        for (int j = 0; j < shortRoute.size(); j++) {
            System.out.print(shortRoute.get(j).name + " ");
        }
        shortRoute.clear();
        System.out.println();
    }


    //4.查询景点间可行路径：任意两个景点之间的路径可能有很多条，
    // 求出两景点间所有可行路径中，限制只输出路径长度不超过N个景点的路线。

    @Test
    public void folydWarshall(List<Vertex> graph,int restrictedLength) {
        int size = graph.size();
        //1.创建存储距离的二维数组
        int[][] dist = new int[size][size];
        //2.创建存储前趋顶点的二维数组
        Vertex[][] prev  = new Vertex[size][size];

        //3.二维表格的初始化 ->  直接连接的
        for (int i = 0; i < size; i++) {
            Vertex v = graph.get(i);
            Map<Vertex, Integer> map = v.edges.stream().collect
                    (Collectors.toMap(edge -> edge.linked, edge -> edge.weight));
            for (int j = 0; j < size; j++) {
                Vertex u = graph.get(j);
                if(v == u){     //相同的顶点
                    dist[i][j] = 0;
                }else {          //检查外层和内存顶点是否连接
                    dist[i][j] = map.getOrDefault(u, Integer.MAX_VALUE);
                    //前趋顶点初始化
                    //map.get(u)   检查内层顶点u在外层map集合中是否存在，若存在，则外层v就是内存u的前趋
                    prev[i][j] = map.get(u) != null ? v : null;
                }
            }
        }


        //4.间接连接的,通过中间顶点到达其它顶点
        for (int k = 0; k < size; k++) {
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    //若中间人对俩边能连通 ， 并且距离比直连的距离小
                    if(dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][k] + dist[k][j] < dist[i][j]){
                        //更新距离
                        dist[i][j] = dist[i][k] + dist[k][j];
                        //更新前趋
                        prev[i][j] = prev[k][j];
                    }
                }
            }
        }

        //5.打印二维距离表格
        //printDist(dist,size);

        //6.打印二维前趋表格
        //printPrev(prev,size);

        //7.打印长度小于n的路径
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                restrictedPath(prev,dist,i,j,graph,restrictedLength);
            }
        }

    }



    //7.打印长度小于n的路径          传入的起点和终点只能是int型表示了
    public void restrictedPath(Vertex[][] prev,int[][] dist,int i,int j,List<Vertex> graph,int restrictedLength){

        if(dist[i][j] <= restrictedLength){
            //1.用于存储路径的栈
            LinkedList<Vertex> stack = new LinkedList<>();
            //2.打印路径标题
            System.out.println(graph.get(i).name + " 到 " + graph.get(j).name
                    + "距离为" + dist[i][j]);
            //3.创建临时变量
            Vertex temp01 = graph.get(i);
            Vertex temp02 = graph.get(j);
            //4.将终点入栈
            stack.push(temp02);
            //5.若终点 不等于 起点
            while (i != j){
                Vertex v = prev[i][j];
                //将上一节点装入栈
                stack.push(v);
                //将刚刚入栈的上一节点的下标赋给j
                j = graph.indexOf(v);
            }
            //6.打印路径
            //System.out.println("路径为 " + stack);//打印的是每个顶点，要想打印的是顶点的name，那就遍历stack
            System.out.print("路径为 ");
            while (!stack.isEmpty()){
                Vertex v = stack.pop();
                System.out.print(v.name + " ");
            }
            System.out.println();


        }
    }




    //打印二维距离表格
    public void printDist(int[][] dist,int size){
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(dist[i][j] + "  ");
            }
            System.out.println();
        }
    }

    //打印二维前趋表格
    public void printPrev(Vertex[][] prev,int size){
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                System.out.print(prev[i][j] + "  ");
            }
            System.out.println();
        }
    }
}

//CampusTourGuideAPP类


public class CampusTourGuideAPP {
    public static void main(String[] args) {
        SystemView systemView = new SystemView();
        systemView.print();

    }
}