邻接表非递归深度优先遍历

邻接表非递归深度优先遍历可以使用栈来实现。具体步骤如下：

1. 将起始节点入栈。
2. 如果栈非空，则取出栈顶元素，将其标记为已访问，并将其所有未访问的邻居节点入栈。
3. 重复步骤2，直到栈为空。

下面是一个示例代码实现：

def dfs_iterative(adj_list, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            for neighbor in adj_list[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

其中，`adj_list` 是邻接表，`start` 是起始节点。在代码中，我们使用了一个集合 `visited` 来记录已经访问过的节点，使用一个栈 `stack` 存储待访问的节点。在每次循环中，我们取出栈顶元素 `node`，如果它没有被访问过，则打印它，并将它所有未访问的邻居节点入栈。

需要注意的是，这种非递归实现的深度优先遍历并不能保证遍历顺序与递归实现相同，但它可以避免递归带来的函数调用栈溢出问题，因此在实际应用中具有一定的优势。

相关问题

邻接表非递归深度优先遍历c

邻接表的非递归深度优先遍历可以使用栈来实现。具体步骤如下：

1. 创建一个栈，并将起始节点入栈。
2. 创建一个visited数组，用于标记每个节点是否已经被访问过。将起始节点的visited值设为true。
3. 当栈不为空时，取出栈顶元素，并遍历其所有未被访问的邻居节点。对于每个邻居节点，若其visited值为false，则将其入栈并将visited值设为true。
4. 重复步骤3，直到栈为空。

具体实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct ArcNode {
    int adjvex;             // 邻接点下标
    struct ArcNode *next;   // 指向下一个邻接点
} ArcNode;

typedef struct VNode {
    int data;               // 顶点的数据
    ArcNode *first;         // 指向第一个邻接点
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;       // 邻接表
    int vexnum;             // 顶点数
    int arcnum;             // 边数
} ALGraph;

void init_graph(ALGraph *graph) {
    graph->vexnum = 0;
    graph->arcnum = 0;
}

void create_graph(ALGraph *graph) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &graph->vexnum, &graph->arcnum);

    // 初始化邻接表
    for (int i = 0; i < graph->vexnum; i++) {
        graph->vertices[i].data = i;
        graph->vertices[i].first = NULL;
    }

    // 建立边
    printf("请输入每条边的起点和终点：\n");
    for (int i = 0; i < graph->arcnum; i++) {
        int tail, head;
        scanf("%d %d", &tail, &head);

        ArcNode *arc_node = (ArcNode *) malloc(sizeof(ArcNode));
        arc_node->adjvex = head;
        arc_node->next = graph->vertices[tail].first;
        graph->vertices[tail].first = arc_node;

        // 无向图需加上下面这段代码
        arc_node = (ArcNode *) malloc(sizeof(ArcNode));
        arc_node->adjvex = tail;
        arc_node->next = graph->vertices[head].first;
        graph->vertices[head].first = arc_node;
    }
}

void print_graph(ALGraph *graph) {
    printf("邻接表：\n");
    for (int i = 0; i < graph->vexnum; i++) {
        printf("%d -> ", graph->vertices[i].data);
        ArcNode *arc_node = graph->vertices[i].first;
        while (arc_node) {
            printf("%d -> ", arc_node->adjvex);
            arc_node = arc_node->next;
        }
        printf("NULL\n");
    }
}

void DFS(ALGraph *graph, int start) {
    // 创建一个栈，用于非递归遍历
    int stack[MAX_VERTEX_NUM];
    int top = -1;

    // 创建一个visited数组，用于标记每个节点是否已经被访问过
    bool visited[MAX_VERTEX_NUM] = {false};

    // 将起始节点入栈，并将visited值设为true
    stack[++top] = start;
    visited[start] = true;

    while (top != -1) {
        int current = stack[top--];     // 取出栈顶元素
        printf("%d ", current);         // 访问该节点

        // 遍历所有未被访问的邻居节点
        ArcNode *arc_node = graph->vertices[current].first;
        while (arc_node) {
            if (!visited[arc_node->adjvex]) {
                stack[++top] = arc_node->adjvex;    // 将邻居节点入栈
                visited[arc_node->adjvex] = true;   // 将visited值设为true
            }
            arc_node = arc_node->next;
        }
    }
}

int main() {
    ALGraph graph;
    init_graph(&graph);
    create_graph(&graph);
    print_graph(&graph);

    printf("深度优先遍历结果：");
    DFS(&graph, 0);
    printf("\n");

    return 0;
}

用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;
}

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