如何使用c++ stack類實(shí)現(xiàn)深度優(yōu)先搜索

c++
小樊
81
2024-09-25 08:41:16

在C++中，使用stack類實(shí)現(xiàn)深度優(yōu)先搜索（DFS）主要涉及到兩個(gè)方面：遞歸和棧的使用。這里我們假設(shè)你已經(jīng)熟悉了深度優(yōu)先搜索的基本概念和遞歸的實(shí)現(xiàn)方式。下面是一個(gè)使用C++ stack類實(shí)現(xiàn)深度優(yōu)先搜索的示例代碼：

  1. 首先，你需要包含必要的頭文件：
#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>
  1. 然后，定義一個(gè)圖的數(shù)據(jù)結(jié)構(gòu)，這里我們使用鄰接表表示圖：
using namespace std;

vector<unordered_map<int, int>> graph; // 鄰接表表示的圖
  1. 接下來(lái)，定義一個(gè)遞歸函數(shù)來(lái)實(shí)現(xiàn)深度優(yōu)先搜索：
void dfs(int node, unordered_map<int, bool>& visited) {
    visited[node] = true; // 標(biāo)記節(jié)點(diǎn)為已訪問(wèn)
    cout << node << " "; // 輸出當(dāng)前節(jié)點(diǎn)

    for (auto& neighbor : graph[node]) { // 遍歷當(dāng)前節(jié)點(diǎn)的所有鄰居
        int nextNode = neighbor.first;
        if (!visited[nextNode]) { // 如果鄰居節(jié)點(diǎn)未訪問(wèn)
            dfs(nextNode, visited); // 遞歸訪問(wèn)鄰居節(jié)點(diǎn)
        }
    }
}
  1. 最后，在主函數(shù)中初始化圖并調(diào)用dfs函數(shù)進(jìn)行深度優(yōu)先搜索：
int main() {
    // 初始化圖，這里只是一個(gè)示例，你需要根據(jù)你的實(shí)際情況來(lái)構(gòu)建圖
    graph = {
        {{1, 2}, {3}}, // 節(jié)點(diǎn)0的鄰居是1和2
        {{0}, {2}, {3}}, // 節(jié)點(diǎn)1的鄰居是0、2和3
        {{0}, {1}, {3}}, // 節(jié)點(diǎn)2的鄰居是0、1和3
        {{1}, {2}}, // 節(jié)點(diǎn)3的鄰居是1和2
    };

    unordered_map<int, bool> visited; // 記錄節(jié)點(diǎn)是否已訪問(wèn)
    for (int i = 0; i < graph.size(); ++i) {
        if (!visited[i]) { // 如果節(jié)點(diǎn)i未訪問(wèn)
            dfs(i, visited); // 遞歸訪問(wèn)節(jié)點(diǎn)i及其所有未訪問(wèn)的鄰居節(jié)點(diǎn)
        }
    }

    return 0;
}

注意：在這個(gè)示例中，我們使用了鄰接表表示的圖，并使用unordered_map來(lái)記錄節(jié)點(diǎn)是否已訪問(wèn)。你可以根據(jù)你的實(shí)際情況來(lái)調(diào)整數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)方式。另外，這個(gè)示例中的DFS實(shí)現(xiàn)是基于遞歸的，你也可以使用非遞歸的方式來(lái)實(shí)現(xiàn)DFS，例如使用stack類來(lái)模擬遞歸調(diào)用棧。

0 踩