數(shù)據(jù)結(jié)構(gòu)與算法系列 - 深度優(yōu)先和廣度優(yōu)先

作者：一角錢技術(shù) 2020-10-17 11:14:19

開發(fā) 前端算法

本篇討論深度優(yōu)先搜索和廣度優(yōu)先搜索相關(guān)內(nèi)容。

前言

數(shù)據(jù)結(jié)構(gòu)與算法系列(完成部分)：

時(shí)間復(fù)雜度和空間復(fù)雜度分析
數(shù)組的基本實(shí)現(xiàn)和特性
鏈表和跳表的基本實(shí)現(xiàn)和特性
棧、隊(duì)列、優(yōu)先隊(duì)列、雙端隊(duì)列的實(shí)現(xiàn)與特性
哈希表、映射、集合的實(shí)現(xiàn)與特性
樹、二叉樹、二叉搜索樹的實(shí)現(xiàn)與特性
堆和二叉堆的實(shí)現(xiàn)和特性
圖的實(shí)現(xiàn)和特性
遞歸的實(shí)現(xiàn)、特性以及思維要點(diǎn)
分治、回溯的實(shí)現(xiàn)和特性
深度優(yōu)先搜索、廣度優(yōu)先搜索的實(shí)現(xiàn)和特性
貪心算法的實(shí)現(xiàn)和特性
二分查找的實(shí)現(xiàn)和特性
動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)及關(guān)鍵點(diǎn)
Tire樹的基本實(shí)現(xiàn)和特性
并查集的基本實(shí)現(xiàn)和特性
剪枝的實(shí)現(xiàn)和特性
雙向BFS的實(shí)現(xiàn)和特性
啟發(fā)式搜索的實(shí)現(xiàn)和特性
AVL樹和紅黑樹的實(shí)現(xiàn)和特性
位運(yùn)算基礎(chǔ)與實(shí)戰(zhàn)要點(diǎn)
布隆過濾器的實(shí)現(xiàn)及應(yīng)用
LRU Cache的實(shí)現(xiàn)及應(yīng)用
初級(jí)排序和高級(jí)排序的實(shí)現(xiàn)和特性
字符串算法

PS：大部分已經(jīng)完成在公眾號(hào)或者GitHub上，后面陸續(xù)會(huì)在頭條補(bǔ)充鏈接(不允許有外部鏈接)

本篇討論深度優(yōu)先搜索和廣度優(yōu)先搜索相關(guān)內(nèi)容。

關(guān)于搜索&遍歷

對(duì)于搜索來說，我們絕大多數(shù)情況下處理的都是叫 “所謂的暴力搜索” ，或者是說比較簡單樸素的搜索，也就是說你在搜索的時(shí)候沒有任何所謂的智能的情況在里面考慮，很多情況下它做的一件事情就是把所有的結(jié)點(diǎn)全部遍歷一次，然后找到你要的結(jié)果。

基于這樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)，如果這個(gè)數(shù)據(jù)結(jié)構(gòu)本身是沒有任何特點(diǎn)的，也就是說是一個(gè)很普通的樹或者很普通的圖。那么我們要做的一件事情就是遍歷所有的結(jié)點(diǎn)。同時(shí)保證每個(gè)點(diǎn)訪問一次且僅訪問一次，最后找到結(jié)果。

那么我們先把搜索整個(gè)先化簡情況，我們就收縮到在樹的這種情況下來進(jìn)行搜索。

如果我們要找到我們需要的一個(gè)值，在這個(gè)樹里面我們要怎么做？那么毫無疑問就是從根這邊開始先搜左子樹，然后再往下一個(gè)一個(gè)一個(gè)一個(gè)點(diǎn)走過去，然后走完來之后再走右子樹，直到找到我們的點(diǎn)，這就是我們所采用的方式。

再回到我們數(shù)據(jù)結(jié)構(gòu)定義，它只有左子樹和右子樹。

我們要實(shí)現(xiàn)這樣一個(gè)遍歷或者搜索的話，毫無疑問我們要保證的事情就是

每個(gè)結(jié)點(diǎn)都要訪問一次
每個(gè)結(jié)點(diǎn)僅僅要訪問一次
對(duì)于結(jié)點(diǎn)訪問的順序不限
深度優(yōu)先：Depth First Search
廣度優(yōu)先：Breadth First Search

僅訪問一次的意思就是代表我們?cè)谒阉髦校覀儾幌胱鲞^多無用的訪問，不然的話我們的訪問的效率會(huì)非常的慢。

