↑点击上面"算法半岛"
关注"算法半岛"第一时间接收最新文章
DFS理解
深度优先搜索(Depth First Search, DFS)可以理解为走迷宫,假设当一个人走迷宫的时候,会遇到岔路口,面对多条路选择时,可以先随便选择一条,走着走着发现如果走不通了,可以退回到上一个岔路口,然后重新选择一条,用同样的方法继续走,直到直到出口为止。这样的策略即为DFS。
接下来我们将DFS应用到图的搜索中,如下图所示:
在完成相应的 java
代码前,我们先解释相关函数及参数的含义:
HashMap<Integer,LinkedList<Integer>>graph
:我们使用一个 HashMap
来存储图,其中 HashMap
中的 key
为图的顶点, LinkedList<Integer>>
为与该顶点相连的顶点;HashMap<Integer,Boolean>visited
:我们使用一个 visited
用来记录顶点是否被访问,用来避免顶点被重复访问;visit(HashMap<Integer,LinkedList<Integer>>graph,HashMap<Integer,Boolean>visited,Integerstart)
:该函数为DFS的主体部分,用来遍历各个顶点。 具体 java
代码如下所示:
import java.util.HashMap;import java.util.LinkedList;
public class TestDFS {
private static void dfs(HashMap<Integer, LinkedList<Integer>> graph, HashMap<Integer, Boolean> visited){ visit(graph, visited, 1); visit(graph, visited, 2); }
private static void visit(HashMap<Integer, LinkedList<Integer>> graph, HashMap<Integer, Boolean> visited, Integer start){ // 如果该顶点没有被访问,则访问该顶点 if (!visited.containsKey(start)){ System.out.println("当前进入节点为:" + start); visited.put(start, true); // 访问该顶点的相连顶点 for (Integer i : graph.get(start)){ if (!visited.containsKey(i)){ visit(graph,visited, i); // 递归访问相连顶点 } } System.out.println("当前离开节点为:" + start); } }
public static void main(String[] args) {
// 构造各个顶点 LinkedList<Integer> v1 = new LinkedList<>(); v1.add(2); v1.add(3); v1.add(4); LinkedList<Integer> v2 = new LinkedList<>(); v2.add(1); v2.add(3); LinkedList<Integer> v3 = new LinkedList<>(); v3.add(1); v3.add(2); LinkedList<Integer> v4 = new LinkedList<>(); v4.add(1); v4.add(5); v4.add(6); LinkedList<Integer> v5 = new LinkedList<>(); v5.add(4); LinkedList<Integer> v6 = new LinkedList<>(); v6.add(4); v6.add(7); LinkedList<Integer> v7 = new LinkedList<>(); v7.add(6);
// 构造图 HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>(); graph.put(1, v1); graph.put(2, v2); graph.put(3, v3); graph.put(4, v4); graph.put(5, v5); graph.put(6, v6); graph.put(7, v7);
// visited数组记录被访问的节点 HashMap<Integer, Boolean> visited = new HashMap<>();
dfs(graph, visited);
}}
输出结果:
当前进入节点为:1当前进入节点为:2当前进入节点为:3当前离开节点为:3当前离开节点为:2当前进入节点为:4当前进入节点为:5当前离开节点为:5当前进入节点为:6当前进入节点为:7当前离开节点为:7当前离开节点为:6当前离开节点为:4当前离开节点为:1