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

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

1. 创建一个栈，并将起始节点压入栈中。
2. 创建一个数组 visited，用于记录节点是否被访问过。将起始节点标记为已访问。
3. 当栈不为空时，执行以下操作：
- 弹出栈顶节点，访问该节点。
- 遍历该节点的所有未访问过的邻居节点，将其压入栈中，并标记为已访问。
4. 如果栈为空，遍历结束。

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

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

其中，graph 是邻接表表示的图，start 是起始节点。在这个实现中，我们使用了一个集合 visited 来记录访问过的节点，以避免重复访问。

相关问题

邻接表非递归深度优先遍历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;
}

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