Java数据结构54:图的深度优先遍历与广度优先遍历数据结构课程设计

野性酷女 2023-02-20 06:19 18阅读 0赞

## 54:图的深度优先遍历与广度优先遍历 ##

时间限制: 20000ms 内存限制: 131072kB

描述

给出一个无向图顶点和边的信息，输出这个无向图的深度优先遍历序列和广度优先遍历序列。从一个顶点出发如果有2个以上的顶点可以访问时，我们约定先访问编号大的那个顶点。示例输入对应的图如下图所示：

![format_png][]

输入

输入的第1行有2个整数m和n。表示图g有m个顶点和n条边。  
第2行是m个以空格隔开的字符串，依次是图中第1个顶点的名字，第2个顶点的名字.....第m个顶点的名字。  
此后还有n行，每行由2个字符串构成，分别是构成图中1条边的两个顶点。我们约定不会有重边。

输出

输出有2行。  
第1行是从第1个顶点出发对图g做深度优先遍历得到的顶点序列。  
第2行是从第1个顶点出发对图g做广度优先遍历得到的顶点序列。

样例输入

8 9
    v1 v2 v3 v4 v5 v6 v7 v8
    v1 v2
    v1 v3
    v1 v6
    v2 v3
    v2 v4
    v3 v4
    v4 v6
    v5 v6
    v7 v8

样例输出

v1 v6 v5 v4 v3 v2 v7 v8
    v1 v6 v3 v2 v5 v4 v7 v8

提示

注意：从一个顶点出发如果有2个以上的顶点可以访问时，我们约定先访问编号大的那个顶点。

### 首先声明，上课没听讲，代码瞎搞的，纯属做着玩，写得质量不好，但是能通过OpenJudge的测试，管他三七二一，反正我过了就行了，好的，废话不多说，直接上代码，拿去就能运行。 ###

import java.util.*;
    
    /**
     * @author baikunlong
     * @date 2020/6/23 10:55
     */
    public class Main {
        private static ArrayList<Graph> list = new ArrayList<>();
        private static ArrayList<Graph> visited;
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            scanner.nextLine();
            String[] names = scanner.nextLine().split(" ");
            for (int i = 0; i < names.length; i++) {
                list.add(new Graph(Integer.parseInt(names[i].substring(1))));
            }
            for (int i = 0; i < m; i++) {
                String[] strings = scanner.nextLine().split(" ");
                Graph graph = list.get(Integer.parseInt(strings[0].substring(1)) - 1);
                graph.list.add(list.get(Integer.parseInt(strings[1].substring(1)) - 1));
                graph = list.get(Integer.parseInt(strings[1].substring(1)) - 1);
                graph.list.add(list.get(Integer.parseInt(strings[0].substring(1)) - 1));
            }
    
            //开始深度遍历
            visited = new ArrayList<>();
            Graph cGraph = list.get(0);
            visited.add(cGraph);
            DFS(cGraph);
            for (int i = 0; i < visited.size(); i++) {
                System.out.print("v" + visited.get(i).gravity + " ");
            }
    
            System.out.println();
    
            //开始广度遍历
            visited = new ArrayList<>();
            //恢复访问状态
            for (int i = 0; i < list.size(); i++) {
                list.get(i).visited = false;
                list.get(i).preGraph = null;
            }
            cGraph = list.get(0);
            visited.add(cGraph);
            ArrayList<Graph> cGraphs = new ArrayList<>();
            cGraphs.add(cGraph);
            BFS(cGraphs);
    
            for (int i = 0; i < visited.size(); i++) {
                System.out.print("v" + visited.get(i).gravity + " ");
            }
        }
    
        /**
         * 广度优先遍历
         * @param cGraphs 当前点的连接点集合
         */
        private static void BFS(ArrayList<Graph> cGraphs) {
    //        System.out.println("set " + cGraphs);
            //是否还存在没访问的点
            boolean isEmpty = true;
            ArrayList<Graph> nextGraphs = new ArrayList<>();
            //遍历每个连接点
            for (int i = 0; i < cGraphs.size(); i++) {
                Graph cGraph = cGraphs.get(i);
                ArrayList<Graph> cList = cGraph.list;
                if (cList.size() != 0) {
                    cList.sort(Comparator.comparingInt(o -> (o.gravity)));
                    Collections.reverse(cList);
                    //把连接点的所有子连接点给访问了，还是遵循从大大小，上面已排序
                    for (int k = 0; k < cList.size(); k++) {
                        Graph graph = cList.get(k);
                        graph.preGraph = cGraph;
                        graph.visited = true;
                        if (!visited.contains(graph)){
                            visited.add(graph);
                            isEmpty = false;
                        }
                        //保存为下一层的连接点
                        nextGraphs.add(graph);
                    }
                }
            }
            //如果所有连接点都访问了
            if (isEmpty) {
                //遍历剩下的其他的未连接的点
                for (int i = 0; i < list.size(); i++) {
                    if (!list.get(i).visited) {
                        visited.add(list.get(i));
                        cGraphs = new ArrayList<>();
                        cGraphs.add(list.get(i));
                        BFS(cGraphs);
                    }
                }
            }else {
                //访问下一层
                BFS(nextGraphs);
            }
    
        }
    
        /**
         * 深度优先遍历
         * @param cGraph 当前点
         */
        private static void DFS(Graph cGraph) {
    //        System.out.println("set v" + cGraph.gravity);
            //设置被访问
            cGraph.visited = true;
            //如果被访问集合不包含则添加该点
            if (!visited.contains(cGraph))
                visited.add(cGraph);
            ArrayList<Graph> cList = cGraph.list;
            if (cList.size() == 0) {
                //如果该点的连接点为空，代表已到最深处，则回到上一个点
                DFS(cGraph.preGraph);
                return;
            }
            //根据权重排序，优先访问大的点
            cList.sort(Comparator.comparingInt(o -> (o.gravity)));
            Collections.reverse(cList);
    //        System.out.println(cList);
    
            //访问每一个连接点
            for (int i = 0; i < cList.size(); i++) {
                if (!cList.get(i).visited) {
                    cList.get(i).preGraph = cGraph;
                    cGraph = cList.get(i);
                    //递归访问下去，知道没有连接点为止
                    DFS(cGraph);
                    return;
                }
            }
            //如果没有回到起点则继续遍历
            if (cGraph.preGraph != null) {
                DFS(cGraph.preGraph);
            } else {
                //遍历剩下的未连接的点
                for (int i = 0; i < list.size(); i++) {
                    if (!list.get(i).visited) {
                        DFS(list.get(i));
                    }
                }
            }
        }
    
        static class Graph {
            //权重
            int gravity;
            //连接点
            ArrayList<Graph> list = new ArrayList<>();
            //是否访问
            boolean visited;
            //上一个点
            Graph preGraph;
    
            public Graph(int gravity) {
                this.gravity = gravity;
            }
    
            @Override
            public String toString() {
                return "Graph{" +
                        "gravity=" + gravity +
                        '}';
            }
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL21lZGlhLm9wZW5qdWRnZS5jbi9pbWFnZXMvdXBsb2FkLzE0MzM3NzE0NjAuSlBH?x-oss-process=image/format,png