跳至主要內容

算法与数据结构（五）：图算法与字符串算法

星辰逐梦2026/6/3大约 14 分钟JAVAjava 算法

算法与数据结构（五）：图算法与字符串算法

导语：本篇收尾两个"块状"专题。图论部分覆盖存储结构、DFS/BFS、拓扑排序、最短路与最小生成树；字符串部分覆盖 KMP、最长回文子串、滚动哈希与高频题型。算法均给出可运行的 Java 实现。共 11 题。

一、图的存储与遍历

1. 图的存储方式有哪些？邻接矩阵与邻接表如何选择？

答： 两种主流存储方式：

维度邻接矩阵 int[V][V]邻接表 List<List<Integer>>
空间O(V²)O(V + E)
判断 u-v 是否有边O(1)O(度(u))
遍历某点的所有邻居O(V)（要扫整行）O(度(u))
加边/删边O(1)加 O(1)、删 O(度)
适用稠密图、需要频繁判断两点是否相邻稀疏图（绝大多数真实场景）

邻接表的 Java 写法：

int n = 5;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

int[][] edges = {{0, 1}, {1, 2}, {2, 3}};
for (int[] e : edges) {
    graph.get(e[0]).add(e[1]);      // 有向边 u -> v
    graph.get(e[1]).add(e[0]);      // 无向图再加一条反向边
}

带权图用 List<List<int[]>>（每个元素是 {邻居, 权值}），边集数组 int[][] edges = {u, v, w} 则适合 Kruskal 这类"按边处理"的算法。

工程选择：绝大多数场景选邻接表——真实图几乎都是稀疏的（E 远小于 V²），用矩阵会浪费大量空间。只有当图很稠密、或算法需要频繁做 O(1) 邻接判断（如 Floyd）时，矩阵才更合适。

2. 图的 DFS 与 BFS 如何实现？

答：

// 1. DFS —— 递归版（最直观）
public void dfs(List<List<Integer>> graph, int u, boolean[] visited) {
    visited[u] = true;
    // 处理节点 u
    for (int v : graph.get(u)) {
        if (!visited[v]) dfs(graph, v, visited);
    }
}

// 2. DFS —— 迭代版（用显式栈，避免深图递归爆栈）
public void dfsIterative(List<List<Integer>> graph, int start, boolean[] visited) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;      // 注意：出栈时可能已访问过（入栈时未标记）
        visited[u] = true;
        // 处理节点 u
        for (int v : graph.get(u)) {
            if (!visited[v]) stack.push(v);
        }
    }
}

// 3. BFS —— 队列 + 层序
public void bfs(List<List<Integer>> graph, int start, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;             // 关键：BFS 在【入队时】就标记
    while (!queue.isEmpty()) {
        int u = queue.poll();
        // 处理节点 u（此处是当前层）
        for (int v : graph.get(u)) {
            if (!visited[v]) {
                visited[v] = true;     // 入队即标记，防止同一节点被重复入队
                queue.offer(v);
            }
        }
    }
}

最容易错的点：BFS 必须在"入队时"标记 visited，而不是"出队时"。若在出队时才标记，同一个节点可能被多个邻居重复入队，队列规模会爆炸（最坏到指数级）；DFS 递归版进入时标记即可，但迭代版若在入栈时无法标记，就必须在出栈时判重（见上面代码的 if (visited[u]) continue;）。

3. DFS 与 BFS 分别适用什么场景？

答：

维度DFSBFS
实现递归 / 栈队列
空间O(h)（h 为路径最大深度）O(w)（w 为最大层宽）
是否保证最短路不保证无权图保证最短
适合穷举所有方案、连通性判断、找所有路径、回溯、拓扑排序最短路径（无权）、层序遍历、辐射扩散、社交网络 N 度人脉
风险深图/长链可能栈溢出宽度极大时内存占用高（如需存整层）

选型口诀：

  • "求最短/最少步数" → BFS（例：腐烂的橘子、迷宫最短路径、单词接龙）；
  • "求所有方案/是否存在某路径" → DFS（例：岛屿数量、全排列、组合总和、括号生成）；
  • 两者都要"记录访问状态"防重复。BFS 用队列层级天然记录距离，DFS 需要额外传参记录当前深度（若要最短则需搜索完所有路径再比较，效率差）。

二、图的高级算法

4. 什么是拓扑排序？如何实现？

答： 拓扑排序只适用于有向无环图（DAG），输出一个线性序列，使每条边 u → v 中 u 都排在 v 前面（即满足所有依赖关系）。

