专栏首页大闲人柴毛毛图的遍历(BFS+DFS)

图的遍历(BFS+DFS)

图的遍历与树的遍历基本类似,但要注意两个不同: 1. 图中可能有环路,因此可能会导致死循环; 2. 一个图可能由多个独立的子图构成,因此一条路径走到头后要重新选择尚未遍历的起点。

图的邻接表数据结构请参见:图的邻接表示法Java版

宽度优先遍历

思路

  1. 选择一个尚未访问的起点,依次访问它的相邻结点;
  2. 若相邻结点还有相邻结点的话,再依次访问尚未访问的相邻结点;直到以该结点为起点的这条路径上所有的结点都已访问;
  3. 再选择一个尚未访问的结点作为起点,重复上述操作,直到所有结点都已访问为止;

代码实现

/**
 * 图的宽度优先遍历
 * PS:本函数用于选择未访问的起点
 * @param graph 图的邻接表
 */
public void BFS( Map<String,List<ENode>> graph ){
    // 记录结点是否被访问
    Map<String,Boolean> mark = new HashMap<>();
    for( String node : graph.keySet() ){
        mark.put( node, false );
    }

    for( String node : graph.keySet() ){
        if ( !mark.get(node) ) {
            // 选择一个起点
            String start = graph.get(node).id;
            BFS( graph, start );
        }
    }
}

/**
 * 图的宽度优先遍历
 * PS:本函数用于访问指定起点的路径上所有结点
 * @param graph 图的邻接表
 * @param start 起点
 */
private void BFS( Map<String,List<ENode>> graph, String start ){
    Queue<String> queue = new LinkedList<>();
    queue.offer( start );
    while( !queue.isEmpty() ){
        String curNode = queue.poll();// 取出一个结点
        System.out.println(curNode);// 访问结点
        mark.put(curNode,true);// 设为已访问
        // 将相邻结点依次丢进queue
        for( ENode edge : graph.get(curNode) ){
            if ( !mark.get(edge.id) ) {
                queue.offer( edge.id );
            }
        }
    }
}

深度优先遍历

思路

寻找一个尚未访问的结点作为起点,依次访问它的相邻结点,直到所有的相邻结点都已访问,再回溯到上一层,访问上层结点的第二个相邻结点,每个结点的访问过程都要一条道走到黑。

代码实现

/**
 * 图的深度优先遍历
 * PS:本函数用于选择未访问的起点
 * @param graph 图的邻接表
 */
public void DFS( Map<String,List<ENode>> graph ){
    // 记录结点是否被访问
    Map<String,Boolean> mark = new HashMap<>();
    for( String node : graph.keySet() ){
        mark.put( node, false );
    }

    for( String node : graph.keySet() ){
        if ( !mark.get(node) ) {
            // 选择一个起点
            String start = graph.get(node).id;
            DFS( graph, start );
        }
    }
}

/**
 * 图的深度优先遍历
 * PS:本函数用于访问某一结点为起点的所有相邻结点
 * @param graph 图的邻接表
 * @param start 起点
 */
public void DFS( Map<String,List<ENode>> graph, String start ){
    // 访问起点
    System.out.println(start);
    // 标记为已访问
    mark.put( start, true );
    // 依次访问所有相邻结点
    for( ENode edge : graph.get(start) ){
        if ( !mark.get( edge.id ) ) {
            String curNode = edge.id;
            DFS(graph, curNode);
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划法(五)——多段图问题

    问题描述 给定一个多段图,求出多段图中的最短路径和最短路径长度。 什么是多段图? 多段图是一个有向、无环、带权 图。 有且仅有一个起始结点(原点source...

    大闲人柴毛毛
  • 贪心算法(五)——迪杰斯特拉算法

    问题描述 给一个有向无环带权图,并给一个起点,求出该原点到所有顶点的最短路径。 ? 数据结构 dis: Map<String,Integer> dis; ...

    大闲人柴毛毛
  • 剑指offer代码解析——面试题25二叉树中和为某一值的路径

    题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

    大闲人柴毛毛
  • Jsoup代码解读之六-parser(下)

    读Jsoup源码并非无聊,目的其实是为了将webmagic做的更好一点,毕竟parser也是爬虫的重要组成部分之一。读了代码后,收获也不少,对HTML的知识也更...

    哲洛不闹
  • GIS的核心价值——服务

    注:本观点仅代表个人观点,与任何人员或者组织无任何关系,如有雷同或者相似之处,只能说明我们对GIS的理解相同,无抄袭之嫌。     写这个题目,源于前两天...

    lzugis
  • 新的一年,新的希望,新的努力

    2014年1月22日,国务院办公厅以国办发〔2014〕2号印发《关于促进地理信息产业发展的意见》,该《意见》分充分认识发展地理信息产业的重大意义、总体要求、推动...

    lzugis
  • 如何批量印刷防伪标签、不干胶标签?

    防伪标签、不干胶标签,只需从底纸上剥离,轻轻一按,即可贴到各种基材的表面,也可使用贴标机在生产线上自动贴标。常见的有药品标签、食品标签、酒标签、电池标签、外箱标...

    用户6457849
  • 《ArcGIS 地理信息系统教程》概念笔记

    之前研究了 GIS,接触到了很多 GIS 的概念。因此找了《 ArcGIS 地理信息系统教程(第 4 版)》来看。书的版本比较老了,不过一些基本概念还是想通的,...

    amc
  • 标签打印软件如何实现不同标签打印不同份数

    前两天有人咨询小编标签打印软件中不同标签打印不同份数是如何实现的,大家都知道标签重复打印的份数如果一样,直接在标签打印软件中设置就行,但是,如果要实现不同标签批...

    中琅软件
  • 浏览器解析与编码顺序及xss挖掘绕过全汇总

    在以往的培训和渗透过程中,发现很多渗透人员尤其是初学者在挖掘xss漏洞时,很容易混淆浏览器解析顺序和解码顺序,对于html和js编码、解码和浏览器解析顺序、哪些...

    Jayway

扫码关注云+社区

领取腾讯云代金券