CSP-J 算法基础 图论

前言

图论是计算机科学与离散数学中非常重要的一个分支，广泛应用于网络流、最短路径、图的连通性等众多领域。在实际问题中，许多关系可以抽象成图的形式，比如交通路线、社交网络、通信网络等。图论的核心概念包括顶点和边，通过这些基本单元可以构建不同类型的图模型。

对于 CSP-J 竞赛或算法基础学习，掌握图的基本算法是非常重要的。我们经常会遇到与图相关的问题，例如最短路径问题、图的遍历（深度优先搜索与广度优先搜索）、连通分量的求解、最小生成树、最大流问题等。这些问题的高效解法依赖于对图的深入理解以及合理的数据结构设计（如邻接矩阵和邻接表）。

在本文中，我们将探讨图论的基础概念与算法，简要了解如何在实际竞赛题目中应用这些算法来解决问题。

图的简介

“图”这种数据结构，是计算机科学中的一种非常重要的数据结构，广泛应用于社交网络、网络路由、地图导航、推荐系统等领域。我们可以深入探讨图的核心概念和其重要的组成部分。

1. 图的定义

图是一种由**顶点（vertices）和边（edges）**组成的集合，用来描述实体及其相互关系。通常用 $$G=(V,E)$$ 表示图，其中：

• ( V ) 是顶点的集合，表示图中的每一个节点。
• ( E ) 是边的集合，表示图中顶点之间的连接关系。

它是一种多对多的一种关系

2. 图的类型

图可以根据其边的性质分为以下几种常见类型：

• 有向图（Directed Graph）：边具有方向性，每条边 ( (u, v) ) 表示从顶点 ( u ) 到顶点 ( v ) 的单向连接。
• 无向图（Undirected Graph）：边没有方向性，边 ( (u, v) ) 表示顶点 ( u ) 和顶点 ( v ) 之间的双向连接。
• 加权图（Weighted Graph）：边附带权重，每条边都有一个数值，表示两个顶点之间的距离、成本等属性。
• 非加权图（Unweighted Graph）：边不附带任何权重，只有连通性信息。

3. 图的表示方法

图的数据结构可以用不同的方式表示，常见的有两种：

a. 邻接矩阵（Adjacency Matrix）

邻接矩阵是一个 $$n\times n$$ 的矩阵，其中 ( n ) 是图的顶点数。如果顶点 ( i ) 和顶点 ( j ) 之间有边连接，矩阵中的对应元素 ( A[i][j] ) 赋值为 1（对于无权图）或边的权重（对于加权图）；如果没有边，则赋值为 0。例如：

   0  1  2  3
0 [0, 1, 0, 1]
1 [1, 0, 1, 1]
2 [0, 1, 0, 0]
3 [1, 1, 0, 0]

• 优点：访问某条边的时间复杂度为 ( O(1) )。
• 缺点：占用空间较大，特别是对稀疏图（即边较少的图）。

b. 邻接表（Adjacency List）

邻接表是一种更节省空间的表示方式，尤其适用于稀疏图。每个顶点都有一个链表，链表中存储了该顶点的所有相邻顶点。比如，对于图：

0: 1 -> 3
1: 0 -> 2 -> 3
2: 1
3: 0 -> 1

• 优点：节省空间，尤其适合稀疏图。
• 缺点：查找某条边的时间复杂度较高，最坏情况下需要 ( O(n) )。

4. 图的基本操作

常见的图操作有：

• 查找相邻顶点：找到某个顶点所有的直接相邻顶点。
• 添加边：在图中增加顶点之间的连接。
• 删除边：移除顶点之间的连接。

5. 图的遍历

图的遍历方法有两种主要方式：

• 深度优先搜索（DFS, Depth-First Search）：通过递归或栈，从一个起点开始，尽量深入地遍历图中的节点，直到不能继续为止，然后回溯到上一个节点。
• 广度优先搜索（BFS, Breadth-First Search）：通过队列，从一个起点开始，逐层遍历相邻节点，优先访问离起点最近的节点。