两大用途：① 判断有向图是否有环（排序结果长度 < 顶点数 ⇒ 有环）；② 解决依赖顺序问题（编译顺序、课程安排、任务调度）。

实现一：Kahn 算法（BFS，入度法）——推荐

public int[] topologicalSort(int n, List<List<Integer>> graph) {
    int[] indegree = new int[n];
    for (int u = 0; u < n; u++) {
        for (int v : graph.get(u)) indegree[v]++;        // 统计每个点的入度
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) queue.offer(i);             // 入度为 0 的点可先执行
    }

    int[] order = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[idx++] = u;                                 // 输出
        for (int v : graph.get(u)) {
            if (--indegree[v] == 0) queue.offer(v);       // 入度降为 0 → 解锁
        }
    }
    // 输出节点数不足 n ⇒ 存在环，无拓扑序
    return idx == n ? order : new int[0];
}

实现二：DFS 后序逆序
对图做 DFS，记录后序遍历（离开节点时加入列表），最后把列表逆序即为拓扑序。若 DFS 中遇到"正在访问中"的节点，说明存在环。

复杂度：Kahn 算法 O(V + E)，因为每条边与每个点各处理一次。

注意：拓扑序通常不唯一（入度同时为 0 的多个点顺序任意）；只有全序图（任意两点间都有路径）才有唯一拓扑序。

5. Dijkstra 算法如何实现？

答： Dijkstra 解决非负权图的单源最短路径（一个起点到所有点的最短距离），是贪心算法的代表：每次从未确定的点中选出"当前距离最小"的点，确定其最短距离，再用它松弛（relax）邻居。

朴素版：每次线性扫描找最小值 → O(V²)，适合稠密图。
优先队列版：用小顶堆取最小值 → O((V + E) log V)。

import java.util.Arrays;
import java.util.PriorityQueue;

// graph.get(u) 中每个元素是 {邻居, 边权}
public int[] dijkstra(int n, List<List<int[]>> graph, int start) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 小顶堆
    pq.offer(new int[]{start, 0});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d > dist[u]) continue;            // 过期条目，跳过（惰性删除）

        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {      // 松弛操作
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;   // dist[i] 即 start → i 的最短距离
}

为什么不能有负权边：Dijkstra 的核心前提是"一旦某个点被确定为最短，之后不会再有更短的路径"。负权边会破坏这个单调性——后续可能通过负边绕回来得到更短的距离，导致已确定的结果错误。含负权时必须用 Bellman-Ford。

if (d > dist[u]) continue; 的作用：同一个节点可能被多次入堆（每次距离更优都会 offer），这里是"惰性删除"——跳过已过期的旧条目，避免重复处理。

6. Floyd 与 Bellman-Ford 的区别与适用场景？

答： 三大最短路算法对比：

算法类型时间复杂度负权边检测负环适用
Dijkstra单源O((V+E) log V) / O(V²)✗✗非负权图（最常见）
Bellman-Ford单源O(V × E)✓✓含负权边 / 需检测负环
Floyd多源（任意两点）O(V³)✓通过对角线判顶点数少、需要全源距离

Bellman-Ford 的两个特点：

  • 对所有边做 V - 1 轮松弛（V - 1 是"最长简单路径的边数"），第 V 轮若还能松弛成功，说明存在负环；
  • 常用队列优化版即 SPFA，但 SPFA 最坏仍退化到 O(V × E)。

Floyd（动态规划，多源最短路）：

public static final int INF = Integer.MAX_VALUE / 2;   // 防止相加溢出

