这是本节的多页打印视图。 点击此处打印.

返回本页常规视图.

数据结构---图

描述

图是由[节点(Node)]通过[边(Edge)]相连组成的集合，用以表示实体之间的关系。图可以用 来建模社交网络、计算机网络、交通网络等。图包 含[顶点（节点）]和[边（节点之间的连接）]。图可以是[有向的]也可以是[无向的]，并且 可以[包含环]或者是[无环的]。图的遍历算法包括[广度优先搜索]和[深度优先搜索]。

图的术语

  • 顶点: 顶点
  • 边：顶点之间的连接线称为边。
  • 路径：从一个顶点到另一个顶点之间经过的所有顶点的描述
  • 路径长度：路劲上对单元路线的计量。
  • 环：起点和终点为同一个顶点的路径。
  • 负权环：在「加权图」中，如果一个环的所有边的权重加起来为负数，我们就称之为 「负权环」。
  • 连通性：两个不同顶点之间存在至少一条路径，则称这两个顶点是连通的。
  • 顶点的度：「度」适用于无向图，指的是和该顶点相连接的所有边数称为顶点的度。
  • 顶点的入度：「入度」适用于有向图，一个顶点的入度为 𝑑 d，则表示有 𝑑 d 条与 顶点相连的边指向该顶点。
  • 顶点的出度：「出度」适用于有向图，它与「入度」相反。一个顶点的出度为 𝑑 d， 则表示有 𝑑 d 条与顶点相连的边以该顶点为起点。

图的分类

  • 无向图: 边的两个节点是没有顺序关系的, A-B 和 B-A 是一条边
  • 有向图: 边的两个节点是有顺序关系的, A->B 和 B->A 是不同的
  • 加权图: 图中的每条边带有一个权重的参数

图的相关算法

  • 并查集（ Union Find ）数据结构
  • 「图」的深度优先搜索算法
  • 「图」的广度优先搜索算法
  • 最小生成树相关定理和算法
    • 切分定理
    • Kruskal 算法
    • Prim 算法
  • 单源最短路径相关算法
    • Dijkstra 算法
    • Bellman-Ford 算法
  • 拓扑排序之 Kahn 算法

1 - 图的表示方法

描述

邻接矩阵

用一个二维矩阵来存储两个节点之间的状态

缺点: 面对稀疏图时，有很多空间没有储存有效信息

  • 确定邻接至或邻接于一个给定节点的集合需要用时 \(\Theta{(n)}\), 增加或删除一条 边仅需要 \(\Theta{(1)}\)

邻接链表

只考虑那些有连边的点对

对一个有 n 个点的图, 可以用 n 个链表, 第 i 个链表中存着从 i 直接连接的点

链式前向星表示的图

链式前向星（也称为邻接表的一种变种）是一种用于存储图的数据结构，它结合了数组和链表的优点，既节省空间又方便使用。在链式前向星中，每个节点的边不是直接存储在一个链表中，而是通过一个数组来存储所有边的信息，同时使用两个辅助数组来记录每条边的起点以及下一条边的位置。

2 - 图的深度优先搜索算法

描述

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。

DFS 的基本思想是从一个初始节点开始，尽可能[深入地探索]其子节点，直到无法继续深入 为止，然后回溯到上一个节点，继续探索其他未访问过的分支。这种策略类似 于[树的先序遍历] 。

DFS 的基本步骤

  1. 选择一个其实节点: 选择图中的任意一个节点作为起始节点
  2. 标记节点为已访问: 将当前节点标记为已访问，避免重复访问
  3. 递归访问相邻节点: 对于当前节点的每一个未访问过的相邻节点，递归地执行 DFS
  4. 回溯: 当当前节点的所有相邻节点都被访问过之后，回溯到上一个节点，继续访问 其他未访问过的分支

3 - 图的广度优先搜索算法

描述

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树或图的算法。 这种算法从根节点开始，然后遍历所有[相邻的]节点，之后对于每一个相邻的节点，再遍历 它们未访问过的相邻节点，依次类推，直到所有的节点都被访问过为止。BFS 是一种逐层扩 展节点的搜索策略，即先搜索离起始节点最近的所有节点，然后再搜索下一层的节点。

BFS 的基本步骤

  1. 初始化：选择一个起始节点，将其标记为已访问，并放入队列中。
  2. 处理队列中的节点：
    1. 从队列中移除第一个节点。
    2. 对于这个节点，访问它所有的邻接点。如果某个邻接点没有被访问过，则标记这个邻 接点为已访问，并将其添加到队列的末尾。
  3. loop[2]，直到队列为空。

在实际操作中，为了防止重复访问同一个节点，通常需要使用一个数据结构来记录已经访 问过的节点。此外，队列是实现 BFS 的关键数据结构，因为它是先进先出（FIFO）的数 据结构，能够确保节点按照其被发现的顺序被处理。

4 - 最小生成树

描述

生成树（Spanning Tree）是[图论]中的一个重要概念，尤其在处理连通图时非常有用。生 成树是指一个[无向图]的一个子图，它是一个包含图中所有顶点的树。也就是说，生成树是 一棵包含了原图中所有节点的[无环连通子图]

最小生成树

最小生成树（Minimum Spanning Tree, MST）是图论中的一个基本概念，特别是在处理加权 无向图时非常重要。给定一个加权无向图，最小生成树是指该图的一个生成树，其中所有边 的权重之和是最小的。这意味着，在保证所有节点连通的情况下，最小生成树选取的边的总 成本最低

5 - 单源最短路径算法