6. 图的应用

图可以应用于很多实际问题，举例说明：

• 最短路径问题：在交通导航或社交网络中，找到两个节点之间的最短路径。常见算法有Dijkstra算法、Floyd-Warshall算法。
• 连通性问题：判断图中的节点是否相互连通。
• 拓扑排序：在有向无环图（DAG）中，找到一个没有冲突的执行顺序，如任务调度、编译器优化等。

7. 图的算法

一些重要的图算法包括：

• 最短路径算法：如Dijkstra、Bellman-Ford算法等。
• 最小生成树算法：如Prim和Kruskal算法，用于连接所有顶点的最小成本树。
• 连通分量算法：如强连通分量（SCC）算法，用于分解图的强连通部分。

总结来说，图是一种非常灵活且强大的数据结构，能够有效地表示和处理各种关系和结构。根据不同的应用场景，我们可以选择合适的图类型、表示方法和算法来处理具体问题。

出度与入度

出度和入度是图中用来描述顶点与其他顶点之间连接关系的重要概念，尤其在有向图（Directed Graph）中，它们有着非常重要的意义。

1. 出度（Out-degree）

出度指的是一个顶点指向其他顶点的边的数量。也就是说，在有向图中，一个顶点有多少条边从它出发，连接到其他顶点，出度就是该顶点的出度。

示例：

假设有一个有向图：

A → B → C
 \   ↑
  → D

• 顶点 A 的出度为 2，因为它有两条边指向 B 和 D。
• 顶点 B 的出度为 1，因为它有一条边指向 C。
• 顶点 C 的出度为 0，因为它没有任何边指向其他顶点。
• 顶点 D 的出度为 1，因为它有一条边指向 B。

2. 入度（In-degree）

入度指的是一个顶点被其他顶点指向的边的数量。也就是说，在有向图中，有多少条边指向某个顶点，这个顶点的入度就是这些边的数量。

示例：

继续以上图：

A → B → C
 \   ↑
  → D

• 顶点 A 的入度为 0，因为没有任何顶点有边指向 A。
• 顶点 B 的入度为 2，因为顶点 A 和 D 各有一条边指向 B。
• 顶点 C 的入度为 1，因为只有顶点 B 有一条边指向 C。
• 顶点 D 的入度为 1，因为只有顶点 A 有一条边指向 D。

3. 出度和入度的应用

出度和入度在图算法中有很多应用，尤其在处理有向图时，例如：

• 拓扑排序：在有向无环图（DAG）中，利用入度为 0 的顶点进行拓扑排序。比如，在任务调度问题中，一个任务的入度表示必须在这个任务之前完成的其他任务数。
• PageRank算法：出度和入度用于计算网页的权重，网页被其他页面引用的次数（入度）和它引用其他页面的次数（出度）会影响网页的重要性评分。
• 强连通性分析：通过出度和入度可以分析一个顶点是否可以到达其他顶点或被其他顶点访问，这在网络分析和社交网络建模中非常有用。

4. 出度和入度的计算

在实际图的表示方式中，计算出度和入度的方式略有不同：

• 邻接表：对于出度，直接查看某个顶点的邻接链表的长度即可；而入度则需要遍历整个邻接表，统计指向该顶点的边。
• 邻接矩阵：出度是某行中非零元素的数量，入度是某列中非零元素的数量。

总结：

• 出度表示顶点有多少条边指向其他顶点。
• 入度表示顶点被多少条边从其他顶点指向。

这些概念在理解有向图中的结构与算法时至关重要。

图的连通

在图论中，连通性是用来描述图中顶点之间是否能够通过边相互到达的特性。根据图的不同特点，连通性可以分为几种不同的类型，下面我会用通俗易懂的方式为你解释这些概念。

1. 连通的基本概念

