首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图的遍历(BFS+DFS)

图的遍历(BFS+DFS)

作者头像
大闲人柴毛毛
发布2018-03-12 10:42:48
1K0
发布2018-03-12 10:42:48
举报
文章被收录于专栏:大闲人柴毛毛大闲人柴毛毛

图的遍历与树的遍历基本类似,但要注意两个不同: 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);
        }
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年04月12日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 宽度优先遍历
    • 思路
      • 代码实现
      • 深度优先遍历
        • 思路
          • 代码实现
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档