基于c语言图的深度优先遍历非递归

在C语言中，基于非递归的方式实现深度优先遍历(DFS)通常需要借助栈数据结构，因为深度优先搜索的过程需要回溯。以下是使用栈实现图的深度优先遍历的一个示例：

#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // 图的最大节点数

typedef struct {
    int vertex; // 节点值
    struct Node* next; // 指向下一个邻接节点的指针
} Node;

typedef struct {
    Node* top;
    int size;
} Stack;

// 初始化栈
void init(Stack *s) {
    s->top = NULL;
    s->size = 0;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return (s->top == NULL);
}

// 入栈操作
void push(Stack *s, Node* node) {
    if (isEmpty(s)) {
        s->top = node;
    } else {
        node->next = s->top;
        s->top = node;
    }
    s->size++;
}

// 出栈操作
Node* pop(Stack *s) {
    if (isEmpty(s))
        return NULL;
    Node* temp = s->top;
    s->top = s->top->next;
    s->size--;
    return temp;
}

// 非递归深度优先遍历
void dfs(Node** graph, int v, Stack* stack) {
    printf("%d ", v); // 访问当前节点
    push(stack, (Node*)graph[v]); // 将未访问的相邻节点入栈

    while (!isEmpty(stack)) {
        v = pop(stack)->vertex; // 取出栈顶节点并访问其邻居
        for (Node* n = graph[v]; n != NULL; n = n->next) {
            if (n->vertex != v && !visited[n->vertex]) { // 如果邻居未访问过
                visited[n->vertex] = 1; // 标记已访问
                dfs(graph, n->vertex, stack); // 递归调用dfs
            }
        }
    }
}

int main() {
    int graph[MAX][MAX];
    int numVertices; // 图的节点数
    printf("Enter number of vertices: ");
    scanf("%d", &numVertices);

    // 填充图的邻接矩阵或其他表示法...
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            scanf("%d", &graph[i][j]);
        }
    }

    Stack stack;
    Node* visited = (Node*)malloc(numVertices * sizeof(int)); // 创建标记数组
    memset(visited, 0, numVertices * sizeof(int));

    Node** graphPtr = (Node**)malloc(sizeof(Node*) * numVertices);
    for (int i = 0; i < numVertices; ++i) {
        graphPtr[i] = NULL; // 初始化邻接表
        for (int j = 0; j < numVertices; ++j) {
            if (graph[i][j] != 0) {
                graphPtr[i] = (Node*)malloc(sizeof(Node));
                graphPtr[i]->vertex = j;
                graphPtr[i]->next = NULL;
            }
        }
    }

    dfs(graphPtr, 0, &stack); // 从第一个节点开始遍历
    free(graphPtr);
    free(visited);
    return 0;
}