在无向图中，两个顶点如果通过若干条边能够互相到达，我们就说这两个顶点是连通的。如果图中的所有顶点都彼此连通，那么这个图就是连通图。相反，如果图中存在一些顶点之间无法互相到达，那么这个图就是非连通图。

在有向图中，连通性可以更加复杂，因为边是有方向的。两个顶点之间的路径可能是单向的，也可能是双向的。

2. 连通的类型

a. 无向图的连通性

• 连通图（Connected Graph）：在无向图中，任意两个顶点之间都有路径相连。换句话说，图中没有“孤立”的顶点。比如：

  A -- B -- C
       | 
       D
  

  这个无向图就是连通的，因为从任意一个顶点都可以通过边到达其他顶点。

• 非连通图（Disconnected Graph）：在无向图中，存在顶点之间没有路径相连。例如：

  A -- B      C -- D
  

  这个图是非连通的，因为顶点 A 和 B 与顶点 C 和 D 之间没有任何连接。

b. 有向图的连通性

有向图中，连通性可以分为更细致的两种：

• 强连通图（Strongly Connected Graph）：在有向图中，任意两个顶点之间不仅有路径相连，而且路径是双向的，即从顶点 A 能到达顶点 B，反过来从顶点 B 也能到达顶点 A。如果图中的所有顶点都满足这个条件，那么这个图就是强连通图。比如：

  A → B
  ↑   ↓
  D ← C
  

  在这个有向图中，任意两个顶点之间都可以通过边互相到达，因此它是强连通图。

• 弱连通图（Weakly Connected Graph）：在有向图中，如果忽略边的方向，将它视为无向图后，图是连通的，那么这个有向图就是弱连通图。也就是说，虽然有些顶点之间的连接是单向的，但整个图中没有孤立的顶点。比如：

  A → B → C
  

  这个图是弱连通的，因为虽然 A 可以到 B，但 B 不能回到 A，然而如果忽略边的方向，A、B 和 C 仍然通过路径连通。

3. 如何区分连通的类型

• 无向图：只需检查所有顶点是否通过边彼此连通即可。如果所有顶点都能连通，则是连通图，否则是非连通图。

• 有向图：

  • 如果任意两个顶点都可以通过有向路径相互到达，则是强连通图。
  • 如果仅在忽略方向后可以相互连通，但有些路径是单向的，则是弱连通图。

4. 连通性的数学定义

在数学上，我们可以用路径和连通分量的概念来描述连通性。

• 路径：从顶点 ( u ) 到顶点 ( v ) 的路径是顶点和边的序列，使得每条边都连接前后两个顶点。如果存在从 ( u ) 到 ( v ) 的路径，称 ( u ) 和 ( v ) 是连通的。

  无向图的连通性：无向图是连通的，当且仅当对于所有顶点 ( u ) 和 ( v )，都存在一条从 ( u ) 到 ( v ) 的路径。

  有向图的强连通性：有向图是强连通的，当且仅当对于所有顶点 ( u ) 和 ( v )，都存在从 ( u ) 到 ( v ) 以及从 ( v ) 到 ( u ) 的路径。

用公式表达：
$$\forall u,v\in V,\exists \text{path}(u\to v)\wedge \exists \text{path}(v\to u)$$

有向图的弱连通性：有向图是弱连通的，如果我们将所有边的方向去掉，变成无向图后，所有顶点是连通的。

总结：

• 连通性描述图中顶点之间是否可以通过边相互到达。
• 无向图只有连通和非连通之分。
• 有向图有强连通和弱连通两种情况，强连通要求双向连通，弱连通则只需要忽略方向后连通。

连通性是图论中分析图结构的基础，理解这些概念有助于解决路径规划、网络连通等实际问题。

完全图

完全图是指一种特殊的图，图中任意两个顶点之间都有一条边相连。简单来说，就是每个顶点都和图中的其他所有顶点直接相连，没有遗漏的连接。

1. 完全图的特点

