C++中實(shí)現(xiàn)圖的深度優(yōu)先遍歷需用鄰接表存儲(chǔ)圖，通過(guò)遞歸或棧進(jìn)行節(jié)點(diǎn)訪問(wèn)并標(biāo)記已訪問(wèn)節(jié)點(diǎn)避免重復(fù)。1. 使用vector<vector<int>>表示鄰接表；2. 遞歸實(shí)現(xiàn)DFS，從起始節(jié)點(diǎn)出發(fā)，訪問(wèn)未訪問(wèn)的鄰接點(diǎn)并遞歸調(diào)用；3. 非遞歸實(shí)現(xiàn)使用stack模擬調(diào)用棧，壓入起始節(jié)點(diǎn)后循環(huán)處理；4. 完整示例展示了從節(jié)點(diǎn)0開(kāi)始的遍歷過(guò)程，輸出可能為0 1 3 2 4。若圖非連通，需對(duì)每個(gè)未訪問(wèn)節(jié)點(diǎn)調(diào)用DFS。

在C++中實(shí)現(xiàn)圖的深度優(yōu)先遍歷（DFS），核心是使用遞歸或棧來(lái)訪問(wèn)每個(gè)頂點(diǎn)，并避免重復(fù)訪問(wèn)。通常結(jié)合鄰接表存儲(chǔ)圖結(jié)構(gòu)，再通過(guò)標(biāo)記數(shù)組記錄已訪問(wèn)節(jié)點(diǎn)。

1. 圖的表示：鄰接表

假設(shè)圖有n個(gè)節(jié)點(diǎn)，編號(hào)從0到n-1，可以這樣初始化：

2. DFS遞歸實(shí)現(xiàn)

需要一個(gè)布爾數(shù)組visited[]來(lái)記錄訪問(wèn)狀態(tài)：

調(diào)用時(shí)指定起始節(jié)點(diǎn)，比如從節(jié)點(diǎn)0開(kāi)始：

立即學(xué)習(xí)“C++免費(fèi)學(xué)習(xí)筆記（深入）”；

3. 使用棧的非遞歸實(shí)現(xiàn)

步驟如下：

UP簡(jiǎn)歷

基于AI技術(shù)的免費(fèi)在線簡(jiǎn)歷制作工具

72

查看詳情

• 創(chuàng)建棧，壓入起始節(jié)點(diǎn)
• 標(biāo)記該節(jié)點(diǎn)為已訪問(wèn)
• 循環(huán)直到?？眨簭棾鲆粋€(gè)節(jié)點(diǎn)并訪問(wèn)，將其所有未訪問(wèn)鄰接點(diǎn)壓棧并標(biāo)記

void dfs_iterative(int start) {
????stack<int> st;
????st.push(start);
????vector<bool> visited(n, false);
????visited[start] = true;

????while (!st.empty()) {
????????int u = st.top();
????????st.pop();
????????cout << u << " ";

????????for (int v : graph[u]) {
????????????if (!visited[v]) {
????????????????st.push(v);
????????????????visited[v] = true;
????????????}
????????}
????}
}

4. 完整示例代碼

include <iostream>

include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int u) {
????visited[u] = true;
????cout << u << " ";
????for (int v : graph[u]) {
????????if (!visited[v])
????????????dfs(v);
????}
}

int main() {
????int n = 5; // 節(jié)點(diǎn)數(shù)
????graph.resize(n);
????visited.assign(n, false);

????// 添加邊
????graph[0].push_back(1);
????graph[1].push_back(0);
????graph[0].push_back(2);
????graph[2].push_back(0);
????graph[1].push_back(3);
????graph[3].push_back(1);
????graph[2].push_back(4);
????graph[4].push_back(2);

????cout << "DFS traversal: ";
????dfs(0);
????return 0;
}

輸出結(jié)果為：0 1 3 2 4（具體順序可能因鄰接點(diǎn)插入順序而異）

基本上就這些。根據(jù)實(shí)際需求選擇遞歸或迭代方式，注意處理連通性問(wèn)題——如果是非連通圖，需對(duì)每個(gè)未訪問(wèn)節(jié)點(diǎn)都調(diào)用一次DFS。

以上就是c++++中如何實(shí)現(xiàn)圖的深度優(yōu)先遍歷_c++圖DFS遍歷方法的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注php中文網(wǎng)其它相關(guān)文章！