C++数据结构深度优先搜索有向图非递归

深度优先搜索有向图的非递归实现可以使用栈来实现。具体步骤如下：

1. 创建一个栈，用于存储待遍历的节点。

2. 将起始节点压入栈中，并将其标记为已访问。

3. 当栈不为空时，执行以下操作：

a. 弹出栈顶节点，遍历其所有未访问的邻居节点，并将其标记为已访问，然后将其依次压入栈中。

b. 如果该节点没有未访问的邻居节点，则继续弹出栈顶节点，直到找到有未访问邻居节点的节点或者栈为空。

4. 重复步骤3，直到栈为空。

下面是一个示例代码：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// 有向图的邻接表表示
vector<int> adjList[100];

// 深度优先搜索非递归实现
void dfs(int start) {
    stack<int> s;
    bool visited[100] = { false }; // 标记节点是否已访问
    s.push(start);
    visited[start] = true;
    while (!s.empty()) {
        int curr = s.top();
        s.pop();
        cout << curr << " ";
        for (int neighbor : adjList[curr]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                s.push(neighbor);
            }
        }
    }
}

int main() {
    // 初始化邻接表
    adjList[1].push_back(2);
    adjList[1].push_back(3);
    adjList[2].push_back(4);
    adjList[2].push_back(5);
    adjList[3].push_back(5);
    adjList[4].push_back(6);
    adjList[5].push_back(6);
    // 从节点1开始进行深度优先搜索
    dfs(1);
    return 0;
}