一、图的基本概念

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

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

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

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

下面详细分析：

---

一、DFS 和 BFS 的核心区别

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

一、图连通性的基本概念

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

• 节点可达（Reachability）：如果存在一条从节点 A 到节点 B 的路径，则称 A 可达 B。

• 连通图（Connected Graph）：

  • 无向图：如果任意两个节点之间都有路径，称图是连通的。

  • 有向图：

    • 强连通（Strongly Connected）：每对节点 u,v 都有路径 u→v 和 v→u。
    • 弱连通（Weakly Connected）：将有向图看作无向图后连通，则称弱连通。

1️⃣ 并查集的本质

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

• 用途：

  • 判断图中两个节点是否连通
  • 求连通分量个数
  • 处理网络、社交关系、群体合并等问题

• 核心思想：

  • 每个集合有一个“代表元素”（root）
  • 每个元素只保存指向父节点的指针
  • 查找元素的根节点可以判断是否属于同一个集合
  • 合并两个集合就是把一个集合的根挂到另一个根上

1️⃣ 堆的概念

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

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

特点：

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

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。

它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(lg(n)) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。

用途和好处

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。

伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊 O(log n) 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。

它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。

核心思想

考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。

ps: 这个思想实际上非常的简单，也非常的实用。我们以前实现的 LFU 的思想是类似的。

2–3树是一种树型数据结构，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。

2–3树由约翰·霍普克洛夫特于1970年发明。

2–3树和AA树是等距同构的，意味着它们是同一种数据结构。

换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。

2–3树是平衡树，意味着右边，左边，中间的子树的元素数量都是相同或接近的。

定义

（1）2-3 树要么为空要么具有以下性质：

在1970年，Bayer＆McCreight发表的论文《ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES》（大型有序索引的组织和维护）中提出了一种新的数据结构来维护大型索引，这种数据结构在论文中称为B Tree。

B树的定义

h：代表树的高度，k 是个自然数，一个B树要么是空的，要么满足以下条件：

1. 所有叶子节点到根节点的路径长度相同，即具有相同的高度；（树是平衡的）

2. 每个非叶子和根节点（即内部节点）至少有 k+1 个孩子节点，根至少有 2 个孩子；（这是关键的部分，因为节点都是分裂而来的，而每次分裂得到的节点至少有 k 个元素，也就有 k+1 个孩子；但根节点在分裂后可能只有一个元素，因为不需要向上融合，中间元素作为新的根节点，因此最少有两个孩子。而叶子节点没有孩子。）

3. 每个节点最多有 2k+1 个孩子节点。（规定了节点的最大容量）

4. 每个节点内的键都是递增的

B+ 树是应文件系统所需而产生的一种B Tree的变形树。

描述

B Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B Tree相比，B+Tree有以下不同点：

每个节点的指针上限为2d而不是2d+1。

内节点不存储data，只存储key；叶子节点不存储指针。

图3是一个简单的B+Tree示意。