图

• 1: 定义
• 2: 算法和应用

# 图

## 图的基本概念

## 图的存储结构及基本操作

- 邻接矩阵
- 邻接表
- 邻接多重表、十字链表

## 图的遍历

- 深度优先搜索
- 广度优先搜索

## 图的基本应用

- 最小生成树
- 最短路径
- 拓扑排序
- 关键路径

1 - 定义

图的概念

图是由顶点和边组成的非线性数据结构。顶点有时也被称为节点，而边是连接图中任意两个节点的线或弧。更正式地说，图是由一组顶点 $(V)$ 和一组边 $(E)$ 组成的。图用 $G(E, V)$ 表示。

在图论中，根据边的方向性、连接方式、顶点间的关系等，可以进一步划分出多种类型的图，并引入如连通性、完全性、度数等一系列关键概念。这些分类和术语有助于我们更好地理解图的结构特点和应用场景，下面我们将逐一进行介绍。

方向

• 有向图（directed graph）：边是有方向的，从一个定点指向另一个定点
• 无向图（undirected graph）：边是没有方向的

连通性

• 连通图（Connected Graph）：图中的每一对不同顶点都可以通过一条或多条边相互连接，也就是说，从图中的任意一个顶点出发，都可以到达图中的任意其他顶点。
• 非连通图（Disconnected Graph）：图中存在两个或多个互不相连的子图，也就是说，其中至少存在一个顶点集合，无法通过边连接到图中的其他顶点集合。
• 完全图（Complete Graph）：完全图是一种特殊的图，其中每一对不同的顶点都直接相连，也就是说，完全图中的任意两个顶点之间都存在一条边。如果一个完全图有 n 个顶点，那么它将有 $C(n, 2) = n(n-1)/2$ 条边，其中 $C(n, 2)$ 表示从 n 个顶点中选择 2 个顶点的组合数。

• 连通分量（Connected Components）：连通分量（Connected Components），也称为连通子图，是一个无向图中的一个重要概念。一个连通分量是指在无向图中，如果从其中一个顶点出发，可以通过边的路径到达该连通分量内的任何其他顶点，而无法通过图中的边到达其他连通分量内的顶点。

度

• 顶点的度（Degree）：顶点的度是指与该顶点相邻的边的数量，也就是与该顶点直接相连的其他顶点的个数。对于有向图和无向图都适用。
  • 在无向图中，顶点的度就是与该顶点相邻的边的数量。
  • 在有向图中，顶点的度分为入度和出度，分别表示指向该顶点的边的数量和从该顶点出发的边的数量的总和。
• 入度（In-Degree）：入度是指在有向图中指向某个顶点的边的数量，也就是与该顶点关联的边中以该顶点为终点的边的数量。
• 出度（Out-Degree）：出度是指在有向图中从某个顶点出发的边的数量，也就是与该顶点关联的边中以该顶点为起点的边的数量。

路径

• 简单路径：顶点 不出现重复 的路径
• 非简单路径：顶点出现重复的路径
• 回路：路径的起点和终点相同

图的存储

在我们使用数据结构存储图时，主要关注两点：1. 如何存储顶点？ 2. 如何存储边？ 采用的数据结构需要能够准备表示这些信息。

邻接矩阵

定义

图的邻接矩阵（Adjacency Matrix）是一种常用的图表示方法，特别适用于稠密图，它以矩阵的形式表示图的连接关系。

在邻接矩阵中，行和列分别代表图的顶点，矩阵的元素表示顶点之间是否相邻或者边的权重。

1. 对于无向图：
   • 如果顶点 $i$ 和顶点 $j$ 之间存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $1$ （或者表示边的权重）。
   • 如果顶点 $i$ 和顶点 $j$ 之间不存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $0$ 。
2. 对于有向图：
   • 如果有一条从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $1$ （或者表示边的权重）。
   • 如果没有从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $0$ 。

实现

在邻接矩阵的实现中，我们使用一个二维数组来表示图的连接关系，邻接矩阵 matrix 的行数和列数与图中的顶点数量相同。 其中 matrix[i][j] 表示顶点 i 到顶点 j 是否有边（或边的权值）。

