图的深度优先遍历

简介: 图的深度优先遍历

图深度优先遍历:先用自己通俗易懂的话描述一下:从某个结点出发的一条路走到不能再走了,就返回到上一个结点,如果还是没有路就再返回到上一个结点。简称:一条路走到黑。

准备一个栈(记录深度优先遍历的路径)和HashSet(确保每个结点只进一次栈)。

并且打印的时机是进栈的时候,进栈就打印,所以栈弹出的时候就不要打印了。

栈弹出的时候,遍历当前结点的所有直接邻居,如果当前结点的直接邻居没有在HashSet里,就把父结点(当前结点)重新压入栈,直接邻居也压入栈,这个直接邻居也要压入HashSet,然后打印这个直接邻居。如果有不理解直接邻居的,建议先看看这篇文章——图结构的实现,从点到边再到图。这跟实现图的方式有关,跟宽度优先遍历一样,图的深度优先遍历只需要用到点结构。

放上一张图片,再结合核心代码供大家理解:

image.png

package com.harrison.class11;
import java.util.HashSet;
import java.util.Stack;
import com.harrison.class11.Code01_NodeEdgeGraph.Node;
public class Code03_DFS {
  public static void dfs(Node node) {
    if(node==null) {
      return ;
    }
    Stack<Node> stack=new Stack<Node>();
    HashSet<Node> set=new HashSet<>();
    stack.push(node);
    set.add(node);
    System.out.println(node.value);
    while(!stack.isEmpty()) {
      Node cur=stack.pop();
      for(Node next:cur.nexts) {
        if(!set.contains(next)) {
          stack.push(cur);
          stack.push(next);
          set.add(next);
          System.out.println(next.value);
          break;
        }
      }
    }
  }
}
相关文章
|
6月前
|
存储 算法
图的深度优先算法
图的深度优先算法
40 0
|
6月前
|
NoSQL 容器 消息中间件
图、图的遍历及图的拓扑排序
图、图的遍历及图的拓扑排序
|
存储 算法
图的广度优先遍历和深度优先遍历
本文主要是学习图的广度优先遍历和图的深度优先遍历
165 1
|
存储
图操作之邻接矩阵与邻接表的深度优先遍历
图操作之邻接矩阵与邻接表的深度优先遍历
175 0
|
存储 索引
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
78 0
|
算法
树与图的深度优先遍历
复习acwing算法基础课的内容,本篇为讲解基础算法:树与图的深度优先遍历,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
179 0
树与图的深度优先遍历
|
存储 算法 搜索推荐
C++实现图 - 05 拓扑排序
今天来讲另一个非常重要的知识点 —— 拓扑排序。咋一看好像是一个排序算法,然而它和排序扯不上半点关系,它可以用于判断我们的图中是否存在有向环。
610 0
C++实现图 - 05 拓扑排序
|
算法
树与图的广度优先遍历
复习acwing算法基础课的内容,本篇为讲解基础算法:树与图的广度优先遍历,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
102 0
树与图的广度优先遍历
|
存储 算法 C++
C++实现图 - 03 最小生成树
这一讲来讲一个图中非常重要的内容 —— 最小生成树,在此之前我们先来回顾一下生成树的概念。
226 0
C++实现图 - 03 最小生成树