深度优先和广度优先算法详解

一、DFS 和 BFS 算法概述

1.什么是DFS和BFS？

DFS （Depth-First-Search）,称为深度优先搜索；BFS（Breadth-First-Search），称为广度优先搜索。

这二者都是在树和图的遍历中应用非常广泛的算法，那么再来看下遍历的定义：从初始点出发，按照某种

搜索方法对树或图中的每个节点均做一次且仅做一次的访问，访问具体节点所做的操作依赖于具体的问题。

在树的遍历算法中，我们经常会看到前序遍历、中序遍历、后续遍历、层序遍历等方法，其实前序遍历

就是深度优先搜索的一种实现，层序遍历就是对广度优先搜索的一种实现。树也可以看做是一种特殊的图，

树和图的遍历主要的区别就是树有根节点（指定的），而图需要我们自身指定开始遍历的节点。

2.DFS和BFS算法的核心思想

BFS和DFS都是图的遍历方法。它们具有一些共性的问题，比如都要避免节点的重复访问，具体的实践

中可以设置一个访问数组，数组中的每个元素代表一个节点，当节点被访问后数组中对应的元素赋一个特定

的值进行标记即可

DFS的搜索过程是这样的：

  • 先访问初始节点V

  • 从V未被访问的邻接点中选取一个W，从W出发进行DFS

  • 重复上述步骤即可

BFS的搜索过程是这样的：

  • 先访问图的初始节点V

  • 依次访问V节点的所有邻接节点V1，V2，V3...

  • 按照V1，V2，V3被访问的次序依次访问与它们相邻接的未被访问的节点

  • 重复上述过程

3.DFS和BFS算法效率分析

DFS和BFS的时间复杂度只与数据的底层存储结构相关，而与搜索的路径无关。当使用邻接矩阵存

储时，对于每一个被访问的节点，都要循环检测矩阵中的整整一行（n个元素），时间复杂度为O（n^2）

当使用邻接表来存储时，有2e个表节点，但只需要扫描e个节点即可完成遍历，加上访问n个头节点的

时间，时间复杂度为O（n+e）

DFS和BFS算法的空间复杂度相同，都是借用了堆栈或队列，为O（n）。递归在本质上也属于栈

二、DFS 和BFS 的算法实现

图在底层都是以邻接表或者邻接矩阵的方式来存储的，在Java、C++都可以使用表或者矩阵来进行定义

的，Python中可以使用字典来进行定义。解决图的BFS问题就是利用队列的先进先出的思想，队列可以保存

图中未遍历的节点；解决图的DFS问题是利用栈这种数据结构，递归和非递归的实现本质上都是先进后出。

1.DFS的算法实现

假设有这样一张图：

1j2RIS.png

（1）Python的实现

#定义一个图的结构  使用字典
graph = {
    'A':['B','C'],
    'B':['A','C','D'],
    'C':['A','B','D','E'],
    'D':['B','C','E','F'],
    'E':['C','D'],
    'F':['D']
}

#DFS算法的实现（非递归）
def DFS(graph,s):  #graph是一个图,s指的是开始节点
    stack=[]    #使用来列表来模拟队列
    stack.append(s)
    visited = set()  #利用集合元素的唯一性
    visited.add(s)
    while stack:
        vertex = stack.pop()  #拿出一个邻接点
        nodes = graph[vertex] #得到这个邻接点的所有邻接点，返回的是一个列表
        for node not in nodes:
            stack.append(node)
            visited.add(node)
        print(vertex)
    
#DFS算法的实现（递归）
visited = set()
def DFS(vertex,visited):
    visited.add(vertex)
    nodes = graph[vertex]
    for node in nodes:
        if node not in visited:
            DFS(node,visieted)
    print(vertex)

#BFS算法的实现 
def BFS(graph,s):   #graph是图,s是开始遍历的节点
    queue = []  #待使用的队列
    queue.append(s)
    visited = set()
    visited.add(s)
    while queue:
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for node in nodes:
            if node not in visited:
                queue.append(node)
                visited.add(node)
        print(vertex)

（2）Java中的实现

//DFS 算法
//1.使用邻接表 时间复杂度O（n+e）递归实现
public void DFS(int vertex){
    System.out.print(this.table[vertex].data + " ");
    this.visited[vertex] = true;
    for(ArcNode node = this.table[vertex].firstarc; node !=null; p = p.nextarc)
        if(this.visited[node.adjvex] == false)
            this.DFS(node.adjvex)
}

//2.使用邻接表  借助栈来实现 
public void DFS(int vertex){
    System.out.print(this.table[vertex].data + " ");
    this.visited[vertex] = true;
    ArrayDeque stack = new ArrayDeque();
    stack.addFirst(table[vertex]);
}

//3.使用邻接矩阵  时间复杂度O（n^2） 递归
public void DFS(int vertex){
    System.out.print(this.table[vertex] + " ");
    this.visited[vertex] = true;
    
    for(int i = 0;)
}
//省略

三、典型问题