图

图的表示图的搜索拓扑排序 BFS入度表法图中最大环并查集 Dijikstra (不会考)速通参考

图的表示

邻接表 adjacency list


graph = [[] for _ in range(节点数)]
graph[节点1].append(节点2)
...

邻接矩阵 adjacency matrix


# 矩阵中，值为0 表示无连接，数字表示权重
graph = [[0] * 节点数 for _ in range(节点数)]
graph[节点1][节点2] = 1

图的搜索

完整参考

🌔

BFS ，

🎋

DFS & 回溯

拓扑排序

概念介绍

入度 & 出度：

入度：进入该节点的边的条数

出度：从该节点出发的边的条数

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。

若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

注：有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

拓扑排序通常用来“排序”具有依赖关系的任务。比如盖房子要先建地基，比如要想吃鸡一般要先搜二级以上头甲，比如上课程A需要先上课程B。

实现方式有两种：

(Yes) BFS Kahn算法, 基于贪心，每次从入度为0的点开始，正序为拓扑

(No) DFS 基于搜索，每次保证当前点出度为0后才遍历，逆序为拓扑。不推荐！！！

BFS入度表法

从图中选择一个入度为0的节点，输出该节点

从图中删除该节点及其所有接边（即与之相邻的所有节点入度 -1）

反复执行这两个步骤，直到所有节点都输出，即整个拓扑排序完成。或者直至剩下的图中没有入度为0的点，这就说明图中有回路，不可能进行拓扑排序。

对于如下有向无环图，使用BFS 进行拓扑排序过程如下：

先选择1，2 是因为 1，2 的入度为0；然后是3，因为此时3的入度为0；然后是 4，最后是5。

因此，拓扑排序可以用来判断图中有没有环，即直接判断从队列中出来的节点个数是否等于所有节点个数。环中的节点是没法进入队列的，因为入队列的前提的入度为0，而环中的节点入度均不是0。

模板


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 建图 建入度
        indegree = [0 for _ in range(numCourses)]
        graph = collections.defaultdict(list)
        for node in prerequisites:
            graph[node[1]].append(node[0])
            indegree[node[0]] += 1

        # 找入口
        queue = []
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)

        # BFS拓扑排序
        count = 0
        while queue:
            cur = queue.pop(0)
            count += 1
            for node in graph[cur]:
                indegree[node] -= 1
                if indegree[node] == 0:
                    queue.append(node)
                    
        return count == numCourses

题目为：207：课程表

经典题目

剑指 Offer II 114. 外星文字典

图中最大环

用并查集找环，拓扑排序+BFS 找环

565. 数组嵌套

765. 情侣牵手

6135. 图中的最长环

并查集

完整知识点参考

💫

并查集。并查集需要掌握的：

基本的模板（在find中做 path compression 优化）

在union中做优化的两种模板。一种是统计当前集合个数的，另外一种是统计当前集合树深度的。

理解并背诵 path compression 优化的技巧和两种union优化的策略

📎

+ 如果是考集合的数目，最后可以通过统计 uf.parents[i] == i 的个数来计算如547 839 + 如果是考某集合的最大元素数量，那么通过第二种优化策略，通过size数组来辅助，最后直接返回uf.size的最大值即可如128，695 对于矩阵，将矩阵拉平，那么初始化并查集大小为 m*n, 且每个位置（i，j）对应的是 i * n + j, 其中n为矩阵的列数。不要怕进行多次union，因为如果本来就是同一个集合中的元素，那么执行union的时候，只是会进行两次查找，且查找的时候，还会进行路径压缩优化！进行路径优化的时候，也就是find时的优化，并不需要更新集合的大小，也不需要更新树的深度！！

经典题目