• 邻接矩阵定义
• 添加边

##define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵

// 初始化邻接矩阵
void initializeMatrix(int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0; // 初始化所有元素为 0
        }
    }
}

// 在邻接矩阵中添加一条边
void addEdge(int start, int end) {
    adjMatrix[start][end] = 1; // 添加边，将对应位置的元素设为 1
    adjMatrix[end][start] = 1; // 无向图需要将对称位置的元素也设为 1
}

入度出度

如果需要计算邻接矩阵中某个顶点的 出度 的话，假设顶点编号为 i，我们统计邻接矩阵中的 第 i 行 有多少元素不为 0 即可（该顶点指向哪些顶点）。

如果需要计算邻接矩阵中某个顶点的 出度 的话，假设顶点编号为 i，我们统计邻接矩阵中的 第 i 列 有多少元素不为 0 即可（哪些顶点指向该顶点）。

邻接表

定义

图的邻接表（Adjacency List）是一种常见的图表示方法，特别适用于稀疏图，它使用链表或数组的形式来表示图的连接关系。每个顶点都对应一个链表，链表中存储与该顶点相邻的其他顶点。

邻接表的主要思想是为每个顶点创建一个链表，链表中的每个节点表示与该顶点相邻的另一个顶点。对于无向图，通常需要为每一条边创建两个链表节点，分别表示两个相邻的顶点。

实现

在邻接表的实现中，我们为每个顶点维护一个链表，用于存储与该顶点相邻的所有顶点；所有顶点对应的链表头节点组成一个数组或列表（在以下实现为 struct AdjList *array），形成整个图的邻接表结构。

• 数据结构
• 创建新节点
• 创建图
• 添加边

// 链表节点结构：表示邻接的一个顶点
struct Node {
    int dest;            // 邻接顶点的编号
    struct Node* next;   // 指向下一个邻接点
};

// 邻接表：每个顶点有一个链表
struct AdjList {
    struct Node* head;   // 链表头
};

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

struct Node* newNode(int dest) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->dest = dest;
    node->next = NULL;
    return node;
}

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));
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    // src -> dest
    struct Node* n1 = newNode(dest);
    n1->next = graph->array[src].head;
    graph->array[src].head = n1;

    // dest -> src（因为是无向图）
    struct Node* n2 = newNode(src);
    n2->next = graph->array[dest].head;
    graph->array[dest].head = n2;
}

邻接多重表

邻接多重表（Adjacency Multi-list）是一种用于表示 无向图 的数据结构，主要用于避免在邻接表存储方式中重复存储无向边，提高存储效率，同时便于图的操作（如边的删除）。

邻接多重表中顶点种类分为两种：

• 顶点结点（Vertex Node）：
  • 每个顶点有一个头结点，存储该顶点的信息，以及指向其所有关联边的指针。
• 边结点（Edge Node）：
  • 每条边有一个结点，存储该边的两个顶点及其相关信息。
  • 该结点包含两个指针，分别指向该边所连接的两个顶点的邻接边链表的下一条边，使得图的存储更加紧凑。

还是举个实际例子说明，在上述的邻接多重表中，总共需要存储 5 条边，每条边只需要存储一次，所以总共有 5 个边结点，每个边结点中存储的数据如下表所示：

总结一下，相比于邻接表，邻接多重表最大的不同在于如下两点：

• 节省存储空间：对于无向图，每条边只存储一次。
• 方便进行边的操作：例如，删除一条边时，只需要修改相关顶点的链表中的指针，而不需要像邻接表那样在两个顶点的邻接表中都进行操作。

十字链表

十字链表（Orthogonal List）是一种用于表示 有向图 的链式存储结构，它兼顾了出边和入边的高效查找。相比邻接表只方便查找出边，十字链表允许同时高效遍历某个顶点的所有出边和所有入边。

在十字链表（Orthogonal List）中，顶点种类也可以分为两种：