• 无向完全图（Complete Undirected Graph）：在无向图中，完全图中的每一对顶点之间都有一条无向边。例如，如果一个完全图有 3 个顶点（我们称之为 ( K_3 )），它们的连接情况如下：

  A -- B
  |  /
  C
  

  在这个图中，A、B、C 三个顶点之间两两都有边连接，所以是完全图。

• 有向完全图（Complete Directed Graph）：在有向图中，完全图中的每一对顶点之间都有双向的边，也就是说，两个顶点之间不仅有一条从 A 指向 B 的边，还有一条从 B 指向 A 的边。例如，3 个顶点的有向完全图：

在有向完全图中，所有顶点之间都有双向的连接。

2. 完全图的顶点数与边数的关系

如果一个无向完全图有 ( n ) 个顶点，那么这个图的边数是：

$$E=\frac{n(n-1)}{2}$$

因为每两个顶点之间都有一条边。

例如：

• 对于 3 个顶点的完全图，边数为：$$E=\frac{3(3-1)}{2}=3$$
• 对于 4 个顶点的完全图，边数为：$$E=\frac{4(4-1)}{2}=6$$

对于有向完全图，边数会是：

$$E=n(n-1)$$

因为每两个顶点之间都有两条边，一条从 A 到 B，另一条从 B 到 A。

3. 完全图的应用

完全图在实际中可以用于描述全连接的网络，比如：

• 社交网络中，每个人都和其他人直接有联系时，社交图可以被看作是一个完全图。
• 在通信网络中，完全图可以表示所有节点彼此直接通信的网络结构。

总结：完全图是一种图中每个顶点都与其他所有顶点直接相连的特殊图。在无向图中，所有顶点之间都有边；在有向图中，顶点之间有双向边。

图的邻接矩阵存储

在 C 语言中，可以通过邻接矩阵来存储图的结构。邻接矩阵是一种二维数组，用来表示图中的顶点和它们之间的边。无论是无向图还是有向图，邻接矩阵都能有效表示图的连接关系。

1. 邻接矩阵的结构

对于一个图，有 ( n ) 个顶点，我们可以使用一个 n x n 的二维数组来存储这些顶点之间的连接关系。

• 无向图：如果顶点 ( i ) 和顶点 ( j ) 之间有一条边，则矩阵元素 ( A[i][j] ) 和 ( A[j][i] ) 都为 1；否则为 0。

• 有向图：如果从顶点 ( i ) 到顶点 ( j ) 有一条边，则矩阵元素 ( A[i][j] ) 为 1；否则为 0。不同于无向图，有向图的 ( A[i][j] ) 和 ( A[j][i] ) 不对称。

• 带权图：可以在矩阵中存储边的权重（例如，距离、时间、费用等）。如果从 ( i ) 到 ( j ) 有边，则 ( A[i][j] ) 为权重；如果没有边，则 ( A[i][j] ) 可以为 0 或某个特定的无效值（如 -1 或 INF 表示无穷大）。

2. 存储结构

我们可以用一个二维数组来表示邻接矩阵，以下是一个简单的结构定义：

#include <stdio.h>

#define MAX_VERTICES 10  // 图中最大顶点数

// 定义邻接矩阵存储结构
typedef struct {
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];  // 二维数组存储边的关系
    int numVertices;  // 顶点数
} Graph;

在这个结构中，adjMatrix 是存储图的邻接矩阵，numVertices 是图的顶点数量。

3. 操作方法

对于邻接矩阵的操作，我们可以通过简单的赋值和访问来修改或查询顶点之间的连接情况。

• 初始化图：将邻接矩阵的所有元素初始化为 0（表示没有边）。

• 添加边：在无向图中，若顶点 ( i ) 和顶点 ( j ) 之间有一条边，则将 ( adjMatrix[i][j] ) 和 ( adjMatrix[j][i] ) 设为 1。在有向图中，只需将 ( adjMatrix[i][j] ) 设为 1。

