数据结构与算法-深度优先搜索
↑点击上面"算法半岛"
关注"算法半岛"第一时间接收最新文章
DFS理解
深度优先搜索(Depth First Search, DFS)可以理解为走迷宫，假设当一个人走迷宫的时候，会遇到岔路口，面对多条路选择时，可以先随便选择一条，走着走着发现如果走不通了，可以退回到上一个岔路口，然后重新选择一条，用同样的方法继续走，直到直到出口为止。这样的策略即为DFS。
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本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-06-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
