图的深度优先遍历和广度优先遍历c语言

图的深度优先遍历和广度优先遍历是图论中的两种常用算法，它们都可以用C语言实现。

深度优先遍历（DFS）是一种递归算法，它从图的某个顶点开始遍历，沿着一条路径走到底，直到不能再走为止，然后回溯到上一个节点，继续遍历其他路径，直到遍历完整个图。DFS可以用栈来实现，也可以用递归来实现。

广度优先遍历（BFS）是一种迭代算法，它从图的某个顶点开始遍历，先访问该顶点，然后访问它的所有邻接点，再依次访问它们的邻接点，直到遍历完整个图。BFS可以用队列来实现。

下面是DFS和BFS的C语言实现示例：

DFS：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

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

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

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

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

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

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

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

void enqueue(Queue *q, int x) {
    q->data[q->rear++] = x;
}

int dequeue(Queue *q) {
    return q->data[q->front++];
}

int isEmpty(Queue *q) {
    return q->front == q->rear;
}

typedef struct {
    int n;
    int adj[MAX_VERTICES][MAX_VERTICES];
} Graph;

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

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

void dfs(Graph *g, int v, int visited[]) {
    visited[v] = 1;
    printf("%d ", v);
    for (int i = ; i < g->n; i++) {
        if (g->adj[v][i] && !visited[i]) {
            dfs(g, i, visited);
        }
    }
}

void dfsStack(Graph *g, int v, int visited[]) {
    Stack s;
    initStack(&s);
    push(&s, v);
    visited[v] = 1;
    printf("%d ", v);
    while (!isEmpty(&s)) {
        int u = pop(&s);
        for (int i = ; i < g->n; i++) {
            if (g->adj[u][i] && !visited[i]) {
                push(&s, i);
                visited[i] = 1;
                printf("%d ", i);
            }
        }
    }
}

void bfs(Graph *g, int v, int visited[]) {
    Queue q;
    initQueue(&q);
    enqueue(&q, v);
    visited[v] = 1;
    printf("%d ", v);
    while (!isEmpty(&q)) {
        int u = dequeue(&q);
        for (int i = ; i < g->n; i++) {
            if (g->adj[u][i] && !visited[i]) {
                enqueue(&q, i);
                visited[i] = 1;
                printf("%d ", i);
            }
        }
    }
}

int main() {
    Graph g;
    int n, m, u, v;
    scanf("%d%d", &n, &m);
    initGraph(&g, n);
    for (int i = ; i < m; i++) {
        scanf("%d%d", &u, &v);
        addEdge(&g, u, v);
    }
    int visited[MAX_VERTICES] = {};
    dfs(&g, , visited);
    printf("\n");
    for (int i = ; i < n; i++) {
        visited[i] = ;
    }
    dfsStack(&g, , visited);
    printf("\n");
    for (int i = ; i < n; i++) {
        visited[i] = ;
    }
    bfs(&g, , visited);
    printf("\n");
    return ;
}

BFS：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

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

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

void enqueue(Queue *q, int x) {
    q->data[q->rear++] = x;
}

int dequeue(Queue *q) {
    return q->data[q->front++];
}

int isEmpty(Queue *q) {
    return q->front == q->rear;
}

typedef struct {
    int n;
    int adj[MAX_VERTICES][MAX_VERTICES];
} Graph;

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

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

void bfs(Graph *g, int v, int visited[]) {
    Queue q;
    initQueue(&q);
    enqueue(&q, v);
    visited[v] = 1;
    printf("%d ", v);
    while (!isEmpty(&q)) {
        int u = dequeue(&q);
        for (int i = ; i < g->n; i++) {
            if (g->adj[u][i] && !visited[i]) {
                enqueue(&q, i);
                visited[i] = 1;
                printf("%d ", i);
            }
        }
    }
}

int main() {
    Graph g;
    int n, m, u, v;
    scanf("%d%d", &n, &m);
    initGraph(&g, n);
    for (int i = ; i < m; i++) {
        scanf("%d%d", &u, &v);
        addEdge(&g, u, v);
    }
    int visited[MAX_VERTICES] = {};
    bfs(&g, , visited);
    printf("\n");
    return ;
}