public void floyd(int[][] dist) {          // dist[i][j] 初始为 i→j 的边权（无边为 INF，自身为 0）
    int n = dist.length;
    for (int k = 0; k < n; k++) {          // k 必须是最外层：表示"允许经过 k 中转"
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

k 为什么必须放最外层？ Floyd 的状态定义是 dp[k][i][j]——"只允许用前 k 个点作为中转"时 i → j 的最短距离。k 是"阶段"，必须逐层推进；若把 k 放内层，就会用到"当前阶段尚未完成的中间结果"，逻辑就错了。这是 Floyd 最高频的考点。

INF 取 Integer.MAX_VALUE / 2 是为了避免 dist[i][k] + dist[k][j] 相加时整数溢出变负数。

7. 最小生成树：Prim 与 Kruskal 的区别？

答： 最小生成树（MST） 是在连通无向带权图中选出 V - 1 条边，使所有点连通且总权值最小。

算法核心思想时间复杂度适用
Prim从任一顶点出发，每次把"离当前生成树最近"的点及其边加入（贪心 + 优先队列）O(E log V)稠密图
Kruskal把所有边按权值升序排序，依次尝试加入"不与已有边构成环"的边（并查集判环）O(E log E)稀疏图

Kruskal 的 Java 实现（依赖并查集，见第二篇第 16 题）：

// edges 中每个元素是 {u, v, w}
public int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);   // 1. 按边权升序
    UnionFind uf = new UnionFind(n);
    int total = 0, used = 0;

    for (int[] e : edges) {
        if (uf.union(e[0], e[1])) {              // 2. 两端不在同一集合 → 不构成环，可加入
            total += e[2];
            if (++used == n - 1) break;          // 3. 已有 n-1 条边即完成
        }
    }
    return used == n - 1 ? total : -1;           // 边数不足说明图不连通
}

选型口诀："稠密用 Prim，稀疏用 Kruskal"。直观理解——Kruskal 的复杂度由边数决定（要排序所有边），Prim 由顶点数与边数共同决定；边多的时候 Kruskal 的排序开销就显现出来了。

共性：两者都是贪心算法，且都正确（MST 的割性质与环性质保证）；MST 不唯一（存在等权边时），但最小总权值唯一。

三、字符串算法

8. KMP 算法的原理是什么？如何实现？

答： 朴素匹配的问题在于：失配时主串指针 i 要回退，导致最坏 O(n × m)。

KMP 的核心思想：失配时主串指针 i 永不回退，只让模式串滑动——滑动的距离由 next 数组（最长相等前后缀）决定。

next 数组的含义：next[i] = 模式串子串 pattern[0..i] 的最长相等前后缀长度。它的作用是：当在位置 j 失配时，说明 pattern[0..j-1] 已经匹配成功，而该前缀的"最长相等前后缀"可以直接复用，于是把 j 回退到 next[j-1] 继续比较，无需重头再来。

public class KMP {

    /** 构建 next 数组：next[i] = pattern[0..i] 的最长相等前后缀长度 */
    private int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        int len = 0;                            // 当前最长相等前后缀长度
        for (int i = 1; i < m; i++) {           // 注意从 1 开始（next[0] = 0）
            while (len > 0 && pattern.charAt(i) != pattern.charAt(len)) {
                len = next[len - 1];            // 失配 → 回退到更短的前缀继续尝试
            }
            if (pattern.charAt(i) == pattern.charAt(len)) len++;
            next[i] = len;
        }
        return next;
    }

    /** 返回 pattern 在 text 中首次出现的下标，未找到返回 -1 */
    public int indexOf(String text, String pattern) {
        if (pattern.isEmpty()) return 0;
        int[] next = buildNext(pattern);
        int j = 0;                              // 模式串已匹配的长度
        for (int i = 0; i < text.length(); i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];                // 关键：主串指针 i 不回退，只滑动模式串
            }
            if (text.charAt(i) == pattern.charAt(j)) j++;
            if (j == pattern.length()) {
                return i - j + 1;               // 匹配完成，返回起始下标
            }
        }
        return -1;
    }
}

复杂度：构建 next 为 O(m)，匹配为 O(n)，总计 O(n + m)；空间 O(m)。

理解要点：next 数组本质是模式串的自我匹配——它把"模式串自身的前后缀信息"预处理出来，从而在失配时跳过那些"必然不可能匹配"的位置。

同类思想：KMP 的 next 数组与 AC 自动机（多模式串匹配）、Z 函数、Manacher 都属于"利用字符串自身的周期性/对称性做预处理"的家族。

9. 如何求最长回文子串？

答： 三种解法，面试首选中心扩展（好写、O(n²) 可接受）：

// 中心扩展法：以每个字符（奇数长度）和每两个相邻字符之间（偶数长度）为中心向两侧扩
public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) return s;
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);       // 奇数长度回文，如 "aba"
        int len2 = expandAroundCenter(s, i, i + 1);   // 偶数长度回文，如 "abba"
        int len = Math.max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;                // 由中心与长度反推起点
        }
    }
    return s.substring(start, start + maxLen);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;   // 退出循环时两侧各多走了一步，故减 1
}

三种解法对比：