• 顶点结点：
  • 每个顶点对应一个头结点，存储该顶点的信息；
  • 同时包含两个指针：
    • firstout：指向从该顶点出发的第一条出边；
    • firstin：指向以该顶点为终点的第一条入边；
  • 这样可分别建立“出边链表”和“入边链表”。
• 边结点：
  • 每条有向边对应一个边结点，存储该边的起点和终点在顶点表中的位置；
  • 包含两个指针，使该边同时链接在：
    • 起点顶点的出边链表中（通过 hlink）；
    • 终点顶点的入边链表中（通过 tlink）；
  • 边结点也可扩展存储额外信息（如权重）。

下图给出了一个十字链表的一个实例，其中忽略了边结点的 info 字段。我们可以沿着顶点结点的 firstin 和 firstout 字段高效遍历所有的入边和出边。

2 - 算法和应用

DFS

深度优先搜索（Depth-First Search，简称 DFS）是一种用于图的遍历和搜索的算法，它从图中的一个起始顶点开始，尽可能深地访问顶点，直到无法继续前进，然后回溯到之前的顶点，继续深入其他分支。DFS 通常用递归或栈来实现，确保在深度方向上优先遍历。

以下是 DFS 算法的一般步骤：

1. 从起始顶点开始，将其标记为已访问。
2. 遍历与当前顶点相邻的未访问顶点，选择其中一个未访问顶点作为下一个深度遍历的目标，然后递归地进行 DFS。
3. 如果无法继续深度遍历（即当前顶点没有未访问的邻居），则回溯到上一个顶点，继续遍历其他未访问的邻居。
4. 重复步骤 2 和步骤 3，直到所有顶点都被访问。

图中 DFS 实现的框架与 树的遍历 类似，不同点在于需要使用 visit 数组记录已经访问过的节点，避免重复遍历：

function DFS(G, v, visited):
    visited[v] ← true
    for each neighbor u of v in G.adjacent[v]:
        if not visited[u]:
            DFS(G, u, visited)

图在邻接矩阵和邻接表中的 DFS 都遵循这个框架，两者的不同点在于获取 v 的邻居 u 的方式不同。

邻接矩阵

在邻接矩阵中，我们定义一个递归函数 dfs，函数从 start 顶点出发，输出当前结点，然后递归地去访问所有与其相邻的顶点。

注意递归前需要保证下一个顶点未被访问过，这样可以避免重复访问结点以及死循环。

// 全局变量，标记顶点是否被访问过
int visited[MAX_VERTICES];

// 递归函数，从 start 顶点出发
void dfs(int start) {
    visited[start] = 1;
    printf("%d ", start);

    // 依次访问 start 的邻接顶点
    for (int i = 0; i < MAX_VERTICES; i++) {
        // 递归的两个条件：
        // 1. 顶点 (start, i) 之间存在边
        // 2. 顶点 i 未被访问过
        if (adjMatrix[start][i] == 1 && !visited[i]) {
            // 递归调用
            dfs(i);
        }
    }
}

邻接表

邻接表的递归思路与邻接矩阵一致，唯一的区别就是访问邻接顶点方式的不同。

在邻接矩阵中，通过遍历矩阵中的一行来访问相邻顶点。在邻接表中，通过遍历链表来访问相邻顶点。

// 全局变量，标记顶点是否被访问过
int visited[MAX_VERTICES];

// 递归函数，从 start 顶点出发
void dfs(struct Graph* graph, int start) {
    visited[start] = 1;
    printf("%d ", start);

    // 依次访问 start 的邻接顶点
    struct Node* temp = graph->adjacencyList[start];
    while (temp) {
        int adjVertex = temp->data;
        // 递归条件：顶点 i 未被访问过
        if (!visited[adjVertex]) {
            dfs(graph, adjVertex);
        }
        temp = temp->next;
    }
}

BFS

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于图的遍历和搜索的算法，它从图中的一个起始顶点开始，逐层地访问与该顶点相邻的顶点，然后再访问这些相邻顶点的邻居，以此类推。BFS 通常用队列来实现，确保按照广度优先的顺序访问顶点。

以下是 BFS 算法的一般步骤：