• 查询是否存在边：通过检查矩阵中的值即可判断顶点 ( i ) 和顶点 ( j ) 之间是否有边。

4. 代码示例

以下是一个简单的例子，展示如何用 C 语言实现邻接矩阵的存储和操作。

#include <stdio.h>

#define MAX_VERTICES 5

// 定义图结构
typedef struct {
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
    int numVertices;  // 顶点数量
} Graph;

// 初始化图的邻接矩阵
void initGraph(Graph* g, int vertices) {
    g->numVertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->adjMatrix[i][j] = 0;  // 初始时没有边
        }
    }
}

// 添加边
void addEdge(Graph* g, int i, int j) {
    g->adjMatrix[i][j] = 1;  // 对于无向图
    g->adjMatrix[j][i] = 1;  // 双向边
}

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

int main() {
    Graph g;
    initGraph(&g, MAX_VERTICES);

    // 添加一些边
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 3, 4);

    // 打印邻接矩阵
    printf("邻接矩阵:\n");
    printGraph(&g);

    return 0;
}

5. 代码解释

• initGraph 函数初始化图的邻接矩阵，将所有的边设为 0，表示没有连接。
• addEdge 函数添加边。对于无向图，我们需要同时设置 ( adjMatrix[i][j] ) 和 ( adjMatrix[j][i] )。
• printGraph 函数打印邻接矩阵的内容，方便我们观察图的结构。

6. 输出结果

程序运行后的输出会显示邻接矩阵：

邻接矩阵:
0 1 1 0 0
1 0 1 1 0
1 1 0 0 0
0 1 0 0 1
0 0 0 1 0

这个矩阵对应的图为：

  0 -- 1 -- 3 -- 4
   \   |
     2

邻接表存储图

在 C 语言中，邻接表是一种存储图的常用方式，特别适合处理稀疏图，即边的数量远小于顶点的数量的图。相较于邻接矩阵，邻接表更加节省空间，因为它只存储存在的边，而不是所有可能的顶点对。

1. 邻接表的结构

邻接表将每个顶点的邻居顶点存储在一个链表（或其他动态数据结构）中。对于有 ( n ) 个顶点的图，我们会有 ( n ) 个链表，每个链表存储该顶点所有直接连接的邻居顶点。

• 无向图：如果顶点 ( i ) 和顶点 ( j ) 之间有一条边，则顶点 ( i ) 的邻接链表中会有顶点 ( j )，同样，顶点 ( j ) 的链表中也会有顶点 ( i )。

• 有向图：如果从顶点 ( i ) 到顶点 ( j ) 有一条边，则顶点 ( i ) 的邻接链表中会有顶点 ( j )，但顶点 ( j ) 的链表中没有 ( i ) 。

• 带权图：链表中可以存储权重信息，每个链表节点可以不仅仅存储邻居顶点，还可以存储与该邻居的边的权重。

2. 存储结构

邻接表的结构可以用数组 + 链表的形式来实现。数组的每个元素对应一个顶点，而每个元素是一个链表的头指针，链表的节点存储与该顶点相邻的顶点。

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

#define MAX_VERTICES 10

// 链表节点表示边
typedef struct AdjListNode {
    int dest;  // 邻居顶点的编号
    struct AdjListNode* next;  // 指向下一个邻接节点
} AdjListNode;

// 顶点的邻接表
typedef struct AdjList {
    AdjListNode* head;  // 邻接链表的头指针
} AdjList;

// 图结构
typedef struct {
    AdjList array[MAX_VERTICES];  // 顶点的数组，每个元素是一个链表
    int numVertices;  // 图中的顶点数
} Graph;

• AdjListNode 表示一个链表节点，其中 dest 表示邻居顶点的编号，next 指向下一个链表节点。
• AdjList 表示一个顶点的邻接表头。
• Graph 是一个包含多个顶点邻接表的图结构。

3. 操作方法

邻接表的操作主要包括：

