图的遍历(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 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

剑指Offer-把数组排成最小的数

题目描述 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成...

2675
来自专栏Java成神之路

Spring_总结_04_高级配置(三)之处理歧义

本文承接上一节:Spring_总结_04_高级配置(二)之条件注解@Conditional

724
来自专栏IT可乐

Java数据结构和算法(十四)——堆

  在Java数据结构和算法(五)——队列中我们介绍了优先级队列,优先级队列是一种抽象数据类型(ADT),它提供了删除最大(或最小)关键字值的数据项的方法,插入...

32111
来自专栏架构说

leetcode538. 把二叉搜索树转换为累加树

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater

803
来自专栏desperate633

LintCode 恢复IP地址题目分析

[ "255.255.11.135", "255.255.111.35" ] (顺序无关紧要)

591
来自专栏Java技术

初探Java源码之LinkedList

上篇文章我们分析了常见的ArrayList源码,它的内部是由一个数组来实现的。那么今天,我们来分析另一个常见的类LinkedList。本文分析都来自Java8。...

892
来自专栏海天一树

二叉树的分层遍历

给定一棵二叉树,要求从上到下从左到右分层输出该二叉树的节点值。 ? bitree.png 一、递归法 二叉树本身就带有递归属性,通常我们可以用递归方法解决。假设...

2647
来自专栏尾尾部落

[算法总结] 一文搞懂面试链表题

链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。

481
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题17合并两个排序的链表

本题的详细解析均在代码注释中: /** * 题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。 * @author 大闲人...

3777
来自专栏猿人谷

判断单链表是否存在环

周末参加完美世界校园招聘中就有一道判断单链表是否有环的编程题。 写一个C/C++函数,来判断一个单链表是否具有环,如果存在环,则给出环的入口点。 有一个单链表,...

1799

扫描关注云+社区