1. 将起始顶点放入队列中，标记为已访问。
2. 从队列中弹出一个顶点并访问它。
3. 遍历该顶点的所有未被访问的邻居，将它们放入队列中，并标记为已访问。
4. 重复步骤 2 和步骤 3，直到队列为空。

BFS 的伪代码实现如下所示，基于邻接矩阵或邻接表的 BFS 都遵循这个框架：

function BFS(G, start):
    visited[start] ← true
    enqueue(Q, start)

    while Q is not empty:
        v ← dequeue(Q)
        process(v)
        for each neighbor u of v in G.adjacent[v]:
            if not visited[u]:
                visited[u] ← true
                enqueue(Q, u)

邻接矩阵

实现 bfs 时，首先添加起始顶点进入队列中，然后不断从队列中取出顶点，并添加该顶点的未访问相邻顶点进入队列。 重复直到队列为空。

在 dfs 中，visited 数组是各个递归函数都需要访问的数据结构，为了方便起见，可以定义为全局变量。 在 bfs 中，由于算法实现是基于迭代而非递归，所以 visited 和 队列 可以定义为局部变量。

// 从 start 开始遍历图
void bfs(int start, int vertices) {
    // 队列 q
    queue q;
    // 标记顶点是否被访问过
    int visited[MAX_VERTICES];
    // 添加初始顶点
    q.enqueue(start);
    visited[start] = 1;

    // 一直遍历到队列为空
    while (q.size() > 0) {
        // 从队列头部取出结点作为当前结点
        int currentVertex = q.dequeue();
        // 输出当前结点
        printf("%d ", currentVertex);
        // 将当前结点的所有 相邻的未访问顶点 添加到队列中
        for (int i = 0; i < vertices; i++) {
            if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                q.enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

邻接表

实现思路与邻接矩阵方式一致，不同点在与访问相邻顶点的方式不同。

void bfs(struct Graph* graph, int start) {
    // 队列 q
    queue q;
    // 标记顶点是否被访问过
    int visited[MAX_VERTICES];
    // 添加初始顶点
    q.enqueue(start);
    visited[start] = 1;

    // 一直遍历到队列为空
    while (front != rear) {
        // 从队列头部取出结点作为当前结点
        int currentVertex = q.dequeue();
        // 输出当前结点
        printf("%d ", currentVertex);
        // 将当前结点的所有 相邻的未访问顶点 添加到队列中
        struct Node* temp = graph->adjacencyList[currentVertex];
        while (temp) {
            int adjVertex = temp->data;
            if (!visited[adjVertex]) {
                q.enqueue(adjVertex);
                visited[adjVertex] = 1;
            }
            temp = temp->next;
        }
    }
}

最小生成树

最小生成树（Minimum Spanning Tree，MST）是在一个连接所有顶点的无向图中，通过选择一部分边而形成的树，使得树的总权重（或成本）最小。

准确的最小生成树定义如下：在无向图 $G = (V, E)$ 中，$(u, v)$ 代表连接顶点 $u$ 和顶点 $v$ 的边，而 $w(u, v)$ 代表此边的权重，若存在 $T$ 为 $E$ 的子集且 $(V, E)$ 为树，使得 $w(T) = \sum_{(u, v) \in T} w(u, v)$ 最小，则此 $T$ 为 $G$ 的最小生成树。

最小生成树满足以下特点：

• 包含图中的所有顶点。
• 通过选择一些边而形成一个树结构，没有环路。
• 边的总权重最小。

prim 算法

Prim 算法的主要思想是从一个初始顶点开始，逐步扩展生成树，每次选择与当前生成树相邻且权重最小的边所连接的顶点，并将该顶点加入生成树。算法的运行过程可以概括为以下步骤：

1. 选择一个起始顶点作为生成树的根节点。
2. 初始化一个空的生成树，包含初始顶点。
3. 将与生成树中的顶点相邻且权重最小的边的另一端顶点加入生成树，即选择一条最小权重边。
4. 重复步骤 3，直到生成树包含了所有的顶点。
5. 最终生成树即为原图的最小生成树。