C语言图的创建与遍历：邻接矩阵、深度优先搜索 (DFS) 和广度优先搜索 (BFS)

本文介绍如何使用 C 语言通过邻接矩阵创建图，并使用深度优先搜索 (DFS) 和广度优先搜索 (BFS) 遍历图。代码示例演示了图的初始化、DFS 算法和使用循环队列实现 BFS 算法的步骤。

代码示例

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

#define MAX_VERTEX_NUM 100  // 图中最大顶点数

// 邻接矩阵表示的图结构体
typedef struct {
    int vexs[MAX_VERTEX_NUM];  // 顶点数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int vexnum, arcnum;  // 顶点数和边数
} Graph;

// 初始化图
void initGraph(Graph *G)
{
    int i, j;
    printf("请输入图的顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入图的顶点：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = 0;  // 初始化邻接矩阵
        }
    }
    printf("请输入图的边（顶点编号从0开始）：\n");
    int v1, v2;
    for (i = 0; i < G->arcnum; i++) {
        scanf("%d%d", &v1, &v2);
        G->arcs[v1][v2] = 1;  // 有向图
    }
}

// 深度优先遍历
void dfs(Graph *G, int v, int *visited)
{
    int i;
    visited[v] = 1;
    printf("%d ", G->vexs[v]);  // 访问顶点v
    for (i = 0; i < G->vexnum; i++) {
        if (G->arcs[v][i] && !visited[i]) {
            dfs(G, i, visited);  // 递归访问v的未访问过的邻接点
        }
    }
}

// 广度优先遍历
void bfs(Graph *G, int v, int *visited)
{
    int queue[MAX_VERTEX_NUM];  // 定义队列
    int front = 0, rear = 0;  // 队头和队尾指针
    queue[rear++] = v;  // 将v入队
    visited[v] = 1;
    printf("%d ", G->vexs[v]);  // 访问顶点v
    while (front < rear) {  // 队列不空
        int w = queue[front++];  // 出队
        int i;
        for (i = 0; i < G->vexnum; i++) {
            if (G->arcs[w][i] && !visited[i]) {
                queue[rear++] = i;  // 将i入队
                visited[i] = 1;
                printf("%d ", G->vexs[i]);  // 访问顶点i
            }
        }
    }
}

int main()
{
    Graph G;
    initGraph(&G);
    printf("深度优先遍历结果：");
    int visited[MAX_VERTEX_NUM] = {0};  // 初始化为未访问过
    int i;
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            dfs(&G, i, visited);  // 对每个未访问过的顶点进行深度优先遍历
        }
    }
    printf("\n广度优先遍历结果：");
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0;  // 重置visited数组
    }
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            bfs(&G, i, visited);  // 对每个未访问过的顶点进行广度优先遍历
        }
    }
    printf("\n");
    return 0;
}

解释

• 邻接矩阵: 使用一个二维数组 arcs 来表示图的连接关系。如果顶点 i 和 j 之间存在边，则 arcs[i][j] 为 1，否则为 0。
• 深度优先遍历 (DFS): 使用递归的方式，从一个顶点出发，依次访问其未访问过的邻接点，直到所有可达顶点都被访问。
• 广度优先遍历 (BFS): 使用队列来存储待访问的顶点。从一个顶点出发，先访问其所有直接邻接点，再访问这些邻接点的邻接点，以此类推，直到所有可达顶点都被访问。

注意

• 代码中使用的图是有向图。如果要修改为无向图，需要将两个方向的邻接矩阵元素都设为 1。
• 代码中的 MAX_VERTEX_NUM 定义了图中最大顶点数，可以根据需要修改。
• 代码中使用了 visited 数组来记录每个顶点是否被访问过。
• 在 BFS 算法中，使用了循环队列来实现队列功能。

希望这篇文章能够帮助您理解 C 语言中的图的创建和遍历。