• 初始化图：初始化图的顶点数量，并将每个顶点的邻接表头指针设为 NULL。
• 添加边：在邻接表中添加节点，表示两个顶点之间有边。
• 打印图：打印每个顶点的邻接表，显示顶点之间的连接关系。

4. 代码示例

以下是如何在 C 语言中实现邻接表存储的代码。

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

// 链表节点表示边
typedef struct AdjListNode {
    int dest;  // 邻居顶点
    struct AdjListNode* next;  // 指向下一个邻接节点
} AdjListNode;

// 顶点的邻接表
typedef struct AdjList {
    AdjListNode* head;  // 链表头指针
} AdjList;

// 图结构
typedef struct {
    int numVertices;  // 顶点数
    AdjList* array;  // 邻接表数组
} Graph;

// 创建链表节点
AdjListNode* createNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 初始化图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;

    // 创建邻接表
    graph->array = (AdjList*)malloc(numVertices * sizeof(AdjList));

    // 初始化每个顶点的邻接表
    for (int i = 0; i < numVertices; i++) {
        graph->array[i].head = NULL;
    }

    return graph;
}

// 添加无向边
void addEdge(Graph* graph, int src, int dest) {
    // 添加 src -> dest
    AdjListNode* newNode = createNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 添加 dest -> src (无向图)
    newNode = createNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

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

int main() {
    int numVertices = 5;
    Graph* graph = createGraph(numVertices);

    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);

    printGraph(graph);

    return 0;
}

5. 代码解释

• createNode 函数用于创建一个新的链表节点，表示某个顶点的邻居。
• createGraph 函数初始化一个图，分配内存并为每个顶点创建一个邻接表。
• addEdge 函数在无向图中添加边。对于无向图，源顶点和目标顶点都需要在彼此的邻接表中添加边。
• printGraph 函数打印每个顶点的邻接表，展示顶点之间的连接关系。

6. 输出结果

运行该程序后的输出显示每个顶点的邻接表：

顶点 0 的邻接表: 4 -> 1 -> NULL
顶点 1 的邻接表: 4 -> 3 -> 2 -> 0 -> NULL
顶点 2 的邻接表: 3 -> 1 -> NULL
顶点 3 的邻接表: 4 -> 2 -> 1 -> NULL
顶点 4 的邻接表: 3 -> 1 -> 0 -> NULL

这个邻接表对应的图为：

  0 -- 1 -- 2
  |   |    |
  4 -- 3 -- 

总结：

• 邻接表使用数组加链表的方式存储图，适合用于稀疏图，因为只存储实际存在的边。
• 无向图在两个顶点的邻接表中都要添加边，而有向图只需在源顶点的邻接表中添加边。
• 与邻接矩阵相比，邻接表更加节省空间，特别是在顶点很多但边比较少的情况下。

总结：

• 邻接矩阵是一种用二维数组表示图的方式，适合存储顶点不多的图。
• 在无向图中，矩阵是对称的，而在有向图中，矩阵不对称。
• C 语言中可以用一个二维数组来存储邻接矩阵，通过简单的赋值和访问操作，可以轻松管理图的连接关系。

总结

图论为我们提供了强大的工具来解决现实世界中的很多复杂问题。通过对顶点、边及其关系的建模，我们可以轻松表示并处理网络流、路径规划、社交关系等问题。无论是在 CSP-J 这样的竞赛中，还是在日常开发工作中，图论的基础算法，如图的遍历、最短路径算法、最小生成树等，都可以帮助我们以更加高效的方式解决问题。

熟练掌握图的基本算法，不仅能提高算法竞赛中的解题能力，也能为处理复杂的系统设计和优化问题提供有力的支持。在深入学习图论的过程中，建议多做练习、理解各种经典算法的实现原理，并结合实际问题去思考其应用场景。通过不断的积累，掌握图论不仅仅是一种竞赛技巧，更是一种解决实际问题的思维方式。