用C++写深度优先搜索的算法

以下是用C语言实现深度优先搜索的算法。

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

#define MAX_SIZE 100 // 定义最大节点数

typedef struct {
    int data[MAX_SIZE]; // 存储节点数据
    int top; // 栈顶指针
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack is full\n");
        return;
    }
    s->data[++s->top] = value;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->data[s->top--];
}

typedef struct {
    int data[MAX_SIZE][MAX_SIZE]; // 存储节点之间的关系
    int n; // 节点数
} Graph;

void initGraph(Graph *g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->data[i][j] = 0;
        }
    }
}

void addEdge(Graph *g, int u, int v) {
    g->data[u][v] = 1;
    g->data[v][u] = 1;
}

void dfs(Graph *g, int start, bool *visited) {
    Stack s;
    initStack(&s);
    push(&s, start);
    visited[start] = true;
    printf("%d ", start);

    while (!isEmpty(&s)) {
        int u = pop(&s);
        for (int v = 0; v < g->n; v++) {
            if (g->data[u][v] == 1 && !visited[v]) {
                push(&s, v);
                visited[v] = true;
                printf("%d ", v);
            }
        }
    }
}

int main() {
    Graph g;
    initGraph(&g, 5);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 4);

    bool visited[MAX_SIZE] = {false};

    dfs(&g, 0, visited);

    return 0;
}

以上代码中，使用了栈来模拟深度优先搜索过程。首先将起始节点入栈，并标记为已访问。然后遍历与该节点相邻的节点，将未访问的节点入栈，并标记为已访问。继续出栈，重复上述过程，直到栈为空。同时，使用一个数组visited记录每个节点是否已访问过。这里假设节点数不超过100，可以根据实际情况调整。