c++,分别基于邻接矩阵、邻接表利用堆栈实现非递归的深度优先遍历

首先，我们需要定义一个图的数据结构，包括节点数和边数，以及存储图信息的邻接矩阵和邻接表。下面以邻接矩阵为例：

const int MAXN = 1000;
bool G[MAXN][MAXN]; // 邻接矩阵
int n, m; // n 个节点，m 条边

接下来是非递归的深度优先遍历。我们使用堆栈（stack）来记录遍历的顺序，具体步骤如下：

1. 将起始节点压入堆栈中；
2. 取出堆栈顶部的节点，并标记为已访问；
3. 遍历该节点的所有邻居节点，如果邻居节点未被访问，则将其压入堆栈中；
4. 重复步骤 2 和 3，直到堆栈为空。

这里是基于邻接矩阵的非递归深度优先遍历的代码：

void dfsNonRecursive(int u) {
    stack<int> s;
    bool vis[MAXN] = {false};
    s.push(u);
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (!vis[cur]) {
            vis[cur] = true;
            cout << cur << " ";
        }
        for (int i = 0; i < n; i++) {
            if (G[cur][i] && !vis[i]) {
                s.push(i);
            }
        }
    }
}

接下来是基于邻接表的非递归深度优先遍历的代码：

struct Edge {
    int to, next;
};

const int MAXN = 1000;
Edge edges[MAXN];
int head[MAXN], cnt = 0; // 邻接表
int n, m; // n 个节点，m 条边

void addEdge(int u, int v) {
    edges[cnt].to = v;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}

void dfsNonRecursive(int u) {
    stack<int> s;
    bool vis[MAXN] = {false};
    s.push(u);
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (!vis[cur]) {
            vis[cur] = true;
            cout << cur << " ";
        }
        for (int i = head[cur]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            if (!vis[v]) {
                s.push(v);
            }
        }
    }
}

这里我们使用了一个链式前向星来存储每个节点的邻居节点。在遍历时，我们从头指针 `head[cur]` 开始遍历该节点的所有邻居节点。