當(dāng)然的話還可以有其余的搜索，其余的搜索的話就不再是深度優(yōu)先或者廣度優(yōu)先了，而是按照優(yōu)先級(jí)優(yōu)先。當(dāng)然你也可以隨意定義，比如說從中間優(yōu)先類似于其他的東西，但只不過的話你定義的話要有現(xiàn)實(shí)中的場(chǎng)景。所以你可以認(rèn)為是一般來說就是深度優(yōu)先、廣度優(yōu)先，另外的話就是優(yōu)先級(jí)優(yōu)先。按照優(yōu)先級(jí)優(yōu)先搜索的話，其實(shí)更加適用于現(xiàn)實(shí)中的很多業(yè)務(wù)場(chǎng)景，而這樣的算法我們一般把它稱為啟發(fā)式搜索，更多應(yīng)用在深度學(xué)習(xí)領(lǐng)域。而這種比如說優(yōu)先級(jí)優(yōu)先的話，在很多時(shí)候現(xiàn)在已經(jīng)應(yīng)用在各種推薦算法和高級(jí)的搜索算法，讓你搜出你中間最感興趣的內(nèi)容，以及每天打開抖音、快手的話就給你推薦你最感興趣的內(nèi)容，其實(shí)就是這個(gè)原因。

深度優(yōu)先搜索(DFS)

遞歸寫法

遞歸的寫法，一開始就是遞歸的終止條件，然后處理當(dāng)前的層，然后再下轉(zhuǎn)。

那么處理當(dāng)前層的話就是相當(dāng)于訪問了結(jié)點(diǎn) node，然后把這個(gè)結(jié)點(diǎn) node 加到已訪問的結(jié)點(diǎn)里面去;
那么終止條件的話，就是如果這個(gè)結(jié)點(diǎn)之前已經(jīng)訪問過了，那就不管了;
那么下轉(zhuǎn)的話，就是走到它的子結(jié)點(diǎn)，二叉樹來說的話就是左孩子和右孩子，如果是圖的話就是連同的相鄰結(jié)點(diǎn)，如果是多叉樹的話這里就是一個(gè)children,然后把所有的children的話遍歷一次。

1.二叉樹模版

Java 版本

//C/C++ 
//遞歸寫法： 
map<int, int> visited; 
 
void dfs(Node* root) { 
  // terminator 
  if (!root) return ; 
 
  if (visited.count(root->val)) { 
    // already visited 
    return ; 
  } 
 
  visited[root->val] = 1; 
 
  // process current node here.  
  // ... 
  for (int i = 0; i < root->children.size(); ++i) { 
    dfs(root->children[i]); 
  } 
  return ; 
}

Python 版本

#Python 
visited = set()  
 
def dfs(node, visited): 
    if node in visited: # terminator 
        # already visited  
        return  
 
    visited.add(node)  
 
    # process current node here.  
    ... 
    for next_node in node.children():  
        if next_node not in visited:  
            dfs(next_node, visited)

C/C++ 版本

//C/C++ 
//遞歸寫法： 
map<int, int> visited; 
 
void dfs(Node* root) { 
  // terminator 
  if (!root) return ; 
 
  if (visited.count(root->val)) { 
    // already visited 
    return ; 
  } 
 
  visited[root->val] = 1; 
 
  // process current node here.  
  // ... 
  for (int i = 0; i < root->children.size(); ++i) { 
    dfs(root->children[i]); 
  } 
  return ; 
}

JavaScript版本

visited = set()  
def dfs(node, visited): 
    if node in visited: # terminator 
        # already visited  
        return  
    visited.add(node)  
    # process current node here.  
    ... 
    for next_node in node.children():  
      if next_node not in visited:  
        dfs(next_node, visited)

2.多叉樹模版

visited = set()  
def dfs(node, visited): 
    if node in visited: # terminator 
        # already visited  
        return  
    visited.add(node)  
    # process current node here.  
    ... 
    for next_node in node.children():  
      if next_node not in visited:  
        dfs(next_node, visited)

非遞歸寫法

Python版本

#Python 
def DFS(self, tree):  
 
    if tree.root is None:  
        return []  
 
    visited, stack = [], [tree.root] 
 
    while stack:  
        node = stack.pop()  
        visited.add(node) 
 
        process (node)  
        nodes = generate_related_nodes(node)  
        stack.push(nodes)  
 
    # other processing work  
    ...

C/C++版本

