用C++写邻接表非递归深度优先遍历

邻接表非递归深度优先遍历需要使用栈来辅助实现，下面是C++代码实现：

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

const int MAXN = 100; // 最大顶点数

struct ArcNode {
    int adjvex;         // 该弧所指向的顶点的位置
    ArcNode* nextarc;   // 指向下一条弧的指针
};

struct VNode {
    int data;           // 顶点信息
    ArcNode* firstarc;  // 指向第一条依附该顶点的弧的指针
};

struct ALGraph {
    VNode adjlist[MAXN];    // 邻接表
    int n, e;               // 顶点数和边数
};

// 初始化邻接表
void init(ALGraph& G) {
    G.n = G.e = 0;
    for (int i = 0; i < MAXN; ++i) {
        G.adjlist[i].firstarc = nullptr;
    }
}

// 添加边
void add_edge(ALGraph& G, int u, int v) {
    auto p = new ArcNode;
    p->adjvex = v;
    p->nextarc = G.adjlist[u].firstarc;
    G.adjlist[u].firstarc = p;
}

// 非递归深度优先遍历
void DFS(ALGraph& G, int v) {
    bool visited[MAXN] = { false }; // 标记顶点是否被访问过
    stack<int> s;                   // 栈
    s.push(v);                      // 先将起始顶点入栈
    visited[v] = true;              // 标记起始顶点已被访问
    while (!s.empty()) {
        int u = s.top();            // 取出栈顶元素
        s.pop();
        cout << u << " ";           // 访问该顶点
        auto p = G.adjlist[u].firstarc;
        while (p != nullptr) {
            int w = p->adjvex;
            if (!visited[w]) {      // 如果该顶点未被访问过
                visited[w] = true;  // 标记该顶点已被访问
                s.push(w);          // 将该顶点入栈
            }
            p = p->nextarc;
        }
    }
}

int main() {
    ALGraph G;
    init(G);
    G.n = 6;
    add_edge(G, 0, 1);
    add_edge(G, 0, 2);
    add_edge(G, 1, 3);
    add_edge(G, 1, 4);
    add_edge(G, 2, 4);
    add_edge(G, 3, 5);
    add_edge(G, 4, 5);
    DFS(G, 0); // 从顶点0开始遍历
    return 0;
}

以上代码演示了如何使用邻接表来存储图，并实现非递归深度优先遍历。