C语言图算法详解（从零开始掌握图的表示与遍历）

图的表示方法

在C语言中，图主要有两种表示方式：

1. 邻接矩阵（Adjacency Matrix）

使用二维数组 graph[V][V] 表示，其中 V 是顶点数量。如果顶点 i 和 j 之间有边，则 graph[i][j] = 1，否则为 0。

#define V 5  // 顶点数int graph[V][V] = {    {0, 1, 1, 0, 0},    {1, 0, 1, 1, 0},    {1, 1, 0, 1, 1},    {0, 1, 1, 0, 1},    {0, 0, 1, 1, 0}};

优点：查询两点是否有边非常快（O(1)）。
缺点：空间浪费大，尤其当图稀疏时（边很少）。

2. 邻接表（Adjacency List）

使用链表或动态数组存储每个顶点的邻居。更节省空间，适合稀疏图。

#include <stdio.h>#include <stdlib.h>// 链表节点struct Node {    int dest;    struct Node* next;};// 图结构struct Graph {    int numVertices;    struct Node** adjLists;};// 创建新节点struct Node* createNode(int dest) {    struct Node* newNode = malloc(sizeof(struct Node));    newNode->dest = dest;    newNode->next = NULL;    return newNode;}

深度优先搜索（DFS）

深度优先搜索（DFS）是一种沿着一条路径尽可能深入地访问顶点，直到无法继续为止，然后回溯的遍历方法。它通常使用递归或栈实现。

void DFS(int vertex, int visited[], int graph[][V]) {    visited[vertex] = 1;    printf("Visited %d\n", vertex);    for (int i = 0; i < V; i++) {        if (graph[vertex][i] == 1 && !visited[i]) {            DFS(i, visited, graph);        }    }}// 调用示例int visited[V] = {0};DFS(0, visited, graph);

广度优先搜索（BFS）

广度优先搜索（BFS）则是一层一层地访问顶点，先访问离起点最近的所有顶点。它使用队列实现。

#include <stdbool.h>void BFS(int start, int graph[][V]) {    bool visited[V] = {false};    int queue[V];    int front = 0, rear = 0;    visited[start] = true;    queue[rear++] = start;    while (front != rear) {        int current = queue[front++];        printf("Visited %d\n", current);        for (int i = 0; i < V; i++) {            if (graph[current][i] == 1 && !visited[i]) {                visited[i] = true;                queue[rear++] = i;            }        }    }}

总结

通过本教程，你已经掌握了：
✅ 图的基本概念
✅ 两种常见的图的表示方法（邻接矩阵 vs 邻接表）
✅ 如何用C语言实现深度优先搜索（DFS）
✅ 如何用C语言实现广度优先搜索（BFS）

这些是学习更高级图算法（如Dijkstra最短路径、拓扑排序、最小生成树等）的基础。建议你动手编写并调试上述代码，加深理解。

记住，掌握C语言图算法的关键在于多练习、多画图。祝你在算法学习之路上越走越远！