非递归实现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非递归遍历实现 c++完整代码

在C++中，深度优先搜索（DFS）是非递归的一种常用图遍历算法。这里是一个使用邻接表（Adjacency List）实现的简单DFS遍历示例：

#include <iostream>
#include <vector>

// 定义图的节点
struct Node {
    int value;
    std::vector<Node*> neighbors; // 邻居列表
};

// 深度优先遍历辅助函数
void dfs(Node* node, bool visited[], int start) {
    visited[node->value] = true;
    std::cout << node->value << " ";

    for (Node* neighbor : node->neighbors) {
        if (!visited[neighbor->value]) {
            dfs(neighbor, visited, start);
        }
    }
}

// 主函数，用于创建图并调用DFS
int main() {
    // 创建图的数据结构
    Node nodes[] = {
        {1, {&nodes[2], &nodes[3]}},
        {2, {&nodes[1], &nodes[4]}},
        {3, {&nodes[1]}},
        {4, {&nodes[2], &nodes[5]}},
        {5, {&nodes[4]}}
    };

    // 初始化已访问标志数组
    bool visited[6] = {false};

    // 开始从节点1进行DFS
    dfs(nodes + start, visited, start);

    std::cout << "\n";

    return 0;
}

在这个例子中，我们首先定义了一个`Node`结构，表示图中的每个节点。然后定义了`dfs`函数，这个函数接受当前节点指针、已访问标记数组以及开始遍历的位置。在`dfs`函数内部，我们会标记当前节点为已访问，并打印其值；接着遍历邻居，对未访问过的邻居继续进行DFS。

在`main`函数中，我们创建了一个简单的图，并初始化了一个布尔数组表示哪些节点已被访问过。最后，我们从给定的起始节点开始执行DFS。

请注意，这只是一个基本的示例，实际应用中可能需要根据具体的图结构进行调整。如果你想要提供一个特定的图结构或需求，请告知我如何修改。

邻接表非递归遍历实现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入栈，并将其标记为已访问。接下来，进入循环，每次从栈中取出一个顶点，访问它，并将与之相邻的未访问过的顶点入栈。直到栈为空，遍历结束。

希望对你有所帮助！