手写图结构：邻接表、遍历算法与最短路径

图（Graph）是最通用的数据结构之一，它由**顶点（Vertex/Node）和边（Edge）**组成，能够表示任意复杂的关系网络。社交网络中的好友关系、地图中的路径规划、依赖管理中的包引用关系，本质上都是图。

与树不同，图没有根节点，顶点之间可以任意连接，甚至形成环路。本文将手写实现图数据结构，并深入讲解图的遍历、最短路径和拓扑排序三大经典算法。

图的基本概念

有向图与无向图

无向图（Undirected Graph）：边没有方向，A 连接到 B 意味着 B 也连接到 A。例如：好友关系。
有向图（Directed Graph）：边有方向，A → B 不代表 B → A。例如：Twitter 的关注关系。

加权图

边带有**权重（Weight）**的图称为加权图，常用于表示距离、成本、时间等。例如：地图导航中，边的权重就是两地之间的距离。

图的表示方法

图有两种主流的存储方式：邻接矩阵和邻接表。

邻接矩阵（Adjacency Matrix）

用一个二维数组 matrix[i][j] 表示顶点 i 到顶点 j 是否有边。对于加权图，存储权重值；无权图用 0/1 表示。

// 4 个顶点的无向无权图
//    0 --- 1
//    |     |
//    2 --- 3

const adjMatrix = [
  [0, 1, 1, 0], // 顶点 0 连接到 1、2
  [1, 0, 0, 1], // 顶点 1 连接到 0、3
  [1, 0, 0, 1], // 顶点 2 连接到 0、3
  [0, 1, 1, 0], // 顶点 3 连接到 1、2
];

优点：判断两点之间是否有边是 O(1)。缺点：空间复杂度 O(V²)，稀疏图浪费严重。

邻接表（Adjacency List）

每个顶点维护一个列表，存储与其相邻的所有顶点。这是实际中最常用的表示方式。

// 同一个图用邻接表表示
const adjList = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2],
};

优点：空间复杂度 O(V + E)，适合稀疏图。缺点：判断两点是否有边需要遍历列表，最坏 O(V)。

本文使用邻接表实现，因为它更节省空间，且遍历邻居更高效。

手写图类

class Graph {
  constructor(isDirected = false) {
    this.adjList = new Map();    // 邻接表：顶点 -> 邻居列表
    this.isDirected = isDirected; // 是否为有向图
  }

  // 添加顶点
  addVertex(vertex) {
    if (!this.adjList.has(vertex)) {
      this.adjList.set(vertex, []);
    }
  }

  // 添加边
  addEdge(vertex1, vertex2, weight = 1) {
    // 确保两个顶点都存在
    this.addVertex(vertex1);
    this.addVertex(vertex2);

    // 添加 vertex1 -> vertex2 的边
    this.adjList.get(vertex1).push({ node: vertex2, weight });

    // 无向图需要反向边
    if (!this.isDirected) {
      this.adjList.get(vertex2).push({ node: vertex1, weight });
    }
  }

  // 获取顶点的所有邻居
  getNeighbors(vertex) {
    return this.adjList.get(vertex) || [];
  }

  // 获取所有顶点
  getVertices() {
    return Array.from(this.adjList.keys());
  }

  // 打印图结构
  print() {
    for (const [vertex, edges] of this.adjList) {
      const edgeStr = edges.map(e => `${e.node}${e.weight !== 1 ? `(${e.weight})` : ''}`).join(', ');
      console.log(`${vertex} -> [${edgeStr}]`);
    }
  }
}

构建示例图

const graph = new Graph(false); // 无向图

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');

graph.print();
// A -> [B, C]
// B -> [A, D]
// C -> [A, D, E]
// D -> [B, C, E]
// E -> [C, D]

图的遍历：BFS 与 DFS

图的遍历是指从某个顶点出发，按照某种策略访问图中所有可达的顶点。

广度优先搜索（BFS）

BFS 从起始顶点开始，先访问所有直接邻居，再访问邻居的邻居，逐层向外扩散。它使用队列实现。

class Graph {
  // ... 前面的方法

  bfs(startVertex, callback) {
    const visited = new Set();
    const queue = [startVertex];
    visited.add(startVertex);

    while (queue.length > 0) {
      const vertex = queue.shift();
      callback(vertex);

      // 将所有未访问的邻居入队
      for (const neighbor of this.getNeighbors(vertex)) {
        if (!visited.has(neighbor.node)) {
          visited.add(neighbor.node);
          queue.push(neighbor.node);
        }
      }
    }
  }
}

