图

深入理解“图”

1. 什么是图？

图是由一组顶点（Vertex / Node） 和连接这些顶点的边（Edge） 组成的。简单来说，图 G 可以表示为 G=(V,E)，其中 V 是顶点的集合，而 E 是边的集合。

形象比喻：

• 社交网络： 每个人是一个顶点，朋友关系是连接他们之间的边。
• 城市交通网络： 每个城市是一个顶点，连接城市的道路是边。
• 互联网： 每个网页是一个顶点，网页之间的链接是边。

2. 图的基本术语

理解这些术语是掌握图的关键：

• 顶点（Vertex / Node）： 图中的基本单元，代表了数据实体。例如，城市、人、网页。

• 边（Edge）： 连接两个顶点的线，表示它们之间的关系。例如，道路、朋友关系、网页链接。

• 邻接（Adjacent）： 如果两个顶点之间有一条边直接相连，则称它们是邻接的。

• 度（Degree）：

  对于无向图，一个顶点的度是与它相连的边的数量。

  • 对于有向图，分为入度（In-degree）和 出度（Out-degree）。
    • 入度： 指向该顶点的边的数量。
    • 出度： 从该顶点出发的边的数量。

• 路径（Path）： 从一个顶点到另一个顶点所经过的顶点序列（或边序列）。

• 连通（Connected）： 在无向图中，如果从顶点 A 到顶点 B 存在一条路径，则称 A 和 B 是连通的。

• 连通图（Connected Graph）： 如果图中任意两个顶点都是连通的，则称该图为连通图。

• 回路/环（Cycle）： 一条起始顶点和结束顶点相同的路径。

• 权重/权值（Weight）： 边上可以附加一个数值，表示某种成本、距离或强度。这种图称为带权图（Weighted Graph）。

• 子图（Sub-graph）： 一个图 G′=(V′,E′)，其中 V′⊆V 且 E′⊆E。

3. 图的分类

图可以根据其边的特性进行分类：

• 无向图（Undirected Graph）： 边没有方向。如果 A 到 B 有一条边，则意味着 B 到 A 也有相同的连接。例如，朋友关系。
• 有向图（Directed Graph / Digraph）： 边有方向。如果 A 到 B 有一条边，不代表 B 到 A 也有一条边。例如，单行道，或者 Twitter 上的关注关系（你关注别人，别人不一定关注你）。

---

4. 图在 C 语言中的表示方法

在 C 语言中，表示图通常有两种主要方式：邻接矩阵 和 邻接表。选择哪种方式取决于图的特性（顶点数、边数）和具体应用。

4.1 邻接矩阵（Adjacency Matrix）

邻接矩阵是一个 V×V 的二维数组（或矩阵），其中 V 是图中顶点的数量。

• 如果顶点 i 和顶点 j 之间有边相连，则 matrix[i][j] = 1 (或表示权重)。
• 如果无边相连，则 matrix[i][j] = 0 (或表示无穷大)。

特点：

• 优点：
  • 判断两顶点之间是否存在边非常快速（O(1)）。
  • 实现简单直观。
• 缺点：
  • 空间复杂度高：总是 O(V2)，即使图非常稀疏（边很少）。
  • 遍历一个顶点的所有邻居需要 O(V) 的时间。
• 适用场景： 顶点数量较少，或者图是稠密的（边很多）的情况。

C 语言示例（无向图，不带权）：

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

#define MAX_VERTICES 100 // 最大顶点数

// 邻接矩阵表示图
typedef struct GraphMatrix {
    int numVertices;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} GraphMatrix;

// 初始化图（邻接矩阵）
GraphMatrix* createGraphMatrix(int V) {
    GraphMatrix* graph = (GraphMatrix*)malloc(sizeof(GraphMatrix));
    if (graph == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    graph->numVertices = V;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            graph->adjMatrix[i][j] = 0; // 初始化为无边
        }
    }
    return graph;
}

// 添加边（无向图）
void addEdgeMatrix(GraphMatrix* graph, int src, int dest) {
    if (src >= 0 && src < graph->numVertices && dest >= 0 && dest < graph->numVertices) {
        graph->adjMatrix[src][dest] = 1;
        graph->adjMatrix[dest][src] = 1; // 无向图，对称
    } else {
        printf("无效的顶点索引。\n");
    }
}

