集合与图论学习笔记09

算法 1 Dijkstra 算法

这个算法是用于解决单源最短路径问题的经典算法，适用于边权非负的图。下面给出两种实现方式：

朴素版，适用于稠密图，时间复杂度 \(O(V^2)\)

\[ \begin{array}{l} \textbf{Algorithm} \text{ Dijkstra-Naive}(G, w, s) \\ \hline \textbf{Input:} \text{ 图 } G=(V, E), \text{ 非负权值 } w, \text{ 源点 } s \\ \textbf{Output:} \text{ 最短距离数组 } d[], \text{ 前驱节点数组 } \pi[] \\ \\ \quad \color{gray}{// \text{ 1. 初始化 (Initialization)}} \\ \quad \textbf{for each } \text{vertex } v \in V \textbf{ do} \\ \quad \quad d[v] \leftarrow \infty \\ \quad \quad \pi[v] \leftarrow \text{NIL} \\ \quad \quad \text{visited}[v] \leftarrow \text{FALSE} \\ \quad \textbf{end for} \\ \quad d[s] \leftarrow 0 \\ \\ \quad \color{gray}{// \text{ 2. 主循环：执行 |V| 次}} \\ \quad \textbf{repeat } |V| \text{ times} \textbf{ do} \\ \quad \quad \color{gray}{// \text{ 步骤 A: 线性扫描寻找最小距离顶点}} \\ \quad \quad u \leftarrow \text{NULL} \\ \quad \quad min\_dist \leftarrow \infty \\ \quad \quad \textbf{for each } v \in V \textbf{ do} \\ \quad \quad \quad \textbf{if } \text{visited}[v] = \text{FALSE} \textbf{ and } d[v] < min\_dist \textbf{ then} \\ \quad \quad \quad \quad min\_dist \leftarrow d[v] \\ \quad \quad \quad \quad u \leftarrow v \\ \quad \quad \quad \textbf{end if} \\ \quad \quad \textbf{end for} \\ \\ \quad \quad \textbf{if } u = \text{NULL} \textbf{ or } d[u] = \infty \textbf{ then} \\ \quad \quad \quad \textbf{break} \quad \color{gray}{// \text{ 剩余节点均不可达}} \\ \quad \quad \textbf{end if} \\ \\ \quad \quad \text{visited}[u] \leftarrow \text{TRUE} \\ \\ \quad \quad \textbf{for each } v \in Adj[u] \textbf{ do} \\ \quad \quad \quad \textbf{if } \text{visited}[v] = \text{FALSE} \textbf{ and } d[v] > d[u] + w(u, v) \textbf{ then} \\ \quad \quad \quad \quad d[v] \leftarrow d[u] + w(u, v) \\ \quad \quad \quad \quad \pi[v] \leftarrow u \\ \quad \quad \quad \textbf{end if} \\ \quad \quad \textbf{end for} \\ \quad \textbf{end repeat} \\ \\ \quad \textbf{return } d, \pi \end{array} \]

优先队列版，适用于稀疏图，时间复杂度 \(O((V + E) \log V)\) \[ \begin{array}{l} \textbf{Algorithm} \text{ Dijkstra-PriorityQueue}(G, w, s) \\ \hline \textbf{Input:} \text{ 图 } G=(V, E), \text{ 非负权值 } w, \text{ 源点 } s \\ \textbf{Output:} \text{ 最短距离数组 } d[], \text{ 前驱节点数组 } \pi[] \\ \\ \quad \color{gray}{// \text{ 1. 初始化 (Initialization)}} \\ \quad \textbf{for each } \text{vertex } v \in V \textbf{ do} \\ \quad \quad d[v] \leftarrow \infty \\ \quad \quad \pi[v] \leftarrow \text{NIL} \\ \quad \textbf{end for} \\ \quad d[s] \leftarrow 0 \\ \\ \quad \color{gray}{// \text{ 2. 构建优先队列 (Build Queue)}} \\ \quad S \leftarrow \emptyset \quad \color{gray}{// \text{ 已确定最短路的顶点集合}} \\ \quad Q \leftarrow V \quad \color{gray}{// \text{ 包含所有顶点的最小优先队列，以 } d \text{ 值排序}} \\ \\ \quad \color{gray}{// \text{ 3. 主循环 (Main Loop)}} \\ \quad \textbf{while } Q \neq \emptyset \textbf{ do} \\ \quad \quad u \leftarrow \text{EXTRACT-MIN}(Q) \quad \color{gray}{// \text{ 取出 d 值最小的顶点}} \\ \quad \quad S \leftarrow S \cup \{u\} \\ \\ \quad \quad \textbf{for each } v \in Adj[u] \textbf{ do} \quad \color{gray}{// \text{ 遍历邻居}} \\ \quad \quad \quad \textbf{if } d[v] > d[u] + w(u, v) \textbf{ then} \\ \quad \quad \quad \quad d[v] \leftarrow d[u] + w(u, v) \\ \quad \quad \quad \quad \pi[v] \leftarrow u \\ \quad \quad \quad \quad \text{DECREASE-KEY}(Q, v, d[v]) \quad \color{gray}{// \text{ 更新队列中 v 的优先级}} \\ \quad \quad \quad \textbf{end if} \\ \quad \quad \textbf{end for} \\ \quad \textbf{end while} \\ \\ \quad \textbf{return } d, \pi \end{array} \]

算法 2 Kruskal 算法

这个算法是用于寻找最小生成树的经典算法，基于贪心策略和并查集数据结构

它在稀疏图中表现较好，如果图不连通，则可以找到最小生成森林

时间复杂度为 \(O(E \log E)\)，其中 \(E\) 是图的边数

下面是 Kruskal 算法的伪代码表示： \[ \begin{array}{l} \textbf{Algorithm} \text{ Kruskal}(G, w) \\ \hline \textbf{Input:} \text{ 连通无向图 } G=(V, E), \text{ 边权 } w \\ \textbf{Output:} \text{ 最小生成树的边集 } A \\ \\ \quad \color{gray}{// \text{ 1. 初始化 (Initialization)}} \\ \quad A \leftarrow \emptyset \quad \color{gray}{// \text{ A 用于存储最终生成的 MST 边}} \\ \\ \quad \color{gray}{// \text{ 2. 初始化并查集 (Setup Disjoint Sets)}} \\ \quad \textbf{for each } \text{vertex } v \in V \textbf{ do} \\ \quad \quad \text{MAKE-SET}(v) \quad \color{gray}{// \text{ 每个顶点初始化为一个独立的集合}} \\ \quad \textbf{end for} \\ \\ \quad \color{gray}{// \text{ 3. 边排序 (Sort Edges)}} \\ \quad \text{Sort the edges of } E \text{ into non-decreasing order by weight } w \\ \\ \quad \color{gray}{// \text{ 4. 主循环 (Main Loop)}} \\ \quad \textbf{for each } \text{edge } (u, v) \in E \text{ (taken in sorted order)} \textbf{ do} \\ \quad \quad \color{gray}{// \text{ 判断 u 和 v 是否属于同一个连通分量}} \\ \quad \quad \textbf{if } \text{FIND-SET}(u) \neq \text{FIND-SET}(v) \textbf{ then} \\ \quad \quad \quad A \leftarrow A \cup \{(u, v)\} \quad \color{gray}{// \text{ 将该边加入 MST}} \\ \quad \quad \quad \text{UNION}(u, v) \quad \color{gray}{// \text{ 合并 u 和 v 所在的集合}} \\ \quad \quad \textbf{end if} \\ \quad \textbf{end for} \\ \\ \quad \textbf{return } A \end{array} \]

算法 3 Huffman 算法

这个算法是用于构建最优前缀编码的经典算法，广泛应用于数据压缩领域

时间复杂度为 \(O(n \log n)\)，其中 \(n\) 是字符集的大小

下面是 Huffman 算法的伪代码表示： \[ \begin{array}{l} \textbf{Algorithm} \text{ Huffman}(C) \\ \hline \textbf{Input:} \text{ 字符集 } C, \text{ 其中每个字符 } c \in C \text{ 具有定义的频率 } c.freq \\ \textbf{Output:} \text{ 哈夫曼树的根节点 (The root of the Huffman Tree)} \\ \\ \quad \color{gray}{// \text{ 1. 初始化 (Initialization)}} \\ \quad n \leftarrow |C| \\ \quad Q \leftarrow C \quad \color{gray}{// \text{ 将 C 中所有字符构建为最小优先队列，键值为 freq}} \\ \\ \quad \color{gray}{// \text{ 2. 主循环：执行 n-1 次合并}} \\ \quad \textbf{for } i \leftarrow 1 \textbf{ to } n - 1 \textbf{ do} \\ \quad \quad \color{gray}{// \text{ 分配一个新的内部节点 z}} \\ \quad \quad z \leftarrow \text{ALLOCATE-NODE}() \\ \\ \quad \quad \color{gray}{// \text{ 从 Q 中取出频率最小的两个节点 x 和 y}} \\ \quad \quad x \leftarrow \text{EXTRACT-MIN}(Q) \\ \quad \quad y \leftarrow \text{EXTRACT-MIN}(Q) \\ \\ \quad \quad \color{gray}{// \text{ 将 x 和 y 设为 z 的左右子节点}} \\ \quad \quad z.left \leftarrow x \\ \quad \quad z.right \leftarrow y \\ \\ \quad \quad \color{gray}{// \text{ 新节点 z 的频率为两个子节点频率之和}} \\ \quad \quad z.freq \leftarrow x.freq + y.freq \\ \\ \quad \quad \color{gray}{// \text{ 将新生成的节点 z 插回优先队列}} \\ \quad \quad \text{INSERT}(Q, z) \\ \quad \textbf{end for} \\ \\ \quad \color{gray}{// \text{ 队列中剩下的最后一个节点即为树根}} \\ \quad \textbf{return } \text{EXTRACT-MIN}(Q) \end{array} \]

算法 4 Fleury 算法

这个算法用于寻找欧拉回路或欧拉路径

时间复杂度为 \(O(E^2)\)，其中 \(E\) 是图的边数 \[ \begin{array}{l} \textbf{Algorithm} \text{ Fleury}(G) \\ \hline \textbf{Input:} \text{ 无向连通图 } G=(V, E) \\ \textbf{Output:} \text{ 欧拉路径或欧拉回路序列 } P \\ \\ \quad \color{gray}{// \text{ 1. 预检查与起点选择 (Pre-check \& Start Node)}} \\ \quad \text{Calculate degree for all vertices.} \\ \quad \text{odd\_vertices} \leftarrow \{ v \in V \mid \text{degree}(v) \text{ is odd} \} \\ \\ \quad \textbf{if } |\text{odd\_vertices}| \neq 0 \textbf{ and } |\text{odd\_vertices}| \neq 2 \textbf{ then} \\ \quad \quad \textbf{return } \text{"No Eulerian Path exists"} \\ \quad \textbf{end if} \\ \\ \quad \color{gray}{// \text{ 如果有奇度顶点，必须从其中一个开始；否则从任意非孤立点开始}} \\ \quad \textbf{if } |\text{odd\_vertices}| = 2 \textbf{ then} \\ \quad \quad u \leftarrow \text{odd\_vertices}[0] \\ \quad \textbf{else} \\ \quad \quad u \leftarrow \text{any vertex with degree} > 0 \\ \quad \textbf{end if} \\ \\ \quad \color{gray}{// \text{ 2. 主循环 (Main Loop)}} \\ \quad P \leftarrow [u] \quad \color{gray}{// \text{ 路径序列初始化}} \\ \\ \quad \textbf{while } \text{degree}(u) > 0 \textbf{ do} \\ \quad \quad \text{chosen\_edge} \leftarrow \text{NULL} \\ \\ \quad \quad \textbf{for each } v \in Adj[u] \textbf{ do} \\ \quad \quad \quad \color{gray}{// \text{ 规则 1: 如果只有这一条边可选，则必须选它}} \\ \quad \quad \quad \textbf{if } |Adj[u]| = 1 \textbf{ then} \\ \quad \quad \quad \quad \text{chosen\_edge} \leftarrow (u, v) \\ \quad \quad \quad \quad \textbf{break} \\ \quad \quad \quad \textbf{end if} \\ \\ \quad \quad \quad \color{gray}{// \text{ 规则 2: 如果该边不是桥，则选它}} \\ \quad \quad \quad \textbf{if } \text{IS-BRIDGE}(G, u, v) = \text{FALSE} \textbf{ then} \\ \quad \quad \quad \quad \text{chosen\_edge} \leftarrow (u, v) \\ \quad \quad \quad \quad \textbf{break} \\ \quad \quad \quad \textbf{end if} \\ \quad \quad \textbf{end for} \\ \\ \quad \quad \color{gray}{// \text{ 执行移动}} \\ \quad \quad v \leftarrow \text{destination of chosen\_edge} \\ \quad \quad P.\text{append}(v) \\ \quad \quad \text{REMOVE-EDGE}(G, u, v) \quad \color{gray}{// \text{ 从图中物理删除该边}} \\ \quad \quad u \leftarrow v \\ \quad \textbf{end while} \\ \\ \quad \textbf{return } P \end{array} \]

算法 5 Hierholzer 算法

这个算法同样用于寻找欧拉回路或欧拉路径，但效率更高，时间复杂度为 \(O(E)\)，其中 \(E\) 是图的边数

伪代码： \[ \begin{array}{l} \textbf{Algorithm} \text{ Hierholzer}(G, s) \\ \hline \textbf{Input:} \text{ 有向/无向图 } G=(V, E), \text{ 起点 } s \\ \textbf{Output:} \text{ 欧拉回路序列 } C \\ \\ \quad \color{gray}{// \text{ 1. 初始化数据结构}} \\ \quad \text{Stack } S \leftarrow \emptyset \\ \quad \text{List } C \leftarrow \emptyset \quad \color{gray}{// \text{ 用于存储结果回路}} \\ \quad S.\text{push}(s) \\ \\ \quad \color{gray}{// \text{ 2. 主循环：直到栈为空}} \\ \quad \textbf{while } S \neq \emptyset \textbf{ do} \\ \quad \quad v \leftarrow S.\text{top()} \quad \color{gray}{// \text{ 查看栈顶元素，暂不出栈}} \\ \\ \quad \quad \color{gray}{// \text{ 如果 v 还有相邻边未访问}} \\ \quad \quad \textbf{if } |Adj[v]| > 0 \textbf{ then} \\ \quad \quad \quad \color{gray}{// \text{ 取出并删除一条边 (v, u)}} \\ \quad \quad \quad u \leftarrow Adj[v].\text{extract\_any}() \\ \quad \quad \quad \text{REMOVE-EDGE}(G, v, u) \quad \color{gray}{// \text{ 对于无向图需删双向，有向图删单向}} \\ \quad \quad \quad S.\text{push}(u) \quad \color{gray}{// \text{以此为新起点继续深搜}} \\ \quad \quad \textbf{else} \\ \quad \quad \quad \color{gray}{// \text{ v 无路可走，说明 v 是某个圈的终点}} \\ \quad \quad \quad C.\text{append}(S.\text{pop()}) \quad \color{gray}{// \text{ 弹出 v 并加入结果集}} \\ \quad \quad \textbf{end if} \\ \quad \textbf{end while} \\ \\ \quad \color{gray}{// \text{ 3. 结果处理}} \\ \quad \textbf{return } \text{REVERSE}(C) \quad \color{gray}{// \text{ 逆序输出即为正确路径}} \end{array} \]

算法 6 Prim 算法

这个算法用于在加权连通无向图中寻找最小生成树

时间复杂度为 \(O(E + V \log V)\)，其中 \(E\) 是图的边数，\(V\) 是图的顶点数 \[ \begin{array}{l} \textbf{Algorithm} \text{ Prim}(G, w, r) \\ \hline \textbf{Input:} \text{ 连通无向图 } G=(V, E), \text{ 边权 } w, \text{ 根节点 } r \\ \textbf{Output:} \text{ 前驱节点数组 } \pi \text{ (定义了 MST 的边)} \\ \\ \quad \color{gray}{// \text{ 1. 初始化 (Initialization)}} \\ \quad \textbf{for each } u \in V \textbf{ do} \\ \quad \quad \text{key}[u] \leftarrow \infty \quad \color{gray}{// \text{ key[u] 表示 u 连接到 MST 的最小边权}} \\ \quad \quad \pi[u] \leftarrow \text{NIL} \quad \color{gray}{// \text{ MST 中的父节点}} \\ \quad \textbf{end for} \\ \quad \text{key}[r] \leftarrow 0 \\ \\ \quad \color{gray}{// \text{ 2. 构建优先队列}} \\ \quad Q \leftarrow V \quad \color{gray}{// \text{ Q 包含所有顶点，以 key 值排序的最小优先队列}} \\ \\ \quad \color{gray}{// \text{ 3. 主循环 (Main Loop)}} \\ \quad \textbf{while } Q \neq \emptyset \textbf{ do} \\ \quad \quad u \leftarrow \text{EXTRACT-MIN}(Q) \quad \color{gray}{// \text{ 取出离 MST 最近的顶点}} \\ \\ \quad \quad \textbf{for each } v \in Adj[u] \textbf{ do} \\ \quad \quad \quad \color{gray}{// \text{ 如果 v 还在队列中（未加入 MST），且连接边权小于当前记录的 key}} \\ \quad \quad \quad \textbf{if } v \in Q \textbf{ and } w(u, v) < \text{key}[v] \textbf{ then} \\ \quad \quad \quad \quad \pi[v] \leftarrow u \\ \quad \quad \quad \quad \text{key}[v] \leftarrow w(u, v) \quad \color{gray}{// \text{ 【关键】更新最小边权，不是路径和}} \\ \quad \quad \quad \quad \text{DECREASE-KEY}(Q, v, w(u, v)) \\ \quad \quad \quad \textbf{end if} \\ \quad \quad \textbf{end for} \\ \quad \textbf{end while} \\ \\ \quad \textbf{return } \pi \end{array} \]

算法 7 Borůvka(Sollin) 算法

这个算法用于寻找加权连通无向图的最小生成树

这个算法的特点是可并行性高，适用于分布式计算环境

时间复杂度为 \(O(E \log V)\)，其中 \(E\) 是图的边数，\(V\) 是图的顶点数 \[ \begin{array}{l} \textbf{Algorithm} \text{ Borůvka}(G, w) \\ \hline \textbf{Input:} \text{ 连通无向图 } G=(V, E), \text{ 边权 } w \\ \textbf{Output:} \text{ 最小生成树的边集 } T \\ \\ \quad \color{gray}{// \text{ 1. 初始化}} \\ \quad T \leftarrow \emptyset \\ \quad \text{num\_trees} \leftarrow |V| \\ \quad \textbf{for each } v \in V \textbf{ do } \text{MAKE-SET}(v) \\ \\ \quad \color{gray}{// \text{ 2. 主循环：直到只剩下一个连通分量}} \\ \quad \textbf{while } \text{num\_trees} > 1 \textbf{ do} \\ \quad \quad \color{gray}{// \text{ 初始化最小边数组：cheapest[c] 存储连通分量 c 目前找到的最小出边}} \\ \quad \quad \textbf{for each } v \in V \textbf{ do } \text{cheapest}[v] \leftarrow \text{NIL} \\ \\ \quad \quad \color{gray}{// \text{ 步骤 A: 遍历所有边，更新每个分量的最小出边}} \\ \quad \quad \textbf{for each } (u, v) \in E \textbf{ do} \\ \quad \quad \quad \text{set\_u} \leftarrow \text{FIND-SET}(u) \\ \quad \quad \quad \text{set\_v} \leftarrow \text{FIND-SET}(v) \\ \\ \quad \quad \quad \textbf{if } \text{set\_u} \neq \text{set\_v} \textbf{ then} \\ \quad \quad \quad \quad \color{gray}{// \text{ 检查是否优于 set\_u 当前记录的最小边}} \\ \quad \quad \quad \quad \textbf{if } \text{cheapest}[\text{set\_u}] = \text{NIL} \textbf{ or } w(u, v) < w(\text{cheapest}[\text{set\_u}]) \textbf{ then} \\ \quad \quad \quad \quad \quad \text{cheapest}[\text{set\_u}] \leftarrow (u, v) \\ \quad \quad \quad \quad \textbf{end if} \\ \quad \quad \quad \quad \color{gray}{// \text{ 检查是否优于 set\_v 当前记录的最小边}} \\ \quad \quad \quad \quad \textbf{if } \text{cheapest}[\text{set\_v}] = \text{NIL} \textbf{ or } w(u, v) < w(\text{cheapest}[\text{set\_v}]) \textbf{ then} \\ \quad \quad \quad \quad \quad \text{cheapest}[\text{set\_v}] \leftarrow (u, v) \\ \quad \quad \quad \quad \textbf{end if} \\ \quad \quad \quad \textbf{end if} \\ \quad \quad \textbf{end for} \\ \\ \quad \quad \color{gray}{// \text{ 步骤 B: 依据计算出的最小边进行合并}} \\ \quad \quad \text{merged\_any} \leftarrow \text{FALSE} \\ \quad \quad \textbf{for each } v \in V \textbf{ do} \\ \quad \quad \quad \color{gray}{// \text{ 只处理集合的代表元素}} \\ \quad \quad \quad \textbf{if } v = \text{FIND-SET}(v) \textbf{ and } \text{cheapest}[v] \neq \text{NIL} \textbf{ then} \\ \quad \quad \quad \quad (x, y) \leftarrow \text{cheapest}[v] \\ \quad \quad \quad \quad \text{root\_x} \leftarrow \text{FIND-SET}(x) \\ \quad \quad \quad \quad \text{root\_y} \leftarrow \text{FIND-SET}(y) \\ \\ \quad \quad \quad \quad \textbf{if } \text{root\_x} \neq \text{root\_y} \textbf{ then} \\ \quad \quad \quad \quad \quad T \leftarrow T \cup \{(x, y)\} \\ \quad \quad \quad \quad \quad \text{UNION}(\text{root\_x}, \text{root\_y}) \\ \quad \quad \quad \quad \quad \text{num\_trees} \leftarrow \text{num\_trees} - 1 \\ \quad \quad \quad \quad \quad \text{merged\_any} \leftarrow \text{TRUE} \\ \quad \quad \quad \quad \textbf{end if} \\ \quad \quad \quad \textbf{end if} \\ \quad \quad \textbf{end for} \\ \\ \quad \quad \color{gray}{// \text{ 安全检查：若一轮未合并任何边，说明图不连通}} \\ \quad \quad \textbf{if } \text{merged\_any} = \text{FALSE} \textbf{ then break} \\ \quad \textbf{end while} \\ \\ \quad \textbf{return } T \end{array} \]