一、图的基本概念

在力扣中，“图”通常指由 顶点（Nodes / Vertices） 和 边（Edges） 组成的数据结构。图可以是：

有向图（Directed Graph）：边有方向，例如 A -> B 表示只能从 A 到 B。
无向图（Undirected Graph）：边无方向，例如 A - B 表示 A 可以到 B，B 也可以到 A。
带权图（Weighted Graph）：边有权重（cost、距离等）。
无权图（Unweighted Graph）：边没有权重。

老马啸西风2025年10月1日大约 3 分钟

完全可以先确认一点：在图中，理论上只要能用 DFS 遍历的图，也可以用 BFS 遍历，因为两者都是遍历整个连通分量的算法。

它们的根本区别不在“能否遍历”，而在遍历顺序、应用场景和性能差异。

下面详细分析：

一、DFS 和 BFS 的核心区别

特性	DFS	BFS
遍历顺序	深度优先，尽可能沿一条路径走到底再回溯	广度优先，按层（距离起点的步数）访问
数据结构	栈 / 递归调用栈	队列
访问顺序	先访问子节点最深的路径	先访问距离起点最近的节点
适用场景	搜索路径、连通分量、拓扑排序、回溯	最短路径（无权图）、层序问题、分层处理
性能	空间复杂度受递归深度影响（最坏 O(V)）	空间复杂度受队列影响（最坏 O(V)）

老马啸西风2025年10月1日大约 4 分钟

图的连通性（Graph Connectivity）

一、图连通性的基本概念

在图论中，**连通性（Connectivity）**描述图中节点之间可达的关系：

节点可达（Reachability）：如果存在一条从节点 A 到节点 B 的路径，则称 A 可达 B。
连通图（Connected Graph）：
- 无向图：如果任意两个节点之间都有路径，称图是连通的。
- 有向图：
  - 强连通（Strongly Connected）：每对节点 u,v 都有路径 u→v 和 v→u。
  - 弱连通（Weakly Connected）：将有向图看作无向图后连通，则称弱连通。

老马啸西风2025年10月1日大约 2 分钟

并查集 union-find 入门介绍

1️⃣ 并查集的本质

并查集是一种用于 动态维护不相交集合（Disjoint Sets） 的数据结构，核心目的是快速判断元素是否属于同一个集合，以及将两个集合合并。

用途：
- 判断图中两个节点是否连通
- 求连通分量个数
- 处理网络、社交关系、群体合并等问题
核心思想：
- 每个集合有一个“代表元素”（root）
- 每个元素只保存指向父节点的指针
- 查找元素的根节点可以判断是否属于同一个集合
- 合并两个集合就是把一个集合的根挂到另一个根上

老马啸西风2025年10月1日大约 6 分钟

堆(优先队列) heap 入门介绍

1️⃣ 堆的概念

堆是一种 完全二叉树（Complete Binary Tree） 的数据结构，同时满足 堆性质（Heap Property）：

最大堆（Max-Heap）：每个节点的值都 大于等于其子节点的值。
最小堆（Min-Heap）：每个节点的值都 小于等于其子节点的值。

特点：

完全二叉树：树除了最后一层外，其他层都满；最后一层从左到右依次填充。
根节点是堆中最大（最大堆）或最小（最小堆）的值。
堆一般用数组来实现，而不是指针型节点。

老马啸西风2025年10月1日大约 3 分钟

Tree-00-概览

排序

二分查找法

Tree

二叉查找树

AVL Tree

红黑树

B Tree

B+ Tree

Tree-00-概览

Tree-01-二叉树 Binary Tree

老马啸西风2020年10月17日大约 3 分钟

Tree-01-二叉树 Binary Tree

顾名思义，就是一个节点分出两个节点，称其为左右子节点；每个子节点又可以分出两个子节点，这样递归分叉，其形状很像一颗倒着的树。

二叉树限制了每个节点最多有两个子节点，没有子节点的节点称为叶子。

二叉树引导出很多名词概念，这里先不做系统介绍，遇到时再结合例子一一说明。

如下一个二叉树：

/*   A simple binary tree
 *        A ---------> A is root node
 *       / \
 *      /   \
 *     B     C
 *    /     / \
 *   /     /   \
 *   D     E    F ---> leaves: D, E, F
 *
 *       (1)      ---> Height: 3
 */