// 打印邻接矩阵
void printGraphMatrix(GraphMatrix* graph) {
    printf("邻接矩阵：\n");
    for (int i = 0; i < graph->numVertices; i++) {
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d ", graph->adjMatrix[i][j]);
        }
        printf("\n");
    }
}

4.2 邻接表（Adjacency List）

邻接表是更常用的一种表示方法，特别适用于稀疏图。它是一个由链表（或动态数组） 组成的数组，数组的每个索引代表一个顶点，其对应的链表存储了所有与该顶点邻接的顶点。

特点：

• 优点：
  • 空间复杂度低：O(V+E)，更适合稀疏图。
  • 遍历一个顶点的所有邻居非常高效（O(degree)）。
• 缺点：
  • 判断两顶点之间是否存在边需要遍历链表（最坏 O(degree)）。
  • 实现相对复杂一点。
• 适用场景： 顶点数量很大，或者图是稀疏的（边很少）的情况。

C 语言示例（无向图，不带权）：

// 定义链表节点 (表示邻接顶点)
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表数组中的每个头节点
typedef struct AdjList {
    AdjListNode *head;
} AdjList;

// 邻接表表示图
typedef struct GraphList {
    int numVertices;
    AdjList* array; // 存储 AdjList 结构的数组
} GraphList;

// 创建邻接列表的新节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 初始化图（邻接表）
GraphList* createGraphList(int V) {
    GraphList* graph = (GraphList*)malloc(sizeof(GraphList));
    if (graph == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    graph->numVertices = V;

    graph->array = (AdjList*)malloc(V * sizeof(AdjList));
    if (graph->array == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL; // 初始化所有链表头为NULL
    }
    return graph;
}

// 添加边（无向图）
void addEdgeList(GraphList* graph, int src, int dest) {
    if (src >= 0 && src < graph->numVertices && dest >= 0 && dest < graph->numVertices) {
        // 添加 dest 到 src 的链表
        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;
    } else {
        printf("无效的顶点索引。\n");
    }
}

// 打印邻接表
void printGraphList(GraphList* graph) {
    printf("邻接表：\n");
    for (int v = 0; v < graph->numVertices; v++) {
        AdjListNode* current = graph->array[v].head;
        printf("顶点 %d 的邻居: ", v);
        while (current) {
            printf("-> %d ", current->dest);
            current = current->next;
        }
        printf("-> NULL\n");
    }
}

// 释放邻接表内存
void freeGraphList(GraphList* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        AdjListNode* current = graph->array[i].head;
        while (current != NULL) {
            AdjListNode* temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(graph->array);
    free(graph);
    printf("图的内存已释放。\n");
}

4.3 综合示例 main 函数

int main() {
    // 示例：邻接矩阵
    printf("--- 邻接矩阵示例 ---\n");
    GraphMatrix* g_matrix = createGraphMatrix(5); // 创建 5 个顶点的图
    addEdgeMatrix(g_matrix, 0, 1);
    addEdgeMatrix(g_matrix, 0, 4);
    addEdgeMatrix(g_matrix, 1, 2);
    addEdgeMatrix(g_matrix, 1, 3);
    addEdgeMatrix(g_matrix, 1, 4);
    addEdgeMatrix(g_matrix, 2, 3);
    addEdgeMatrix(g_matrix, 3, 4);
    printGraphMatrix(g_matrix);
    free(g_matrix); // 释放内存

    printf("\n--- 邻接表示例 ---\n");
    GraphList* g_list = createGraphList(5); // 创建 5 个顶点的图
    addEdgeList(g_list, 0, 1);
    addEdgeList(g_list, 0, 4);
    addEdgeList(g_list, 1, 2);
    addEdgeList(g_list, 1, 3);
    addEdgeList(g_list, 1, 4);
    addEdgeList(g_list, 2, 3);
    addEdgeList(g_list, 3, 4);
    printGraphList(g_list);
    freeGraphList(g_list); // 释放内存

    return 0;
}

---

5. 图的遍历

理解图的表示后，如何访问图中的所有顶点和边是另一个核心问题。图的遍历主要有两种方法：

• 广度优先搜索（BFS）： 从一个顶点开始，逐层访问其所有邻居，然后是邻居的邻居，以此类推。通常使用队列实现。
• 深度优先搜索（DFS）： 从一个顶点开始，尽可能深地探索其分支，直到无法继续深入，然后回溯。通常使用栈（或递归）实现。

这两种遍历方法是解决许多图算法的基础，例如查找最短路径、判断连通性等。