dfs和bfs算法实现c++

以下是DFS和BFS算法的C语言实现。

DFS算法：

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

#define MAX_VERTICES 100

bool visited[MAX_VERTICES];

typedef struct {
    int vertices[MAX_VERTICES];
    int top;
} Stack;

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

void push(Stack *s, int vertex) {
    s->vertices[++s->top] = vertex;
}

int pop(Stack *s) {
    return s->vertices[s->top--];
}

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

typedef struct {
    int vertices[MAX_VERTICES];
    int front, rear;
} Queue;

void init(Queue *q) {
    q->front = q->rear = -1;
}

void enqueue(Queue *q, int vertex) {
    if (q->rear == MAX_VERTICES - 1) {
        printf("Queue overflow!\n");
        return;
    }
    if (q->front == -1) {
        q->front = q->rear = 0;
    } else {
        q->rear++;
    }
    q->vertices[q->rear] = vertex;
}

int dequeue(Queue *q) {
    if (q->front == -1) {
        printf("Queue underflow!\n");
        return -1;
    }
    int vertex = q->vertices[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front++;
    }
    return vertex;
}

bool is_queue_empty(Queue *q) {
    return q->front == -1;
}

typedef struct {
    int vertices[MAX_VERTICES];
    int adj_matrix[MAX_VERTICES][MAX_VERTICES];
    int num_vertices;
} Graph;

void init_graph(Graph *g, int num_vertices) {
    g->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = false;
        for (int j = 0; j < num_vertices; j++) {
            g->adj_matrix[i][j] = 0;
        }
    }
}

void add_edge(Graph *g, int start, int end) {
    g->adj_matrix[start][end] = 1;
    g->adj_matrix[end][start] = 1;
}

void dfs(Graph *g, int start_vertex) {
    Stack s;
    init(&s);
    push(&s, start_vertex);
    visited[start_vertex] = true;
    while (!is_empty(&s)) {
        int current_vertex = pop(&s);
        printf("%d ", current_vertex);
        for (int i = 0; i < g->num_vertices; i++) {
            if (g->adj_matrix[current_vertex][i] == 1 && !visited[i]) {
                push(&s, i);
                visited[i] = true;
            }
        }
    }
}

void bfs(Graph *g, int start_vertex) {
    Queue q;
    init(&q);
    enqueue(&q, start_vertex);
    visited[start_vertex] = true;
    while (!is_queue_empty(&q)) {
        int current_vertex = dequeue(&q);
        printf("%d ", current_vertex);
        for (int i = 0; i < g->num_vertices; i++) {
            if (g->adj_matrix[current_vertex][i] == 1 && !visited[i]) {
                enqueue(&q, i);
                visited[i] = true;
            }
        }
    }
}

int main() {
    Graph g;
    init_graph(&g, 5);
    add_edge(&g, 0, 1);
    add_edge(&g, 0, 2);
    add_edge(&g, 1, 2);
    add_edge(&g, 2, 3);
    add_edge(&g, 3, 4);
    printf("DFS traversal: ");
    dfs(&g, 0);
    for (int i = 0; i < g.num_vertices; i++) {
        visited[i] = false;
    }
    printf("\nBFS traversal: ");
    bfs(&g, 0);
    return 0;
}

BFS算法：