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

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

描述

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

输入

输入的第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 +
                    '}';
        }
    }
}