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 + '}'; } } }
