C语言图数据结构：邻接矩阵、深度优先遍历、广度优先遍历

本示例代码展示了使用 C 语言通过邻接矩阵创建图数据结构，并演示了深度优先遍历 (DFS) 和广度优先遍历 (BFS) 算法。代码还包含队列的使用，以实现 BFS 算法。

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

#define MAX_VERTEX_NUM 20 // 最大顶点数

typedef int VertexType; // 顶点类型

typedef struct {
    VertexType vertex[MAX_VERTEX_NUM]; // 存储顶点信息
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边信息
    int vertex_num; // 顶点数
    int edge_num; // 边数
} Graph;

int visited[MAX_VERTEX_NUM] = {0}; // 标记是否已访问过

// 初始化图
void init_graph(Graph *G) {
    printf("请输入图的顶点数和边数：");
    scanf("%d%d", &G->vertex_num, &G->edge_num);
    printf("请输入图的顶点信息：");
    for (int i = 0; i < G->vertex_num; i++) {
        scanf("%d", &G->vertex[i]);
    }
    // 初始化边矩阵
    for (int i = 0; i < G->vertex_num; i++) {
        for (int j = 0; j < G->vertex_num; j++) {
            G->edge[i][j] = 0;
        }
    }
    // 输入边信息
    printf("请输入图的边信息（格式为：起点 终点）：\n");
    for (int k = 0; k < G->edge_num; k++) {
        int i, j;
        scanf("%d%d", &i, &j);
        G->edge[i][j] = 1;
        G->edge[j][i] = 1; // 无向图，需要同时设置两个方向的边
    }
}

// 深度优先遍历
void DFS(Graph *G, int v) {
    visited[v] = 1; // 标记已访问
    printf("%d ", G->vertex[v]); // 输出顶点信息
    for (int i = 0; i < G->vertex_num; i++) {
        if (G->edge[v][i] && !visited[i]) { // 如果有连通且未被访问
            DFS(G, i); // 递归访问
        }
    }
}

// 广度优先遍历
void BFS(Graph *G, int v) {
    int queue[MAX_VERTEX_NUM]; // 定义队列，存储待访问顶点
    int front = 0, rear = 0; // 定义队列的头尾指针
    visited[v] = 1; // 标记已访问
    printf("%d ", G->vertex[v]); // 输出顶点信息
    queue[rear++] = v; // 将顶点入队
    while (front != rear) { // 当队列非空时循环
        int w = queue[front++]; // 取出队首元素并出队
        for (int i = 0; i < G->vertex_num; i++) {
            if (G->edge[w][i] && !visited[i]) { // 如果有连通且未被访问
                visited[i] = 1; // 标记已访问
                printf("%d ", G->vertex[i]); // 输出顶点信息
                queue[rear++] = i; // 将顶点入队
            }
        }
    }
}

int main() {
    Graph G;
    init_graph(&G);
    printf("深度优先遍历结果：");
    for (int i = 0; i < G.vertex_num; i++) {
        if (!visited[i]) { // 如果顶点未被访问
            DFS(&G, i); // 从该顶点开始深度优先遍历
        }
    }
    printf("\n");
    for (int i = 0; i < G.vertex_num; i++) {
        visited[i] = 0; // 重置访问标记
    }
    printf("广度优先遍历结果：");
    for (int i = 0; i < G.vertex_num; i++) {
        if (!visited[i]) { // 如果顶点未被访问
            BFS(&G, i); // 从该顶点开始广度优先遍历
        }
    }
    printf("\n");
    return 0;
}

在上述代码中，我们使用了一个 visited 数组来标记每个顶点是否已被访问过。在深度优先遍历中，我们从未被访问过的顶点开始，递归访问与之相邻的未被访问过的顶点，直到所有顶点都被访问过为止。在广度优先遍历中，我们使用一个队列来存储待访问顶点，从未被访问过的顶点开始，将其入队并标记为已访问，然后循环从队列中取出队首元素并访问其所有未被访问过的相邻顶点，将其入队并标记为已访问，直到队列为空为止。