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