C 语言图基础

介绍

图（Graph）是一种非常重要的数据结构，用于表示对象之间的关系。图由**顶点（Vertex）和边（Edge）**组成，顶点表示对象，边表示对象之间的关系。图广泛应用于社交网络、路径规划、网络拓扑等领域。

在C语言中，图可以通过多种方式表示，最常见的是邻接矩阵和邻接表。本文将逐步讲解图的基本概念、表示方法以及实际应用。

图的基本概念

顶点和边

顶点（Vertex）：图中的节点，表示一个对象。
边（Edge）：连接两个顶点的线，表示两个对象之间的关系。边可以是有向的（Directed）或无向的（Undirected）。

图的类型

无向图（Undirected Graph）：边没有方向，表示双向关系。
有向图（Directed Graph）：边有方向，表示单向关系。
加权图（Weighted Graph）：边带有权重，表示关系的强度或成本。

图的表示方法

1. 邻接矩阵

邻接矩阵是一个二维数组，用于表示图中顶点之间的连接关系。如果图有 n 个顶点，则邻接矩阵是一个 n x n 的矩阵。

如果顶点 i 和顶点 j 之间有边，则 matrix[i][j] = 1（对于无向图，matrix[j][i] = 1）。
如果顶点 i 和顶点 j 之间没有边，则 matrix[i][j] = 0。

c
#include <stdio.h>

#define V 4 // 顶点数量

// 初始化邻接矩阵
void initGraph(int graph[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            graph[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(int graph[V][V], int src, int dest) {
    graph[src][dest] = 1;
    graph[dest][src] = 1; // 无向图需要双向设置
}

// 打印邻接矩阵
void printGraph(int graph[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V];
    initGraph(graph);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);
    return 0;
}

输出：

提示

邻接矩阵适合表示稠密图（边数接近顶点数的平方），但对于稀疏图（边数远少于顶点数的平方），会浪费大量空间。

2. 邻接表

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

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

// 邻接表节点
struct Node {
    int dest;
    struct Node* next;
};

// 图的邻接表表示
struct Graph {
    int V;
    struct Node** array;
};

// 创建新节点
struct Node* createNode(int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct Node**)malloc(V * sizeof(struct Node*));

    for (int i = 0; i < V; i++) {
        graph->array[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->array[src];
    graph->array[src] = newNode;

    // 无向图需要双向设置
    newNode = createNode(src);
    newNode->next = graph->array[dest];
    graph->array[dest] = newNode;
}

// 打印邻接表
void printGraph(struct Graph* graph) {
    for (int i = 0; i < graph->V; i++) {
        struct Node* temp = graph->array[i];
        printf("顶点 %d 的邻居: ", i);
        while (temp) {
            printf("%d -> ", temp->dest);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int V = 4;
    struct Graph* graph = createGraph(V);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);
    return 0;
}

输出：

顶点 0 的邻居: 2 -> 1 -> NULL
顶点 1 的邻居: 2 -> 0 -> NULL
顶点 2 的邻居: 3 -> 1 -> 0 -> NULL
顶点 3 的邻居: 2 -> NULL

备注

邻接表适合表示稀疏图，因为它只存储实际存在的边，节省空间。

实际应用场景

1. 社交网络

在社交网络中，用户是顶点，好友关系是边。通过图可以分析用户之间的关系、推荐好友或发现社区。

2. 路径规划

在地图应用中，地点是顶点，道路是边。通过图算法（如Dijkstra算法）可以找到两点之间的最短路径。

3. 网络拓扑

在计算机网络中，设备是顶点，连接是边。通过图可以分析网络的连通性和性能。

总结

图是一种强大的数据结构，用于表示对象之间的关系。本文介绍了图的基本概念、邻接矩阵和邻接表的表示方法，并展示了实际应用场景。掌握图的基础知识是学习更复杂算法（如深度优先搜索、广度优先搜索、最短路径算法等）的关键。

附加资源与练习

练习：尝试实现一个有向图的邻接表表示，并添加权重功能。
深入学习：研究图的遍历算法（DFS和BFS）以及最短路径算法（Dijkstra和Floyd-Warshall）。
参考书籍：《算法导论》中的图论章节。

警告

在学习图的过程中，务必动手实践代码，理解每种表示方法的优缺点。

介绍​

图的基本概念​

顶点和边​

图的类型​

图的表示方法​

1. 邻接矩阵​

2. 邻接表​

实际应用场景​

1. 社交网络​

2. 路径规划​

3. 网络拓扑​

总结​

附加资源与练习​

介绍