锐客网

  1. 首页 > 生活百科 > it技术 > >

你必须会的DFS的递归实现与堆栈实现

IT知识递归实现

幽映每白日，清辉照衣裳。这篇文章主要讲述你必须会的DFS的递归实现与堆栈实现相关的知识，希望能为你提供帮助。


文章目录

  • ??一. 算法原理??
  • ??1.堆栈式实现方法??
  • ??2.递归式实现方法??
  • ??二.具体实现??
  • ??1.实例??
  • ??2.结果??
  • ??三.如何输出所有的路径？??
一. 算法原理相比于BFS利用队列实现中心扩散式搜索
DFS就是利用堆栈的思想(先进后出)，利用回溯算法，或者使用dfs递归，直观上看是一条路走到黑，如果找到南墙，便回到上个路口，继续一条路走到黑…如此往复，直到到达目标，所以称之为深度优先搜索。
1.堆栈式实现方法
  • 首先将根节点压入堆栈中。
  • 从堆栈中pop一个节点，并检验它是否为目标。
  • 如果找到目标，则结束搜索并回传结果。
  • 否则将它所有尚未检验过的直接子节点加入堆栈中。
  • 若堆栈为空，表示整张图都检查过了——亦即图中没有所搜索的目标。结束搜索并回传“找不到目标”。
  • 重复步骤2。
伪代码
stack.push(root)
while(!stack.isEmpty())
node = stack.pop()
for each neighbor node的相邻节点
if neighbor未被访问
stack.push(neightbor)
//记录路径
stack.parent = node
//其余操作...
todo...

2.递归式实现方法
  • 给定根节点
  • 遍历根节点所有未被访问的相邻节点
  • 如果找到目标，则结束搜索并传回结果
  • 否则将该相邻节点设置为新的根节点，重复步骤2
  • 若没有未被访问的相邻节点，则结束本分支的搜索并返回
  • 所有分支都遍历完毕，结束搜索并回传“找不到目标”。
【你必须会的DFS的递归实现与堆栈实现】伪代码：
DFS()
dfsVisit(root)

dfsVisit(node)
for each neighbor node的相邻节点
if neighbor没有访问过
//记录路径
neighbor.parent = root
//其他操作
todo..
dfs(neighbor)

二.具体实现选用常见的递归实现
package com.example.DFS;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DFS
// < 1, [2, 3]> 表示节点1的父节点是节点2，到源点距离为3
private Map< Integer, int[]> disTo;
/**
* @param edges 一个节点到其他节点的距离
*[[0, 1, 1], [1, 2, 2]] 表示点0到点1的距离为1，点1到点2的距离为2
* @param n所有节点个数1< = n < = 1000
* @param k源节点1< k < n
*/
public Map< Integer, int[]> DFS(int[][] edges, int n, int k)
//通过edges数组生成有向图
//< 0, < 1,2, 2,3> > 表示节点0有1，2两个相邻节点,距离分别为2, 3
Map< Integer, List< int[]> > graph = new HashMap< > ();
for(int[] edge:edges)
if(!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList< int[]> ());
graph.get(edge[0]).add(new int[]edge[1], edge[2]);

//初始化disTo
disTo = new HashMap< > ();
for(int i=0; i< n; i++)
if(i==k)
disTo.put(i, new int[]k, 0);
else disTo.put(i, new int[]-1, Integer.MAX_VALUE);

dfsVisit(graph, k);
return disTo;


/**
* dfs
* @param graph
* @param k
*/
private void dfsVisit(Map< Integer, List< int[]> > graph, int k)
if(graph.containsKey(k))
for(int[] edge:graph.get(k))
int[] temp = disTo.get(edge[0]);
//保证该节点未被访问
if(temp[0] == -1 & & temp[1] == Integer.MAX_VALUE)
//setParent 记录路径
temp[0] = k;
//setDisTo 记录距离
temp[1] = disTo.get(k)[1] + edge[1];
//递归实现
dfsVisit(graph, edge[0]);




/**
* 输出结果
* @param disTo
* @param end
*/
public void printPath(Map< Integer, int[]> disTo,int pathTo)
int distance = disTo.get(pathTo)[1];
List< Integer> path = new ArrayList< > ();
int temp = pathTo;
path.add(temp);
while (temp!=0 & & temp!=-1)
temp = disTo.get(temp)[0];
path.add(temp);

System.out.print("从初始节点到节点"+end+"的距离为"+distance+"\\n"
+"路径为：\\n"+path.get(0));
for(int i

    推荐阅读


    上一篇：基于Python网络爬虫的设计与实现毕业设计

    下一篇：基于Redis的分布式链家二手房房源数据爬虫系统 毕业设计