C语言图数据结构详解（从零开始掌握图的基础表示与操作）

图的两种常见表示方法

在C语言中，图通常用以下两种方式表示：

1. 邻接矩阵（Adjacency Matrix）：使用二维数组，适合稠密图。
2. 邻接表（Adjacency List）：使用链表数组，适合稀疏图，更节省空间。

本教程重点讲解邻接表表示法，因为它在实际应用中更为常见。

C语言实现图的邻接表表示

我们先定义两个结构体：一个表示图中的边（邻接节点），另一个表示整个图。

#include <stdio.h>#include <stdlib.h>// 表示邻接表中的一个节点struct AdjListNode {    int dest;                   // 目标顶点    struct AdjListNode* next; // 指向下一个邻接节点};// 表示图中的一个顶点及其邻接链表struct AdjList {    struct AdjListNode* head;};// 图结构struct Graph {    int V;                    // 顶点数量    struct AdjList* array;   // 邻接表数组};  

创建新节点和图

接下来，我们编写辅助函数来创建新节点和初始化图。

// 创建一个新的邻接节点struct AdjListNode* newAdjListNode(int dest) {    struct AdjListNode* newNode =        (struct AdjListNode*) malloc(sizeof(struct AdjListNode));    newNode->dest = dest;    newNode->next = NULL;    return newNode;}// 创建一个图（V 为顶点数）struct Graph* createGraph(int V) {    struct Graph* graph =        (struct Graph*) malloc(sizeof(struct Graph));    graph->V = V;    // 为邻接表数组分配内存    graph->array =        (struct AdjList*) malloc(V * sizeof(struct AdjList));    // 初始化每个邻接表的头指针为 NULL    for (int i = 0; i < V; ++i)        graph->array[i].head = NULL;    return graph;}  

添加边

对于无向图，每条边需要在两个顶点的邻接表中都添加记录。

// 向无向图中添加边void addEdge(struct Graph* graph, int src, int dest) {    // 添加 dest 到 src 的邻接表    struct AdjListNode* newNode = newAdjListNode(dest);    newNode->next = graph->array[src].head;    graph->array[src].head = newNode;    // 添加 src 到 dest 的邻接表（因为是无向图）    newNode = newAdjListNode(src);    newNode->next = graph->array[dest].head;    graph->array[dest].head = newNode;}  

图的遍历：深度优先搜索（DFS）

图的遍历是图算法的基础。常见的有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。这里我们实现一个简单的 DFS。

// DFS 辅助函数void DFSUtil(struct Graph* graph, int v, int visited[]) {    visited[v] = 1;    printf("%d ", v);    // 遍历所有邻接节点    struct AdjListNode* temp = graph->array[v].head;    while (temp) {        int adj = temp->dest;        if (!visited[adj])            DFSUtil(graph, adj, visited);        temp = temp->next;    }}// 从指定起点开始 DFSvoid DFS(struct Graph* graph, int start) {    int* visited = (int*) calloc(graph->V, sizeof(int));    DFSUtil(graph, start, visited);    free(visited);}  

完整示例：构建并遍历一个图

下面是一个完整的程序，演示如何使用上述代码构建一个包含5个顶点的无向图，并进行DFS遍历。

int main() {    // 创建一个包含5个顶点的图    struct Graph* graph = createGraph(5);    // 添加边    addEdge(graph, 0, 1);    addEdge(graph, 0, 4);    addEdge(graph, 1, 2);    addEdge(graph, 1, 3);    addEdge(graph, 1, 4);    addEdge(graph, 2, 3);    addEdge(graph, 3, 4);    printf("从顶点0开始的DFS遍历结果: ");    DFS(graph, 0);    printf("\n");    return 0;}  

运行结果：

从顶点0开始的DFS遍历结果: 0 4 3 2 1

总结

通过本教程，你已经掌握了C语言图数据结构的基础知识，包括：

• 图的基本概念（顶点、边、有向/无向）
• 使用邻接表在C语言中表示图
• 实现图的深度优先搜索（DFS）遍历

这些是学习更高级图算法（如最短路径、最小生成树等）的基石。希望你能动手实践，加深理解！

SEO关键词回顾：C语言图数据结构、图的邻接表表示、C语言图遍历算法、数据结构基础教程。