.jpg)
c++++中dfs遞歸調(diào)用棧可通過迷宮比喻理解，每次進(jìn)入新節(jié)點(diǎn)即將其信息壓入棧，回溯時(shí)彈出。調(diào)用棧深度反映搜索深度，過深可能導(dǎo)致棧溢出。處理環(huán)的方法是使用visited數(shù)組標(biāo)記已訪問節(jié)點(diǎn)，避免重復(fù)訪問；另一種方法是采用三種狀態(tài)（未訪問、正在訪問、已訪問）來檢測環(huán)。dfs與bfs的主要區(qū)別在于搜索方式：1.dfs盡可能深入探索路徑，適合路徑查找和環(huán)檢測；2.bfs逐層擴(kuò)展，適合尋找最短路徑和連通分量。選擇dfs的情況包括需要找到任意路徑、檢測圖環(huán)或內(nèi)存受限的場景，而bfs更適合需最短路徑或完全遍歷的問題。
深度優(yōu)先搜索（DFS）是一種用于遍歷或搜索樹或圖的算法。它的核心思想是盡可能深地搜索樹的分支。當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被發(fā)現(xiàn)為止。
#include <iostream> #include <vector> using namespace std; void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) { visited[node] = true; cout << node << " "; for (int neighbor : adj[node]) { if (!visited[neighbor]) { dfs(neighbor, adj, visited); } } } int main() { int n, m; // n: 節(jié)點(diǎn)數(shù)量, m: 邊的數(shù)量 cin >> n >> m; vector<vector<int>> adj(n); // 鄰接表 for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); // 如果是無向圖 } vector<bool> visited(n, false); // 從節(jié)點(diǎn)0開始DFS dfs(0, adj, visited); cout << endl; return 0; }
如何理解c++中DFS遞歸的調(diào)用棧？
想象一下，你在一座迷宮里，手里拿著一根線。你總是沿著一條路走到底，如果走到盡頭，就沿著線退回上一個(gè)路口，再選擇另一條路。這個(gè)“線”就是調(diào)用棧。
每次調(diào)用dfs函數(shù)，就像你在迷宮里走到了一個(gè)新的路口。這個(gè)路口的信息（節(jié)點(diǎn)編號、鄰接表、訪問標(biāo)記）都會被壓入調(diào)用棧。當(dāng)dfs函數(shù)到達(dá)一個(gè)沒有未訪問鄰居的節(jié)點(diǎn)時(shí)，函數(shù)執(zhí)行完畢，就像你走到了迷宮的死胡同。這時(shí)，函數(shù)會從調(diào)用棧中彈出，回到上一個(gè)路口，繼續(xù)搜索。
立即學(xué)習(xí)“C++免費(fèi)學(xué)習(xí)筆記（深入）”；
調(diào)用棧的深度反映了DFS搜索的深度。如果圖非常深，調(diào)用棧可能會變得很大，導(dǎo)致棧溢出。
如何處理C++ DFS中的環(huán)？
在圖中存在環(huán)的情況下，DFS可能會陷入無限循環(huán)。解決這個(gè)問題的方法是使用一個(gè)visited數(shù)組來跟蹤已經(jīng)訪問過的節(jié)點(diǎn)。在上面的代碼示例中，visited[node] = true;這一行代碼就是用來標(biāo)記節(jié)點(diǎn)已經(jīng)被訪問過。在遞歸調(diào)用dfs函數(shù)之前，會檢查鄰居節(jié)點(diǎn)是否已經(jīng)被訪問過if (!visited[neighbor])，如果已經(jīng)被訪問過，則跳過該鄰居節(jié)點(diǎn)，避免無限循環(huán)。
另一種方法是使用三種狀態(tài)來標(biāo)記節(jié)點(diǎn)：未訪問、正在訪問、已訪問。當(dāng)?shù)谝淮斡龅揭粋€(gè)節(jié)點(diǎn)時(shí)，將其標(biāo)記為“正在訪問”。當(dāng)該節(jié)點(diǎn)的所有鄰居都訪問完畢后，將其標(biāo)記為“已訪問”。如果在DFS過程中遇到一個(gè)“正在訪問”的節(jié)點(diǎn)，則說明存在環(huán)。
C++ DFS與BFS的區(qū)別是什么？什么時(shí)候應(yīng)該使用DFS？
DFS和BFS都是圖遍歷算法，但它們的搜索方式不同。DFS像是一個(gè)“深度優(yōu)先”的探險(xiǎn)家，總是盡可能深地探索一條路徑，直到無法繼續(xù)前進(jìn)才回溯。而BFS則像是一個(gè)“廣度優(yōu)先”的偵察兵，從起點(diǎn)開始，一層一層地向外擴(kuò)展，先訪問所有距離起點(diǎn)為1的節(jié)點(diǎn)，再訪問所有距離起點(diǎn)為2的節(jié)點(diǎn)，以此類推。
選擇DFS還是BFS取決于具體的問題：
- DFS的優(yōu)點(diǎn)：
- 更容易實(shí)現(xiàn)。
- 占用空間更少（在某些情況下）。
- 可以用于檢測環(huán)。
- 可以用于解決路徑搜索問題，例如迷宮求解。
- BFS的優(yōu)點(diǎn)：
- 可以找到最短路徑（在無權(quán)圖中）。
- 可以用于尋找連通分量。
如果問題需要找到最短路徑，或者需要遍歷圖的所有節(jié)點(diǎn)，BFS通常是更好的選擇。如果問題只需要找到一條路徑，或者需要檢測環(huán)，DFS可能更適合。 此外，如果圖非常深，BFS可能會占用更多的內(nèi)存，因?yàn)樾枰鎯λ幸言L問節(jié)點(diǎn)的隊(duì)列。在這種情況下，DFS可能更有效。
.png)
