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

相关文章

来自专栏静晴轩

你所不知道的setTimeout

JavaScript提供定时执行代码的功能,叫做定时器(timer),主要由setTimeout()和setInterval()这两个函数来完成。它们向任务队列...

39912
来自专栏专注 Java 基础分享

从源码解析TreeMap

     上篇文章我们介绍了HashMap集合,这是一个键值对集合,可以高效的按照键查找数值。但是它有一个缺陷:数据如果是无序的可以是很高效的,但是如果数据...

1928
来自专栏码云1024

AVL平衡二叉树中旋转操作的本质及其实现

           AVL (Adelson Velskii和 Landis)树是带有平衡条件的二叉查找树。这个平衡条件必须容易保持,而且它必须保证树的深度是...

4798
来自专栏有趣的Python

3-玩转数据结构-栈和队列

栈也是一种线性结构;相比数组,栈对应的操作是数组的子集;只能从一端添加元素,也只能从一端取出元素(这一端称之为栈顶)

2032
来自专栏大闲人柴毛毛

Java8新特性——StreamAPI(二)

1. 收集器简介 收集器用来将经过筛选、映射的流进行最后的整理,可以使得最后的结果以不同的形式展现。 collect方法即为收集器,它接收Collector接...

2765
来自专栏大闲人柴毛毛

贪心算法(五)——迪杰斯特拉算法

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

3509
来自专栏用户画像

5.2.4 邻接多重表

在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边,或需要对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。

551
来自专栏Java面试通关手册

精研3道简单的网易2018校招编程题

下面三道编程题来自网易2018校招编程题,这三道应该来说是非常简单的编程题了,这些题目大家稍微有点编程和数学基础的话应该没什么问题。看答案之前一定要自己先想一下...

1626
来自专栏程序生活

斯坦福tensorflow教程-实例代码简单代码关于占位符 placeholder与feed_dictvariable 变量

1003
来自专栏C/C++基础

C++运算符重载形式——成员函数or友元函数

运算符重载是C++多态的重要实现手段之一。通过运算符重载对运算符功能进行特殊定制,使其支持特定类型对象的运算,执行特定的功能,增强C++的扩展功能。

502

扫码关注云+社区