BFS 的特点是：先找到的路径一定是最短的（以边数计）。因此 BFS 常用于无权图的最短路径问题。

深度优先搜索（DFS）

DFS 从起始顶点开始，沿着一条路径尽可能深地探索，直到走不通再回溯。它使用栈（递归调用栈或显式栈）实现。

class Graph {
  // ... 前面的方法

  // 递归实现
  dfs(startVertex, callback) {
    const visited = new Set();
    this._dfsRecursive(startVertex, visited, callback);
  }

  _dfsRecursive(vertex, visited, callback) {
    visited.add(vertex);
    callback(vertex);

    for (const neighbor of this.getNeighbors(vertex)) {
      if (!visited.has(neighbor.node)) {
        this._dfsRecursive(neighbor.node, visited, callback);
      }
    }
  }

  // 非递归实现（使用显式栈）
  dfsIterative(startVertex, callback) {
    const visited = new Set();
    const stack = [startVertex];

    while (stack.length > 0) {
      const vertex = stack.pop();

      if (!visited.has(vertex)) {
        visited.add(vertex);
        callback(vertex);

        // 将未访问的邻居压入栈
        for (const neighbor of this.getNeighbors(vertex)) {
          if (!visited.has(neighbor.node)) {
            stack.push(neighbor.node);
          }
        }
      }
    }
  }
}

BFS vs DFS 对比

const graph = new Graph(false);
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('E', 'F');

//       A
//      / \
//     B   C
//    / \   \
//   D   E - F

console.log('BFS:');
graph.bfs('A', v => console.log(v));
// 输出: A, B, C, D, E, F（分层扩散）

console.log('DFS:');
graph.dfs('A', v => console.log(v));
// 输出: A, B, D, E, F, C（一条道走到黑）

特性	BFS	DFS
数据结构	队列	栈（递归）
空间复杂度	O(V)	O(V)（递归栈）
最短路径	无权图最短	不保证最短
适用场景	最短路径、层级遍历	路径搜索、连通分量、拓扑排序

最短路径：Dijkstra 算法

Dijkstra 算法用于在加权图中找到一个顶点到其他所有顶点的最短路径。它要求边的权重为非负数。

核心思想：维护一个距离数组，每次选择当前距离最小的未确定顶点，用它更新邻居的距离。

class Graph {
  // ... 前面的方法

  dijkstra(startVertex) {
    const distances = new Map();     // 到各顶点的最短距离
    const previous = new Map();      // 最短路径中的前驱节点
    const visited = new Set();

    // 初始化：起点距离为 0，其余为无穷大
    for (const vertex of this.adjList.keys()) {
      distances.set(vertex, vertex === startVertex ? 0 : Infinity);
      previous.set(vertex, null);
    }

    while (visited.size < this.adjList.size) {
      // 找到未访问中距离最小的顶点
      let minVertex = null;
      let minDistance = Infinity;

      for (const [vertex, distance] of distances) {
        if (!visited.has(vertex) && distance < minDistance) {
          minDistance = distance;
          minVertex = vertex;
        }
      }

      // 所有可达顶点都已处理
      if (minVertex === null) break;

      visited.add(minVertex);

      // 更新邻居的距离
      for (const neighbor of this.getNeighbors(minVertex)) {
        if (visited.has(neighbor.node)) continue;

        const newDistance = distances.get(minVertex) + neighbor.weight;
        if (newDistance < distances.get(neighbor.node)) {
          distances.set(neighbor.node, newDistance);
          previous.set(neighbor.node, minVertex);
        }
      }
    }

    return { distances, previous };
  }

  // 构建从起点到目标点的路径
  getPath(previous, target) {
    const path = [];
    let current = target;

    while (current !== null) {
      path.unshift(current);
      current = previous.get(current);
    }

    return path;
  }
}

使用示例：地图最短路径

const cityGraph = new Graph(false);

// 构建城市距离图（单位：公里）
cityGraph.addEdge('北京', '天津', 120);
cityGraph.addEdge('北京', '石家庄', 280);
cityGraph.addEdge('天津', '济南', 320);
cityGraph.addEdge('石家庄', '郑州', 420);
cityGraph.addEdge('济南', '郑州', 460);
cityGraph.addEdge('郑州', '武汉', 520);

