前言

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

1. 時間復(fù)雜度和空間復(fù)雜度分析
2. 數(shù)組的基本實現(xiàn)和特性
3. 鏈表和跳表的基本實現(xiàn)和特性
4. 棧、隊列、優(yōu)先隊列、雙端隊列的實現(xiàn)與特性
5. 哈希表、映射、集合的實現(xiàn)與特性
6. 樹、二叉樹、二叉搜索樹的實現(xiàn)與特性
7. 堆和二叉堆的實現(xiàn)和特性
8. 圖的實現(xiàn)和特性
9. 遞歸的實現(xiàn)、特性以及思維要點
10. 分治、回溯的實現(xiàn)和特性
11. 深度優(yōu)先搜索、廣度優(yōu)先搜索的實現(xiàn)和特性
12. 貪心算法的實現(xiàn)和特性
13. 二分查找的實現(xiàn)和特性
14. 動態(tài)規(guī)劃的實現(xiàn)及關(guān)鍵點
15. Tire樹的基本實現(xiàn)和特性
16. 并查集的基本實現(xiàn)和特性
17. 剪枝的實現(xiàn)和特性
18. 雙向BFS的實現(xiàn)和特性
19. 啟發(fā)式搜索的實現(xiàn)和特性
20. AVL樹和紅黑樹的實現(xiàn)和特性
21. 位運算基礎(chǔ)與實戰(zhàn)要點
22. 布隆過濾器的實現(xiàn)及應(yīng)用
23. LRU Cache的實現(xiàn)及應(yīng)用
24. 初級排序和高級排序的實現(xiàn)和特性
25. 字符串算法

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

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

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

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

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

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

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

 

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

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

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

僅訪問一次的意思就是代表我們在搜索中，我們不想做過多無用的訪問，不然的話我們的訪問的效率會非常的慢。

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

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

遞歸寫法

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

• 那么處理當(dāng)前層的話就是相當(dāng)于訪問了結(jié)點 node，然后把這個結(jié)點 node 加到已訪問的結(jié)點里面去;
• 那么終止條件的話，就是如果這個結(jié)點之前已經(jīng)訪問過了，那就不管了;
• 那么下轉(zhuǎn)的話，就是走到它的子結(jié)點，二叉樹來說的話就是左孩子和右孩子，如果是圖的話就是連同的相鄰結(jié)點，如果是多叉樹的話這里就是一個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)先遍歷的話，它的整個遍歷順序毫無疑問根節(jié)點 1 永遠(yuǎn)最先開始的，接下來往那個分支走其實都一樣的，我們簡單起見就是從最左邊開始走，那么它深度優(yōu)先的話就會走到底。

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

 

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

圖的遍歷順序

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

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

兩者對比

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 
};