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

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

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

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


描述


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

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


目录
相关文章
|
3月前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
74 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
3天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
17 2
|
5月前
|
存储 Java
Java学习笔记 List集合的定义、集合的遍历、迭代器的使用
Java学习笔记 List集合的定义、集合的遍历、迭代器的使用
|
3天前
|
数据采集 存储 算法
【C++数据结构——图】图的遍历(头歌教学实验平台习题) 【合集】
本文介绍了图的遍历算法,包括深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历通过递归方式从起始节点深入探索图,适用于寻找路径、拓扑排序等场景;广度优先遍历则按层次逐层访问节点,适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例,演示了如何实现这两种遍历方法,并附有测试用例及结果,帮助读者理解和实践图的遍历算法。
9 0
|
2月前
|
存储 Java 开发者
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
|
3月前
|
Java 程序员 编译器
Java|如何正确地在遍历 List 时删除元素
从源码分析如何正确地在遍历 List 时删除元素。为什么有的写法会导致异常,而另一些不会。
68 3
|
3月前
|
前端开发 小程序 Java
java基础:map遍历使用;java使用 Patten 和Matches 进行正则匹配;后端传到前端展示图片三种情况,并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配,以及后端向前端传输图片并保存到手机的三种情况。
36 1
|
3月前
|
存储 算法 Java
Java一分钟之-数组的创建与遍历
数组作为Java中存储和操作一组相同类型数据的基本结构,其创建和遍历是编程基础中的基础。通过不同的创建方式,可以根据实际需求灵活地初始化数组。而选择合适的遍历方法,则可以提高代码的可读性和效率。掌握这些基本技能,对于深入学习Java乃至其他编程语言的数据结构和算法都是至关重要的。
35 6
|
3月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
4月前
|
域名解析 分布式计算 网络协议
java遍历hdfs路径信息,报错EOFException
java遍历hdfs路径信息,报错EOFException
45 3