深入理解C语言图挖掘算法（从零开始掌握图数据结构与基础遍历）

图的表示方法

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

• 邻接矩阵（Adjacency Matrix）：使用二维数组表示顶点之间的连接关系。
• 邻接表（Adjacency List）：使用链表或数组存储每个顶点的邻居。

对于初学者，我们先从简单的邻接矩阵入手。

使用C语言实现图的邻接矩阵

下面是一个用C语言定义图并初始化邻接矩阵的示例：

#include <stdio.h>#include <stdlib.h>#define MAX_VERTICES 100typedef struct {    int vertices;    int adjMatrix[MAX_VERTICES][MAX_VERTICES];} Graph;// 初始化图void initGraph(Graph* g, int numVertices) {    g->vertices = numVertices;    for (int i = 0; i < numVertices; i++) {        for (int j = 0; j < numVertices; j++) {            g->adjMatrix[i][j] = 0; // 0 表示无边        }    }}// 添加边void addEdge(Graph* g, int src, int dest) {    g->adjMatrix[src][dest] = 1;    // 如果是无向图，还需添加反向边    // g->adjMatrix[dest][src] = 1;}// 打印邻接矩阵void printGraph(Graph* g) {    for (int i = 0; i < g->vertices; i++) {        for (int j = 0; j < g->vertices; j++) {            printf("%d ", g->adjMatrix[i][j]);        }        printf("\n");    }}

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

图遍历是C语言图算法中最基础的操作之一。深度优先搜索（DFS）从一个起点出发，尽可能深地访问图中的节点。

// DFS辅助函数void DFSUtil(Graph* g, int vertex, int visited[]) {    visited[vertex] = 1;    printf("访问顶点: %d\n", vertex);    for (int i = 0; i < g->vertices; i++) {        if (g->adjMatrix[vertex][i] == 1 && !visited[i]) {            DFSUtil(g, i, visited);        }    }}// 深度优先搜索主函数void DFS(Graph* g, int startVertex) {    int* visited = (int*)calloc(g->vertices, sizeof(int));    DFSUtil(g, startVertex, visited);    free(visited);}

完整示例：构建图并执行DFS

下面是一个完整的程序，展示如何使用上述代码构建一个简单图并进行遍历：

int main() {    Graph g;    initGraph(&g, 5); // 创建5个顶点的图    addEdge(&g, 0, 1);    addEdge(&g, 0, 2);    addEdge(&g, 1, 3);    addEdge(&g, 2, 4);    printf("邻接矩阵:\n");    printGraph(&g);    printf("\n从顶点0开始的DFS遍历:\n");    DFS(&g, 0);    return 0;}

为什么学习C语言图挖掘算法？

掌握图数据结构和基本的图遍历算法是进入高级图挖掘（如社区发现、最短路径、PageRank等）的前提。C语言因其高效性和对内存的直接控制，常用于底层图计算引擎的开发。

即使你是编程小白，只要理解了本文的内容，你就已经迈出了图算法学习的第一步！后续可以尝试实现广度优先搜索（BFS）、Dijkstra最短路径等更复杂的C语言图挖掘算法。

小结

本文介绍了图的基本概念、邻接矩阵表示法，并用C语言实现了深度优先搜索（DFS）。这些是理解更复杂图遍历算法的基础。动手实践是掌握的关键，建议你复制代码到本地编译运行，观察输出结果。

继续探索，让C语言成为你图挖掘之旅的得力工具！