非递归实现DFS的代码C++

非递归实现DFS可以使用栈来实现，具体代码如下：

void dfs(int start, vector<vector<int>>& graph) {
    stack<int> s;
    vector<bool> visited(graph.size(), false);
    s.push(start);
    visited[start] = true;
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        // 处理当前节点
        cout << cur << " ";
        for (int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i];
            if (!visited[next]) {
                s.push(next);
                visited[next] = true;
            }
        }
    }
}

其中，`start`表示起始节点，`graph`表示图的邻接表表示。首先创建一个栈和一个布尔型数组`visited`，用于记录每个节点是否被访问过。将起始节点压入栈中，并将其标记为已访问。然后进入循环，每次从栈中取出一个节点，处理该节点，并将其未访问的邻居节点压入栈中。直到栈为空为止。

相关问题

邻接表非递归遍历实现dfs

邻接表非递归实现DFS的代码如下所示：

void NoReDepthFirstSearch(AdjList g, int v0) {
    int visited[MAX]; // 创建visited数组，用于标记顶点是否已被访问
    for (int vi = 0; vi < g.vexnum; vi++) {
        visited[vi = 0; // 初始化visited数组
    }
    
    stack<int> S; // 创建一个栈用于存储待访问的顶点
    S.push(v0); // 将初始顶点v0入栈
    visited[v0 = 1; // 标记初始顶点v0已被访问
    
    while (!S.empty()) {
        int top = S.top(); // 获取栈顶元素
        S.pop(); // 栈顶元素出栈
        printf("%c ", g.vertexlist[top].data); // 访问栈顶顶点
        
        ArcNode* p = g.vertexlist[top].firstarc; // 获取与栈顶顶点相连的第一个邻接顶点
        
        while (p != NULL) {
            if (!visited[p->adjvex]) { // 如果邻接顶点未被访问过
                visited[p->adjvex = 1; // 标记邻接顶点已被访问
                S.push(p->adjvex); // 将邻接顶点入栈
            }
            p = p->nextarc; // 继续遍历下一个邻接顶点
        }
    }
}

这段代码使用了一个栈来实现非递归的DFS遍历。首先，创建一个visited数组用于标记顶点是否已被访问。然后，将初始顶点v0入栈，并将其标记为已访问。接下来，进入循环，每次从栈中取出一个顶点，访问它，并将与之相邻的未访问过的顶点入栈。直到栈为空，遍历结束。

希望对你有所帮助！

N皇后C++非递归实现

以下是 N 皇后问题的 C++ 非递归实现代码，使用了迭代加深搜索算法：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 20;

int n, ans;
int col[N], dia[N], udia[N];  // 分别表示列、正对角线、反对角线是否被占用

int dfs() {
    int path[N], top = -1;
    memset(col, 0, sizeof col);
    memset(dia, 0, sizeof dia);
    memset(udia, 0, sizeof udia);
    int cnt = 0;  // 记录当前摆放皇后的数量
    for (int i = 0; i < n; i++) {
        path[++top] = i;  // 将第一行皇后放在第 i 列
        col[i] = dia[i + top] = udia[n - i + top] = 1;  // 标记列、对角线
        cnt++;
    }
    while (top >= 0) {
        int u = path[top--];  // 取出栈顶元素
        cnt--;
        for (int i = u + 1; i < n; i++) {
            if (!col[i] && !dia[i - u + N] && !udia[n - i - u + N]) {
                path[++top] = i;
                col[i] = dia[i - u + N] = udia[n - i - u + N] = 1;
                cnt++;
            }
        }
        if (cnt == 0) ans++;  // 摆放了 n 个皇后，答案加 1
        while (top >= 0 && (top + n - u <= cnt)) {  // 回溯
            int j = path[top--];
            col[j] = dia[j - u + N] = udia[n - j - u + N] = 0;
            cnt--;
        }
    }
    return ans;
}

int main() {
    cin >> n;
    cout << dfs() << endl;
    return 0;
}

这里的核心思想是使用栈来模拟回溯过程，每次将当前行可以放置皇后的列号入栈，在回溯时依次弹出栈顶元素，并将其对应的列、对角线解除标记。