const result = cityGraph.dijkstra('北京');

console.log('北京到各城市最短距离:');
for (const [city, distance] of result.distances) {
  if (distance !== Infinity) {
    console.log(`  ${city}: ${distance}km`);
  }
}

// 获取北京到武汉的具体路径
const path = cityGraph.getPath(result.previous, '武汉');
console.log('北京到武汉的路径:', path.join(' -> '));
// 输出: 北京 -> 石家庄 -> 郑州 -> 武汉

Dijkstra 算法的时间复杂度为 O(V²)（上述简单实现），使用**优先队列（最小堆）**优化后可降至 O((V + E) log V)。

拓扑排序

拓扑排序是针对**有向无环图（DAG, Directed Acyclic Graph）**的一种排序算法。它将图中的顶点排成一个线性序列，使得对于图中的每条有向边 A → B，A 在序列中都出现在 B 之前。

经典应用：任务调度（先修课程）、编译依赖解析、Makefile 构建顺序。

Kahn 算法（基于 BFS）

class Graph {
  // ... 前面的方法

  topologicalSort() {
    // 计算每个顶点的入度
    const inDegree = new Map();
    for (const vertex of this.adjList.keys()) {
      inDegree.set(vertex, 0);
    }

    for (const edges of this.adjList.values()) {
      for (const edge of edges) {
        inDegree.set(edge.node, (inDegree.get(edge.node) || 0) + 1);
      }
    }

    // 将所有入度为 0 的顶点入队
    const queue = [];
    for (const [vertex, degree] of inDegree) {
      if (degree === 0) {
        queue.push(vertex);
      }
    }

    const result = [];

    while (queue.length > 0) {
      const vertex = queue.shift();
      result.push(vertex);

      // 将所有邻居的入度减 1
      for (const neighbor of this.getNeighbors(vertex)) {
        const newDegree = inDegree.get(neighbor.node) - 1;
        inDegree.set(neighbor.node, newDegree);

        if (newDegree === 0) {
          queue.push(neighbor.node);
        }
      }
    }

    // 如果结果数量不等于顶点数，说明图中存在环
    if (result.length !== this.adjList.size) {
      throw new Error('图中存在环，无法进行拓扑排序');
    }

    return result;
  }
}

使用示例：课程先修关系

const courseGraph = new Graph(true); // 有向图

// 先修课程关系：A -> B 表示必须先学 A 才能学 B
courseGraph.addEdge('数学', '物理');
courseGraph.addEdge('数学', '化学');
courseGraph.addEdge('物理', '工程力学');
courseGraph.addEdge('化学', '生物化学');
courseGraph.addEdge('工程力学', '结构设计');

try {
  const order = courseGraph.topologicalSort();
  console.log('课程学习顺序:', order.join(' -> '));
  // 输出: 数学 -> 物理 -> 工程力学 -> 结构设计 -> 化学 -> 生物化学
} catch (e) {
  console.log(e.message);
}

总结

算法	时间复杂度	空间复杂度	适用场景
BFS	O(V + E)	O(V)	无权图最短路径、层级遍历
DFS	O(V + E)	O(V)	路径搜索、连通分量检测
Dijkstra	O((V+E) log V)	O(V)	非负权图单源最短路径
拓扑排序	O(V + E)	O(V)	任务调度、依赖解析

图是最灵活的数据结构，几乎所有复杂的关系网络都可以用图建模。掌握图的存储方式、遍历策略和经典算法，是解决实际问题和通过技术面试的关键能力。

从社交网络的好友推荐，到地图导航的最短路径，再到软件工程的依赖管理——图算法的身影无处不在。

手写图结构：邻接表、遍历算法与最短路径

手写图结构：邻接表、遍历算法与最短路径

图的基本概念

有向图与无向图

加权图

图的表示方法

邻接矩阵（Adjacency Matrix）

邻接表（Adjacency List）

手写图类

构建示例图

图的遍历：BFS 与 DFS

广度优先搜索（BFS）

深度优先搜索（DFS）

BFS vs DFS 对比

最短路径：Dijkstra 算法

使用示例：地图最短路径

拓扑排序

Kahn 算法（基于 BFS）

使用示例：课程先修关系

总结

评论

Related Articles

数组内置方法综合运用

手写二叉搜索树：插入、查找、删除与遍历全解析

JavaScript 对象与原型