[数据结构·图] Floyd-Warshall 算法
弗洛伊德算法 (Floyd-Warshall) 详解1. 算法核心思想Floyd 算法本质上是 动态规划 (Dynamic Programming)。 核心问题：从顶点 $i$ 到顶点 $j$，如果我们允许经过一些中转点，最短路径是多少？ 1.1 状态定义我们定义 $dp[k][i][j]$ 为：“只允许使用节点 $1$ 到 $k$ 作为中转节点的情况下，从 $i$ 到 $j$ 的最短路径长度。” 1.2 状态转移方程（核心逻辑）当我们要计算允许使用节点 $1...k$ 的最短路时，我们有两种选择： 不经过节点 $k$：如果不使用 $k$ 做中转，那么最短路径就等于“只允许使用 $1...k-1$”时的路径。即：$dp[k-1][i][j]$。 经过节点 $k$：如果我们利用 $k$ 做中转，那么路径就变成了 $i \to k \to j$。这条路的长度是：$dp[k-1][i][k] + dp[k-1][k][j]$。 结论：我们要在这两者中取最小值。 dp[k][i][j] = \min(dp[k-1][i][j], \quad dp[k-1][i][k] +...
[数据结构·图] 最短路径问题详解
最短路径问题详解：Dijkstra 与 Floyd在图论中，最短路径问题主要分为两类： 单源最短路径 (Single-Source Shortest Path)：求从一个起点到其他所有点的最短路径。（代表：Dijkstra） 多源最短路径 (All-Pairs Shortest Path)：求任意两个点之间的最短路径。（代表：Floyd） 一、Dijkstra 算法 (单源最短路)适用场景：带权图（无向/有向），边权非负。核心思想：贪心策略 (Greedy) + 广度优先搜索 (BFS) 的变种。 1. 详细思路：作为“涟漪”扩散想象你站在起点 $S$，往地上倒了一桶水。水流会优先沿着阻力最小（边权最小）的路径蔓延。 我们维护一个集合 $S$（已确定最短路的点）和一个集合 $U$（未确定最短路的点）。 每次从 $U$ 中找出一个距离起点最近的点 $u$，把它加入 $S$。 然后以 $u$ 为跳板，去“松弛” (Relax) 它的邻居 $v$。 松弛操作：如果 dist[u] + weight(u, v) < dist[v]，说明通过 $u$ 到达 $v$...
[数据结构·图] 松弛操作
什么是“松弛操作” (Relaxation)？在图论的最短路径算法中，松弛是指：尝试通过一个中转点，来缩短到达某个目标点的路径长度。 如果发现通过中转点走更近，我们就更新（减小）目标点的最短距离估计值。这个过程就叫“松弛”。 1. 为什么叫“松弛”？（直观理解）这个术语来源于数学和物理学。我们可以用橡皮筋的例子来形象地理解。 橡皮筋类比想象一下： 图中的顶点是钉在木板上的钉子。 图中的边是连接钉子的橡皮筋。 路径长度可以理解为从起点拉到终点的绳子的“张力”或长度。 一开始，我们不知道从起点 $S$ 到终点 $B$ 的最短路，我们假设它无限远（或者用一条很长的绕远路的绳子连着），这时候绳子绷得很紧（估计值很大，即 dist[B] = ∞）。 当我们发现了一条从 $S$ 经过中间点 $A$ 再到 $B$ 的更短路径时，原本那根绕远路的紧绷绳子就可以松下来了，换成了一条更短的路线。路径的估计值变小了，压力变小了，所以叫“松弛”。 2. 数学定义与公式假设我们有两个顶点 $u$ 和 $v$，以及一条从 $u$ 到 $v$ 的边，权重为 $w(u,...
[数据结构·图] 邻接矩阵
图的存储结构：邻接矩阵 (Adjacency Matrix) 详解1. 邻接矩阵的基本概念邻接矩阵是表示图（Graph）中顶点之间相邻关系的一种方式。它使用一个二维数组（矩阵）来存储图中的边。 设图 $G = (V, E)$ 有 $n$ 个顶点，则其邻接矩阵是一个 $n \times n$ 的方阵 $A$。 1.1 数学定义 无权图： A[i][j] = \begin{cases} 1, & \text{若 } (v_i, v_j) \in E \text{ 或 } \in E \\ 0, & \text{其他} \end{cases} $1$ 表示两点之间有边。 $0$ 表示无边（或自身到自身）。 带权图（网）： A[i][j] = \begin{cases} w_{ij}, & \text{若 } (v_i, v_j) \in E \text{ 或 } \in E \\ \infty, & \text{其他 (且 } i \neq j \text{)} \\ 0, & i = j \end{cases} $w_{ij}$...
[数据结构·图] 邻接表
图的存储：邻接表 (Adjacency List) 详解1. 什么是邻接表？邻接表是图的一种链式存储结构。它克服了邻接矩阵在稀疏图（边数远小于顶点数平方）中浪费空间的缺点。 基本思想：对于图中的每个顶点 $v$，我们将所有与 $v$ 邻接的顶点记录在一个列表中。 通常使用数组（或 vector）来索引所有顶点。 数组的每个元素不再是一个单一的值，而是一个容器（链表或 vector），存储该顶点的所有出边。 内存模型示意假设有 4 个顶点，边为 $1\to2, 1\to3, 2\to4$。 AdjList (Array/Vector)+---+| 1 | -> [2] -> [3] (顶点1连接到2和3)+---+| 2 | -> [4] (顶点2连接到4)+---+| 3 | -> NULL (顶点3无出边)+---+| 4 | -> NULL (顶点4无出边)+---+ 2. 数据结构定义 (C++)在 C++ 中，最现代且方便的实现方式是使用 STL 的...
[数据结构·图] 图的基础
数据结构：图(Graph)图的基本概念一、图的定义图(Graph)是由顶点的有穷非空集合 $V(G)$ 和顶点之间边的集合 $E(G)$ 组成，通常表示为：$G=(V,E)$。 $V$ 是图 $G$ 中顶点的集合。 $E$ 是图 $G$ 中边的集合。 $|V|$ 表示顶点的个数，也称图的阶。 $|E|$ 表示边的条数。 注意：图不可以是空图，顶点集 $V$ 一定非空，但边集 $E$ 可以为空。 二、图的基本概念和术语 有向图：边是有向边（弧），记为 $$。$v$ 为弧尾，$w$ 为弧头。 无向图：边是无向边，记为 $(v, w)$ 或 $(w, v)$。 简单图：不存在重复边，不存在顶点到自身的边。 多重图：两个结点之间的边数多于一条，或允许顶点通过同一条边和自己关联。 完全图： 无向完全图：任意两个顶点之间都存在边，边数范围 $0$ 到 $n(n-1)/2$。 有向完全图：任意两个顶点之间都存在方向相反的两条弧，弧数范围 $0$ 到 $n(n-1)$。 子图：$G'=(V', E')$ 是 $G=(V, E)$ 的子图，若 $V'...
[数据结构·栈] 中缀表达式转后缀表达式
算法应用：使用栈实现中缀表达式转后缀表达式一、基本概念在继续之前，我们先明确两种表达式的定义： 中缀表达式 (Infix Expression)这是我们日常使用的标准算术表达式，操作符位于两个操作数的中间。例如：3 + 4 或 (a + b) * c 后缀表达式 (Postfix Expression / Reverse Polish Notation)也称为逆波兰表达式，操作符位于两个操作数的后面。后缀表达式在计算时不需要括号，并且计算逻辑非常简单，易于计算机处理。例如：3 4 + 或 a b + c * 转换的目标： 将人类易于阅读的中缀表达式，转换为计算机易于处理的后缀表达式。 二、转换算法思想转换过程的核心是使用一个栈来临时存放操作符。我们从左到右遍历中缀表达式的每一个字符（或token），根据字符类型执行不同的操作。 需要一个栈 s：用于存放操作符。 需要一个结果列表 postfix（或字符串）：用于存储最终的后缀表达式。 转换规则从左到右扫描中缀表达式，对于每个元素执行以下步骤： 遇到操作数（数字）： 直接将其追加到 postfix...
[数据结构·栈] 栈的应用：经典算法与例题解析
# 栈的应用：经典算法与例题解析 [[栈]]在理解了栈的基本概念和实现后，我们来看看它在算法中的一些经典应用。栈的“后进先出”（LIFO）特性使其成为处理具有递归结构或需要“暂存”和“回溯”状态问题的理想工具。 算法一：括号匹配1. 算法思想这是栈最经典的应用之一。给定一个只包含 (), [], {} 的字符串，判断字符串中的括号是否有效匹配。 有效匹配的条件： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 解决思路： 遍历字符串，当遇到一个左括号时，我们将其压入栈中。这相当于“暂存”了这个待匹配的左括号。 当遇到一个右括号时，我们需要检查栈顶的左括号是否与之匹配： 如果此时栈是空的，说明没有左括号与之对应，直接判定为无效。 如果栈不为空，取出（pop）栈顶元素，判断这两个括号是否是同一类型。 如果是，则匹配成功，继续遍历。 如果不是，则判定为无效。 遍历完整个字符串后，如果栈是空的，说明所有左括号都找到了对应的右括号，判定为有效。如果栈不为空，则说明有未被匹配的左括号，判定为无效。 2. 例题讲解：有效的括号...
[数据结构·栈] 核心应用与算法实战
数据结构复习：栈 (Stack) 的核心应用与算法实战1. 栈的基本概念回顾栈是一种后进先出 (LIFO, Last In First Out) 的线性数据结构。 主要操作：push (入栈), pop (出栈), top/peek (查看栈顶), isEmpty (判空)。 核心本质：栈主要用于处理具有完全包含关系或逆序处理的问题。 2. 栈的四大核心应用场景2.1 符号匹配与语法解析 (Symbol Matching)这是栈最经典的应用。编译器在检查代码语法（如括号匹配 { [ ( ) ] }）时，利用栈来确保每一个右括号都能匹配最近的一个未匹配的左括号。 原理：遇到左括号入栈，遇到右括号检查栈顶是否为对应的左括号，若是则出栈，否则报错。 2.2 表达式求值 (Expression Evaluation)计算机无法像人类一样直接理解中缀表达式（如 3 + 4 * 5），通常需要转化为后缀表达式 (逆波兰表达式, RPN) 或...
[数据结构·栈] 栈
数据结构：栈 (Stack)一、 什么是栈？栈是一种特殊的线性表，其所有插入和删除操作都限制在表的同一端进行。这个允许操作的端点被称为栈顶 (Top)，另一端则被称为栈底 (Bottom)。 栈的核心特点是 后进先出 (Last-In, First-Out)，简称 LIFO。 形象比喻：我们可以把栈想象成一个只有一个开口的狭窄死胡同，或者一摞盘子。 存入数据 (入栈/Push)：就像在胡同口放东西或者在最上面放一个新盘子。 取出数据 (出栈/Pop)：就像从胡同口取出东西或者从最上面拿走一个盘子。你总是最后放入的那个最先被取出。 二、 栈的逻辑结构从逻辑结构上讲，栈是一种线性结构。数据元素之间存在着“一对一”的关系。除了第一个元素（栈底）没有前驱，最后一个元素（栈顶）没有后继外，其他每个元素都有一个唯一的前驱和唯一的后继。 其特殊之处在于，它的操作受到了限制，数据只能从栈顶进出。 栈顶 (Top)：允许进行插入和删除操作的一端。 栈底 (Bottom)：固定不动，不允许操作的一端。 空栈 (Empty Stack)：不包含任何数据元素的栈。 三、...