图论基础

图的表示方式，以及 BFS / DFS 与最短路入门。代码继续用 JavaScript。

数据结构侧的概念补充见数据结构-图；本篇偏算法用法。

1. 图的基本概念（有向 / 无向 / 权）

图 = 顶点（Vertex） + 边（Edge）。

概念	含义
无向图	边无方向，(u,v) 与 (v,u) 相同
有向图	边有方向，u → v
权	边带数值（距离、成本）
度	无向：关联边数；有向：入度 / 出度
路径 / 环	顶点序列；起点终点相同则为环
连通	无向：任意两点可达；有向常谈强连通

刷题里常见建模：网格四连通、课程依赖（有向）、航班票价（带权）。

2. 邻接表与邻接矩阵

设 n 个顶点、m 条边。

	邻接矩阵	邻接表
空间	O(n²)	O(n + m)
查是否有边	O(1)	O(度)
枚举邻居	O(n)	O(度)
适用	稠密图、小 n	稀疏图（更常见）

// 邻接表：无向图（有向则只 push 一次）
function buildGraph(n, edges) {
  const g = Array.from({ length: n }, () => [])
  for (const [u, v] of edges) {
    g[u].push(v)
    g[v].push(u)
  }
  return g
}

// 带权：存 [to, weight]
function buildWeightedGraph(n, edges) {
  const g = Array.from({ length: n }, () => [])
  for (const [u, v, w] of edges) {
    g[u].push([v, w])
    g[v].push([u, w]) // 无向；有向删这行
  }
  return g
}

矩阵示例：matrix[u][v] = 1 或权值；无边用 0 / Infinity。

3. DFS 与 BFS

DFS（深度优先）

一路走到底再回溯。实现：递归或显式栈。

function dfs(g, start) {
  const seen = new Array(g.length).fill(false)
  const order = []
  function go(u) {
    seen[u] = true
    order.push(u)
    for (const v of g[u]) {
      if (!seen[v]) go(v)
    }
  }
  go(start)
  return order
}

用途：连通分量、环检测、拓扑（DFS 版）、网格沉岛、回溯搜路径。

BFS（广度优先）

按层扩展，无权图最短路（边数最少）用它。

function bfs(g, start) {
  const seen = new Array(g.length).fill(false)
  const dist = new Array(g.length).fill(-1)
  const q = [start]
  seen[start] = true
  dist[start] = 0
  while (q.length) {
    const u = q.shift() // 正式环境可用真正的队列避免 O(n) shift
    for (const v of g[u]) {
      if (seen[v]) continue
      seen[v] = true
      dist[v] = dist[u] + 1
      q.push(v)
    }
  }
  return dist
}

	DFS	BFS
结构	栈 / 递归	队列
最短路	一般不直接给	无权边数最短
空间	最坏 O(n)	最坏 O(n)

网格题把四方向当邻居即可，本质仍是图搜。

4. 拓扑排序

对有向无环图（DAG），排出「先修 → 后修」的线性序。有环则无法拓扑。

Kahn（BFS + 入度）

function topoSort(n, edges) {
  const g = Array.from({ length: n }, () => [])
  const indeg = new Array(n).fill(0)
  for (const [u, v] of edges) {
    // u → v：u 先于 v
    g[u].push(v)
    indeg[v]++
  }
  const q = []
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i)
  const order = []
  while (q.length) {
    const u = q.shift()
    order.push(u)
    for (const v of g[u]) {
      indeg[v]--
      if (indeg[v] === 0) q.push(v)
    }
  }
  return order.length === n ? order : [] // 空数组表示有环
}

用途：课程表、任务依赖、编译顺序。order.length < n ⇒ 有环。

5. 最短路入门（Dijkstra 概览）

场景	算法
无权 / 权全为 1	BFS
非负权	Dijkstra
有负权边（无负环）	Bellman-Ford
全源	Floyd-Warshall（O(n³)）

Dijkstra 思想：每次取出「当前距离最小」的未确定顶点，用它松弛邻居（类似 BFS，但用优先队列按距离扩展）。

// 非负权；返回从 start 到各点最短距离
function dijkstra(n, edges, start) {
  const g = Array.from({ length: n }, () => [])
  for (const [u, v, w] of edges) {
    g[u].push([v, w])
  }
  const dist = new Array(n).fill(Infinity)
  dist[start] = 0
  // 简易优先队列：每次取最小（正式应用堆 / 库）
  const used = new Array(n).fill(false)
  for (let k = 0; k < n; k++) {
    let u = -1
    for (let i = 0; i < n; i++) {
      if (!used[i] && (u === -1 || dist[i] < dist[u])) u = i
    }
    if (u === -1 || dist[u] === Infinity) break
    used[u] = true
    for (const [v, w] of g[u]) {
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w
    }
  }
  return dist
}

上面是 O(n²) 版，实现简单；稀疏图用二叉堆可到 O((n+m) log n)。

前提：边权非负。有负边不要用 Dijkstra。

6. 最小生成树概览

连通无向带权图中，选 n-1 条边连通所有点且权和最小 → 最小生成树（MST）。

算法	思路	复杂度直觉
Kruskal	边按权排序，不构成环就加入（并查集）	O(m log m)
Prim	从点扩张，每次加最小割边（类似 Dijkstra）	堆优化后较好

// Kruskal 骨架（find/union 用并查集）
function kruskal(n, edges) {
  edges = edges.slice().sort((a, b) => a[2] - b[2]) // [u,v,w]
  const parent = Array.from({ length: n }, (_, i) => i)
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])))
  let total = 0
  let cnt = 0
  for (const [u, v, w] of edges) {
    const pu = find(u)
    const pv = find(v)
    if (pu === pv) continue
    parent[pu] = pv
    total += w
    cnt++
    if (cnt === n - 1) break
  }
  return cnt === n - 1 ? total : -1 // -1 表示无法连通
}

面试常考：并查集模板 + Kruskal；Prim 能口述与 Dijkstra 的相似处即可。

---

图论刷题路径建议：邻接表建模 → BFS/DFS → 拓扑 → Dijkstra → 并查集 / MST。

上一篇：动态规划入门