解法时间空间说明
中心扩展O(n²)O(1)面试首选，好写、无额外空间；共 2n-1 个中心
动态规划O(n²)O(n²)dp[i][j] 表示 s[i..j] 是否回文；写起来最直观但耗空间
ManacherO(n)O(n)用 # 插入把奇偶统一，再借"回文半径对称性"复用结果；面试做加分项即可

易错点：中心扩展的 return right - left - 1 容易写错。因为 while 退出时 left、right 已经各向外多走了一步，实际回文长度是 (right - 1) - (left + 1) + 1 = right - left - 1。

常见变体：回文子串的个数（把每次扩展的贡献累加即可）、最长回文子序列（这是子序列，要用 DP 而非中心扩展，注意与"子串"区别）。

10. 什么是字符串哈希（滚动哈希）？

答： 字符串哈希把字符串映射成一个整数，从而在 O(1) 内比较两个子串是否相等，代价是预处理 O(n) 与极小的碰撞概率。

前缀哈希（滚动哈希）思想：把字符串看作 base 进制数。

hash[i] = (hash[i-1] × base + s[i-1]) mod MOD

计算任意子串 s[l..r] 的哈希（用前缀哈希相减，需乘上 base^(r-l+1) 对齐位权）：

public class StringHash {
    private static final long BASE = 131;                 // 常用质数底
    private static final long MOD = 1_000_000_007L;       // 大质数模

    private final long[] hash;   // hash[i] = s[0..i-1] 的哈希
    private final long[] pow;    // pow[i] = BASE^i

    public StringHash(String s) {
        int n = s.length();
        hash = new long[n + 1];
        pow = new long[n + 1];
        pow[0] = 1;
        for (int i = 0; i < n; i++) {
            hash[i + 1] = (hash[i] * BASE + s.charAt(i)) % MOD;
            pow[i + 1] = (pow[i] * BASE) % MOD;
        }
    }

    /** 子串 s[l..r]（含两端）的哈希 */
    public long subHash(int l, int r) {
        return ((hash[r + 1] - hash[l] * pow[r - l + 1]) % MOD + MOD) % MOD;
    }
}

典型应用：

  • 判断两个子串是否相等（O(1)），用于最长重复子串（配合二分长度）；
  • 回文判断：正序与逆序各算一次哈希，O(1) 判断是否回文，再配合二分找最长回文（O(n log n)）；
  • 字符串匹配：模式串哈希与主串每个等长子串哈希比较（Rabin-Karp 算法），平均 O(n + m)。

哈希碰撞的处理：单一取模可能碰撞（不同字符串得到相同哈希）。工程上常用两种加固方式——① 双哈希（用两组 base/MOD 同时校验）；② 随机化 base（避免被恶意构造卡哈希）。面试中说明"存在极小碰撞概率，可用双哈希规避"即可。

11. 常见字符串面试题有哪些？

答： 按套路归类，一张表搞定大部分字符串题：

题目核心思路复杂度
反转字符串 / 反转单词顺序双指针对撞；或先整体反转再逐词反转O(n)
判断回文串双指针；忽略非字母数字时用 Character.isLetterOrDigitO(n)
字母异位词分组用"排序后的字符串"或"字符计数数组"作为哈希表的 keyO(n × k log k)
最长公共前缀纵向扫描（逐列比较）或分治O(n × m)
最长无重复字符子串滑动窗口 + 哈希表（见第四篇）O(n)
最长回文子串中心扩展 / Manacher（见第 9 题）O(n²) / O(n)
字符串匹配KMP（见第 8 题）/ 滚动哈希O(n + m)
字符串转整数（atoi）逐字符处理：去空格 → 符号 → 数字 → 溢出判断（用 long 或提前比较边界）O(n)
字符串相加 / 大数相乘模拟竖式运算：从低位到高位、维护进位、最后反转结果O(n × m)
有效的括号栈匹配（见第一篇）O(n)
最小覆盖子串滑动窗口 + 需求计数（窗口收缩到刚好满足时更新答案）O(n)
编辑距离 / LCS二维 DP（见第四篇）O(m × n)

两类 key 设计技巧（字母异位词类题目通用）：

  • 排序作 key：sortedStr 简单直接，代价是每个词都要排序；
  • 计数数组作 key：Arrays.toString(count) 或把 26 个计数编码成一个字符串，O(k) 更优，是"进阶写法"。

一句话总结：字符串题的三大杀器是——双指针/滑动窗口（线性扫描）、哈希表计数（异位词、频次）、KMP/DP（匹配与编辑）。看到字符串题先判断属于哪一类，再套模板。

最近更新:
贡献者: ixiaoqiang