用C语言分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历

邻接矩阵和邻接表是两种常见的图的存储方式。其中邻接矩阵是一个二维数组，用于表示图中各个节点之间的关系；邻接表则是由链表组成的数组，用于表示每个节点的邻居节点。

下面分别介绍如何用C语言实现邻接矩阵和邻接表的深度优先遍历和广度优先遍历。

1. 邻接矩阵的深度优先遍历

#define MAX_VERTEX_NUM 100 // 最大顶点数
int visited[MAX_VERTEX_NUM]; // 记录节点是否被访问过

void DFS_Matrix(int matrix[][MAX_VERTEX_NUM], int vertex, int n) {
    visited[vertex] = 1; // 标记节点已被访问
    printf("%d ", vertex); // 输出节点值
    for (int i = 0; i < n; i++) {
        if (matrix[vertex][i] && !visited[i]) { // 如果节点i与vertex相邻且未被访问
            DFS_Matrix(matrix, i, n); // 递归访问节点i
        }
    }
}

2. 邻接矩阵的广度优先遍历

#define MAX_VERTEX_NUM 100 // 最大顶点数
int visited[MAX_VERTEX_NUM]; // 记录节点是否被访问过

void BFS_Matrix(int matrix[][MAX_VERTEX_NUM], int vertex, int n) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义队列
    visited[vertex] = 1; // 标记节点已被访问
    printf("%d ", vertex); // 输出节点值
    queue[rear++] = vertex; // 将节点加入队列
    while (front < rear) { // 队列不为空时循环
        int v = queue[front++]; // 取出队首节点
        for (int i = 0; i < n; i++) {
            if (matrix[v][i] && !visited[i]) { // 如果节点i与v相邻且未被访问
                visited[i] = 1; // 标记节点已被访问
                printf("%d ", i); // 输出节点值
                queue[rear++] = i; // 将节点加入队列
            }
        }
    }
}

3. 邻接表的深度优先遍历

#define MAX_VERTEX_NUM 100 // 最大顶点数
int visited[MAX_VERTEX_NUM]; // 记录节点是否被访问过

void DFS_List(LinkedList list[], int vertex) {
    visited[vertex] = 1; // 标记节点已被访问
    printf("%d ", vertex); // 输出节点值
    Node *p = list[vertex].head; // 取出节点的邻居链表
    while (p) { // 遍历邻居链表
        if (!visited[p->data]) { // 如果邻居节点未被访问
            DFS_List(list, p->data); // 递归访问邻居节点
        }
        p = p->next;
    }
}

4. 邻接表的广度优先遍历

#define MAX_VERTEX_NUM 100 // 最大顶点数
int visited[MAX_VERTEX_NUM]; // 记录节点是否被访问过

void BFS_List(LinkedList list[], int vertex) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义队列
    visited[vertex] = 1; // 标记节点已被访问
    printf("%d ", vertex); // 输出节点值
    queue[rear++] = vertex; // 将节点加入队列
    while (front < rear) { // 队列不为空时循环
        int v = queue[front++]; // 取出队首节点
        Node *p = list[v].head; // 取出节点的邻居链表
        while (p) { // 遍历邻居链表
            if (!visited[p->data]) { // 如果邻居节点未被访问
                visited[p->data] = 1; // 标记节点已被访问
                printf("%d ", p->data); // 输出节点值
                queue[rear++] = p->data; // 将节点加入队列
            }
            p = p->next;
        }
    }
}