无向图的深度优先遍历非递归

无向图的深度优先遍历非递归

使用非递归方式进行无向图的深度优先遍历可以通过使用栈来实现。以下是一个简单的算法步骤：

1. 创建一个空栈，并将起始节点压入栈中。

2. 创建一个集合（通常是哈希集合），用于记录已经访问过的节点，防止重复访问。

3. 进入循环，直到栈为空： a. 出栈一个节点，并标记为已访问。 b. 遍历该节点的所有未访问过的邻居节点，将其压入栈中。 c. 将当前节点标记为已访问，以防止重复访问。

以下是用C++编程实现无向图的非递归深度优先遍历的简单示例。在这个示例中，假设图的节点是整数，图的邻接表存储在unordered_map中：

#include <iostream>
#include <unordered_map>
#include <stack>
#include <unordered_set>

using namespace std;

void dfs_iterative(const unordered_map<int, vector<int>>& graph, int start_node) {
    stack<int> s;
    unordered_set<int> visited;

    s.push(start_node);

    while (!s.empty()) {
        int current_node = s.top();
        s.pop();

        if (visited.find(current_node) == visited.end()) {
            cout << current_node << " ";  // 访问节点
            visited.insert(current_node);

            for (int neighbor : graph.at(current_node)) {
                if (visited.find(neighbor) == visited.end()) {
                    s.push(neighbor);
                }
            }
        }
    }
}

int main() {
    // 构建一个简单的无向图的邻接表表示
    unordered_map<int, vector<int>> graph;
    graph[1] = {2, 3};
    graph[2] = {1, 4, 5};
    graph[3] = {1, 6};
    graph[4] = {2};
    graph[5] = {2, 6};
    graph[6] = {3, 5};

    int start_node = 1;  // 选择起始节点

    cout << "Depth First Traversal (Non-Recursive): ";
    dfs_iterative(graph, start_node);

    return 0;
}

下面是一个不使用 <unordered_map>, <unordered_set> 头文件的 C++ 示例，

#include <iostream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

void dfs_iterative(const vector<vector<int>>& graph, int start_node) {
    stack<int> s;
    set<int> visited;

    s.push(start_node);

    while (!s.empty()) {
        int current_node = s.top();
        s.pop();

        if (visited.find(current_node) == visited.end()) {
            cout << current_node << " ";  // 访问节点
            visited.insert(current_node);

            for (int neighbor : graph[current_node]) {
                if (visited.find(neighbor) == visited.end()) {
                    s.push(neighbor);
                }
            }
        }
    }
}

int main() {
    // 构建一个简单的无向图的邻接表表示
    vector<vector<int>> graph = {
        {2, 3},
        {1, 4, 5},
        {1, 6},
        {2},
        {2, 6},
        {3, 5}
    };

    int start_node = 1;  // 选择起始节点

    cout << "Depth First Traversal (Non-Recursive): ";
    dfs_iterative(graph, start_node);

    return 0;
}