Skip to main content

图论

David LiuAbout 6 min

图论

图可以先生成好再遍历，也可以边遍历边生成（推荐变遍历边生成）

dfs时有的时候需要记录parent/from防止出现平凡环/走回头路

编号：图是一个抽象的结构，一定要为图中每一个节点赋值一个唯一的编号。

  • 一般来说，题目上给的节点是按照数组给的有一个默认编号 0到n-1或 1 到 n
  • 没有的情况下，需要用哈希表来记录元素到编号，如合并账户这一题

在我们开始实际执行深度优先搜索之前，让我们快速地向自己确保，邻接表 是这个问题的最佳图形表示。另外两个选项是 邻接矩阵 或 链表表示。

对于这个问题，一个 邻接矩阵 将是一个可以接受的表示，尽管不是很理想。通常，只有当我们知道边数大大高于节点数时，我们才会使用邻接矩阵。我们没有理由相信情况就是这样。方法 2 也将对此提供一些有用的见解。
将实际节点作为对象的 链表表示法 是一种过于复杂的表示法，可能会向面试官暗示您对邻接列表和邻接矩阵的了解有限。它们在面试问题中并不常用。

图的存储/表示

  • 邻接矩阵

    二维数组graph[i][j]，表示i, j之间的距离

  • 邻接表 adjacencyList

    有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。

    图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。

    List<Integer>[] next = new List[n]

    List<Integer>[] adjacencyList = new List[n]

    List<List<Integer>> adjacencyList = new ArrayList<>()

    好处：节省空间，便于遍历

    List<int[]>[] e = new List[n];

  • 边存储

    一个边的数组，每个元素都是起点、终点的二元组

    给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。

    eg. [[0, 1], [0, 2], [1, 2]]

    有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

    好处：适合用并查集，题目一般是给一组边，然后用户根据题意选择合适的方式建图

特殊图

  • 矩阵图（比如一个二维棋盘）
  • 有向无环图 DAG, 无需visited数组，因为不会走回头路
    • 树

树

图 G 是树当且仅当满足以下两个条件：

  1. G 完全连通。换句话说，对于 G 中的每一对点，都有一条路径连接彼此。
  2. G 不包含环。换句话说，对于 G 中的每一对点只有一条路径连接彼此。

或者当且仅当

  1. 检查是否是 n-1 条边。如果没有，则返回 false。
  2. 完全连通：检查该图是否完全连通。如果是，则返回 true，否则返回 false。

图的遍历

遍历过程中要有一个visited数组或表防止一个点重复遍历

  • 深度优先搜索

    好处：代码简短多种类型的状态好存，有先序后序

  • 广度优先搜索

    好处：可用于无权图的最短路径问题

染色法/三色标记法，判断二分图和环的图

根据题意，若起始节点位于一个环内，或者能到达一个环，则该节点不是安全的。否则，该节点是安全的。

我们可以使用深度优先搜索来找环，并在深度优先搜索时，用三种颜色对节点进行标记，标记的规则如下：

白色（用 000 表示）：该节点尚未被访问；
灰色（用 111 表示）：该节点位于递归栈中，或者在某个环上；
黑色（用 222 表示）：该节点搜索完毕，是一个安全节点。

Tarjan 算法

Tarjan 是著名计算机科学家。Tarjan 算法基于 dfs，可以玩出很多花样，比如求无向图的割点、无向图的桥边（割边）、无向图的双连通分量、有向图的强连通分量。用于不同问题时，写法略有区别。

Tarjan 算法的关键点有二：

在 dfs 的过程中，记录每个节点初次被访问的时间戳
计算每个节点能访问到的节点的最小时间戳。

这个算法理解起来略微痛苦，需要结合代码仔细体会其细节。

环

平凡环：无向图里面A->B, B->A构成一个平凡环

自环：一个节点有一条指向自己的边

三色标记法

拓扑排序

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图

连通分量

我们可以将每一个变量看作图中的一个节点，把相等的关系 == 看作是连接两个节点的边，那么由于表示相等关系的等式方程具有传递性，即如果 ab 和 bc 成立，则 a==c 也成立。也就是说，所有相等的变量属于同一个连通分量。因此，我们可以使用并查集来维护这种连通分量的关系。

最短路

Dijkstra

在研究这种方法之前，快速了解一下 Dijkstra 算法。

Dijkstra 算法是一个非常著名的图算法，用于找到给定加权图（图的边表示节点之间的距离）中从任何起始节点到任何目标节点的最短路径。

该算法包括以下步骤：

  1. 为每个节点分配一个临时距离值：对于我们的起始节点，将其设置为零，对于所有其他节点，将其设置为无穷大。

  2. 将起始节点设置为当前节点。标记它为已访问。

  3. 对于当前节点，考虑其所有相邻节点并计算它们的临时距离。将新计算的临时距离与当前分配的值进行比较，并将较小的值分配给所有相邻节点。例如，如果当前节点 A 的距离标记为 6，并且与相邻节点B相连的边长为 2，则到B(通过A)的距离将为 6 + 2 = 8。如果 B 之前标记的距离大于 8，则将其更改为 8。否则，保留当前值。

  4. 当我们完成考虑当前节点的所有相邻节点时，将当前节点标记为已访问。已访问的节点将不再被检查。

  5. 如果目标节点已标记为已访问，或者所有剩余节点中最小的临时距离为无穷大(表示无法到达目标节点)，则停止。算法已完成。

  6. 否则，选择标记为未访问的节点中具有最小临时距离的节点，并将其设置为新的当前节点，然后返回到步骤 3。

可以通过两个简单的示例来了解该算法的工作原理。首先，考虑下面的节点集。

David's Blog
Copyright © 2024 David Liu