//C/C++ 
//非遞歸寫法： 
void dfs(Node* root) { 
  map<int, int> visited; 
  if(!root) return ; 
 
  stack<Node*> stackNode; 
  stackNode.push(root); 
 
  while (!stackNode.empty()) { 
    Node* node = stackNode.top(); 
    stackNode.pop(); 
    if (visited.count(node->val)) continue; 
    visited[node->val] = 1; 
 
 
    for (int i = node->children.size() - 1; i >= 0; --i) { 
        stackNode.push(node->children[i]); 
    } 
  } 
 
  return ; 
}

遍歷順序

我們看深度優(yōu)先搜索或者深度優(yōu)先遍歷的話，它的整個(gè)遍歷順序毫無疑問根節(jié)點(diǎn) 1 永遠(yuǎn)最先開始的，接下來往那個(gè)分支走其實(shí)都一樣的，我們簡單起見就是從最左邊開始走，那么它深度優(yōu)先的話就會(huì)走到底。

參考多叉樹模版我們可以在腦子里面或者畫一個(gè)圖把它遞歸起來的話，把遞歸的狀態(tài)樹畫出來，就是這么一個(gè)結(jié)構(gòu)。

就比如說它開始剛進(jìn)來的話，傳的是 root 的話，root 就會(huì)先放到 visited 里面，表示 root 已經(jīng)被 visit,被 visited之后就從 root.childern里面找 next_node，所有它的next_node都沒有被訪問過的，所以它就會(huì)先訪問最左邊的這個(gè)結(jié)點(diǎn)，這里注意當(dāng)它最左邊這個(gè)結(jié)點(diǎn)先拿出來了，判斷沒有在 visited里面，因?yàn)槌?root之外其他結(jié)點(diǎn)都沒有被 visited過，那么沒有的話它就直接調(diào)dfs，next_node 就是把最左邊結(jié)點(diǎn)放進(jìn)去，再把 visited也一起放進(jìn)去。
遞歸調(diào)用的一個(gè)特殊，它不會(huì)等這個(gè)循環(huán)跑完，它就直接推進(jìn)到下一層了，也就是當(dāng)前夢(mèng)境的話這里寫了一層循環(huán)，但是在第一層循環(huán)的時(shí)候，我就要開始下鉆到新的一層夢(mèng)境里面去了。

圖的遍歷順序

廣度優(yōu)先搜索（BFS）

廣度優(yōu)先遍歷它就不再是用遞歸也不再是用棧了，而是用所謂的隊(duì)列。你可以把它想象成一個(gè)水滴，滴到1這個(gè)位置，然后它的水波紋一層一層一層擴(kuò)散出去就行了。

兩者對(duì)比

BFS代碼模板

//Java 
public class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
 
    TreeNode(int x) { 
        val = x; 
    } 
} 
 
public List<List<Integer>> levelOrder(TreeNode root) { 
    List<List<Integer>> allResults = new ArrayList<>(); 
    if (root == null) { 
        return allResults; 
    } 
    Queue<TreeNode> nodes = new LinkedList<>(); 
    nodes.add(root); 
    while (!nodes.isEmpty()) { 
        int size = nodes.size(); 
        List<Integer> results = new ArrayList<>(); 
        for (int i = 0; i < size; i++) { 
            TreeNode node = nodes.poll(); 
            results.add(node.val); 
            if (node.left != null) { 
                nodes.add(node.left); 
            } 
            if (node.right != null) { 
                nodes.add(node.right); 
            } 
        } 
        allResults.add(results); 
    } 
    return allResults; 
}

# Python 
def BFS(graph, start, end): 
    visited = set() 
    queue = []  
    queue.append([start])  
    while queue:  
        node = queue.pop()  
        visited.add(node) 
        process(node)  
        nodes = generate_related_nodes(node)  
        queue.push(nodes) 
    # other processing work  
    ...

// C/C++ 
void bfs(Node* root) { 
  map<int, int> visited; 
  if(!root) return ; 
 
  queue<Node*> queueNode; 
  queueNode.push(root); 
 
  while (!queueNode.empty()) { 
    Node* node = queueNode.top(); 
    queueNode.pop(); 
    if (visited.count(node->val)) continue; 
    visited[node->val] = 1; 
 
    for (int i = 0; i < node->children.size(); ++i) { 
        queueNode.push(node->children[i]); 
    } 
  } 
 
  return ; 
}

//JavaScript 
const bfs = (root) => { 
  let result = [], queue = [root] 
  while (queue.length > 0) { 
    let level = [], n = queue.length 
    for (let i = 0; i < n; i++) { 
      let node = queue.pop() 
      level.push(node.val)  
      if (node.left) queue.unshift(node.left) 
      if (node.right) queue.unshift(node.right) 
    } 
    result.push(level) 
  } 
  return result 
};