圖搜尋政策
這裡的“圖搜尋政策”應該怎麼了解呢？
首先，是“圖搜尋”，所謂圖無非就是由節點和邊組成的，那麼圖搜尋也就是将這個圖中所有的節點和邊都通路一遍。
其次是“政策”：
==> 如果就直接給你一個圖，要怎麼樣才能将所有的節點和邊都通路一遍呢？
這裡可以考慮一個非常非常大并且結構複雜的圖，那麼當拿到這個圖的時候資訊龐雜無比，你不知道裡面有多少個節點，有多少條邊，不知道節點和邊之間是怎樣錯綜複雜的關系，不知道有多少連通子圖......
對這樣的圖進行搜尋會讓人一下子摸不着頭緒，這時候肯定會想到，得有一個入手點才行！這是一個很通用的解決問題的政策，當整體過于複雜的時候不如試着從一個很小的局部開始一點點梳理脈絡。
這個入手點一般是某個節點。
==> 有了一個入手點之後，要怎樣繼續去搜尋其他的節點和邊呢？
這時候會考慮，從我已有的知識來說，我目前隻知道一個搜尋的起點（記為source），以及關于這個起點的一些資訊：與source相連的邊的集合，與source相鄰的節點集合。不過這兩個資訊其實是重合的，如果我現在從source出發去通路一條與source相連的邊，其實也就是通路了這條邊另一頭的節點（source的一個鄰居）。
當我走了這一條邊之後，到達source的這個鄰居節點之後，又會得到與這個鄰居節點相鄰的邊以及它的鄰居......
也就是說，在每一個時間截面（或者說選擇節點）上，我都有很多選擇——我有一個可以通路但還沒有通路的節點的集合，此時我會從這個節點集合中選出一個節點，想前走一步，每探索一步，我對這個圖的了解就更深一步（如果說有一個已經通路過的節點的集合，那麼這個集合中節點的個數就可以了解為深入的程度），但這樣的深入并非永無止境，這個圖總會周遊完（總會到達這樣一個選擇節點：此時沒有任何可以繼續通路的節點了），是以這個探索會像一個先膨脹再收縮的過程（或者說像一個回力镖？），總會回到已經通路過的節點上來，這時候就不必再繼續下去了，再繼續下去對 “周遊更多的節點和邊” 這一目标沒有任何價值。
于是我得到了一個初步的搜尋思路：
我有一個可以通路但還沒有通路的節點的集合（記為Package），初始時這個集合中隻有我一個節點。
每通路一個節點，都有可能會向這個Package中裝入一些新的節點（目前通路的節點的鄰居中，還沒有通路過的那些節點），當然也可能不會。
我每次從這個Package中取一個節點，然後更新一下Package的内容，然後再取一個節點......就這樣一直重複直到Package為空，這時就已經将從source所在的那個連通子圖全部周遊完了。
==> 每次取出一個節點？
對于剛剛得出的搜尋政策，還有一個值得思考的地方：每次取一個節點？每次取哪個節點？
而如何決定每一次取出哪一個節點這個問題就是所謂的“政策”。
當确定了“政策”之後，還需要考慮Package用什麼資料結構來存儲，要選擇一個最适合于搜尋政策的資料結構。
畫外音：不能狹隘地認為一說到圖搜尋或者周遊圖，不是DFS就是BFS，雖然确實這兩種是最最常用而且能高效地解決很多問題的搜尋政策。但是我也可以簡單地每次就随機取一個節點進行通路，或者說每次先把剩餘未通路鄰居最多的節點拿出來通路，或者說每次把距離source最近的節點拿出來通路等等。我這裡隻是随便舉一些例子，我想說的是，圖搜尋的政策有千千萬萬種，我們不能局限自己的思路，當拿到一個問題時，應該想着，怎麼樣為這個問題服務，而不是直接就開始想“這題用DFS能不能做？不能就用BFS”。
深度優先搜素（DFS）& 廣度優先搜尋（BFS）
跟着上面的思路來考慮DFS和BFS的搜尋政策：
- DFS：每次從Package中選出距離source最遠的節點進行通路。
- BFS：每次從Package中選出距離source最近的節點進行通路。
如果在某一個選擇節點有多個距離source最近/遠的節點，選哪一個都可以，具體選哪個現在暫時無法決定，這個問題先留着之後再考慮。
在前面的“初步搜尋思路”中有一個很重要的細節，回顧一下我們是如何更新Package的？
每通路一個節點，都有可能會向這個Package中裝入一些新的節點（目前通路的節點的鄰居中，還沒有通路過的那些節點）...
如果在通路某個節點A時對Package進行了更新：
- DFS：A離source的距離（記為k）大于等于目前Package中的所有節點
==> A的鄰居中，還沒有被通路過的那些節點離source的距離（k+1）一定大于目前Package中的所有節點
==> 下一次通路的節點一定是這次剛剛加入Package的節點中的某一個
==> 典型的“後入先出”
==> Package用棧來存
==> 每次從棧頂取出一個節點，對其進行通路，并将它的 鄰居中還沒有被通路過的節點 壓棧
- BFS： 假設目前Package中距離source最近的節點構成一個集合S_k，假設它們離source為k
==> 每次從這個集合中選出一個節點，并将該節點的鄰居中還沒有被通路過的那些節點（離source的距離為k+1）放入Package中
==> 在通路S_k時加入到Package中的節點構成集合 S_k+1，以此類推
==> 這就意味着節點是按照他們和source的距離加入Package的，也是按照他們和source的距離離開Package的
==> 加入的順序 = 離開的順序
==> 典型的“先入先出”
==> Package用隊列來存
==> 每次從隊首取出一個節點，對其進行通路，并将它的 鄰居中還沒有被通路過的節點 放入隊尾
再回頭看剛才遺留的那個問題：如果在某一個選擇節點有多個距離source最近/遠的節點時，應該選哪一個？
在DFS中，顯然是選最後加入的那一個；在BFS中，是選最先加入的那一個。因為選哪一個其實都可以，按照這樣的方式取是最友善的，是以這個問題也就解決了。
到這裡就可以開始編碼實作了。
編碼實作
這裡采用《算法(第4版)》中的圖處理算法的設計模式：
1. DFS
因為DFS是用 “棧” 來控制順序的，是以有兩種寫法：一種是顯示地使用一個棧，用疊代的方式來實作；另一種是隐式地使用棧，用遞歸的方式實作。
1 #pragma once
2 #include <stack>
3 #include "Graph.h"
4 using namespace std;
5
6 class DepthFirstSearch {
7 private:
8 bool* mymarked; //在遞歸寫法中：某一個時間截面記錄已經通路過的節點
9 //在疊代寫法中：某一個時間截面記錄已經壓過棧的節點
10 //在dfs結束後記錄與s節點連通的所有節點
11
12 public:
13 DepthFirstSearch(Graph G, int s) {
14 //初始化輔助數組mymarked
15 mymarked = new bool[G.v()];
16 for (int i = 0; i < G.v(); i++)
17 mymarked[i] = false;
18
19 //深度優先搜尋
20 //dfs_recursion(G, s);
21 dfs_iteration(G, s);
22 }
23
24 void dfs_recursion(Graph G, int s) {
25 //Step1: 通路目前節點
26 mymarked[s] = true;
27
28 //Step2: 對于S的所有鄰居，如果沒有通路過的話，調用dfs自身來通路它
29 for (int i = 0; i < G.adj(s).size(); i++) {
30 if (mymarked[G.adj(s)[i]] == false)
31 dfs_recursion(G, G.adj(s)[i]);
32 }
33 }
34
35 void dfs_iteration(Graph G, int s) {
36 stack<int> S;
37
38 //Step0: 初始化棧：放入source節點
39 S.push(s);
40 mymarked[s] = true;
41
42 while (!S.empty()) {
43 //Step1: 取出棧頂元素進行通路
44 int cur = S.top();
45 S.pop();
46
47 //Step2: 将cur節點的鄰居節點中，尚未被通路過的節點壓棧
48 for (int i = 0; i < G.adj(cur).size(); i++) {
49 if (mymarked[G.adj(cur)[i]] == false) {
50 mymarked[G.adj(cur)[i]] = true;
51 S.push(G.adj(cur)[i]);
52 }
53 }
54 }
55 }
56
57 bool marked(int w) {
58 return mymarked[w];
59 }
60
61 }; 2. BFS
1 #pragma once
2 #include <queue>
3 #include "Graph.h"
4 using namespace std;
5
6 class BreadFirstSearch {
7 private:
8 bool* mymarked; //某一個時間截面記錄已經進入過隊列的節點
9 //在bfs結束後記錄與s節點連通的所有節點
10
11 public:
12 BreadFirstSearch(Graph G, int s) {
13 //初始化輔助數組mymarked
14 mymarked = new bool[G.v()];
15 for (int i = 0; i < G.v(); i++) {
16 mymarked[i] = false;
17 }
18
19 //廣度優先搜尋
20 bfs(G, s);
21 }
22
23 void bfs(Graph G, int s) {
24 queue<int> Q;
25
26 //Step0: 初始化隊列：放入source節點
27 Q.push(s);
28 mymarked[s] = true;
29
30 while (!Q.empty()) {
31 //Step1: 取出隊首元素進行通路
32 int cur = Q.front();
33 Q.pop();
34
35 //Step2: 将cur節點的鄰居節點中，尚未被通路過的節點放入隊尾
36 for (int i = 0; i < G.adj(cur).size(); i++) {
37 if (mymarked[G.adj(cur)[i]] == false) {
38 mymarked[G.adj(cur)[i]] = true;
39 Q.push(G.adj(cur)[i]);
40 }
41 }
42
43 }
44
45 }
46
47 bool marked(int w) {
48 return mymarked[w];
49 }
50
51 }; 值得注意的是：
在兩個疊代算法中，mymarked[i] == true的含義是：将該節點放入Package這個操作已經執行過了。
将節點i放入Package意味着它之後一定會被通路，而不是現在就被通路了。
從Package中取出節點i才意味着它被通路了。
是以将一個節點對應的mymarked[i]設為True的時機應該是将它放入Package時，而不是從Package中取出時。
DFS和BFS的對比
“深度優先搜尋和廣度優先搜尋是我們首先學習的幾種通用的圖搜尋的算法之一。
在搜尋中我們都會先将起點存入資料結構中，然後重複以下步驟直到資料結構被清空：
- 取其中的下一個頂點并标記它；
- 将 v 的所有相鄰而又未被标記的頂點加入資料結構。
這兩個算法的不同之處僅在于從資料結構中擷取下一個頂點的規則（對于廣度優先搜尋來說是最早加入的頂點，對于深度優先搜尋來說是最晚加入的頂點）。這種差異得到了處理圖的兩種完全不同的視角，盡管無論使用哪種規則，所有與起點連通的頂點和邊都會被檢查到。圖 4.1.19 和 圖 4.1.20 顯 示了深度優先搜尋和廣度優先搜尋處理樣圖 mediumG.txt 的過程，它們清晰地展示了兩種方法中搜尋路徑的不同。
- 深度優先搜尋不斷深入圖中并在棧中儲存了所有分叉的頂點；廣度優先搜尋則像扇面一般掃描圖，用一個隊列儲存通路過的最前端的頂點。
- 深度優先搜尋探索一幅圖的方式是尋找離起點更遠的頂點，隻在碰到死胡同時才通路近處的頂點；廣度優先搜尋則會首先覆寫起點附近的頂點，隻在臨近的所有頂點都被通路了之後才向前進。
- 深度優先搜尋的路徑通常較長而且曲折，廣度優先搜尋的路徑則短而直接。”
—— 《算法（第4版）》
畫外音：書中在介紹DFS之前還介紹了一個走迷宮的例子，這個例子對于了解DFS也很有價值。
![緒論-算法【資料結構與算法】總結[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)