SorryToPerson logo
返回
算法2026-04-15·8 分钟

算法知识库：图算法实现

图表示、遍历与最短路径算法的 JavaScript/TypeScript 实现。

图算法实现

1. 图的数据结构表示

时间复杂度: O(1) (创建图对象) 空间复杂度: O(V + E) (V为顶点数，E为边数)

  • 邻接表最常用于稀疏图。
  • 邻接矩阵适合小规模或稠密图。
  • 边列表适合构建最短路径和最小生成树。
ts
type Graph = Record<string, string[]>;

const graph: Graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C'],
};

2. 广度优先搜索（BFS）

ts
function bfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>([start]);
  const queue = [start];
  const order: string[] = [];

  while (queue.length) {
    const node = queue.shift()!;
    order.push(node);
    for (const neighbor of graph[node] ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return order;
}

3. 深度优先搜索（DFS）

ts
function dfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>();
  const result: string[] = [];

  function traverse(node: string) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph[node] ?? []) {
      traverse(neighbor);
    }
  }

  traverse(start);
  return result;
}

4. Dijkstra 最短路径

ts
type WeightedGraph = Record<string, { node: string; weight: number }[]>;

function dijkstra(graph: WeightedGraph, start: string) {
  const distances: Record<string, number> = {};
  const visited = new Set<string>();
  const nodes = Object.keys(graph);

  nodes.forEach((node) => {
    distances[node] = node === start ? 0 : Infinity;
  });

  while (visited.size < nodes.length) {
    const current = nodes.filter((node) => !visited.has(node)).reduce((minNode, node) => (distances[node] < distances[minNode] ? node : minNode), nodes[0]);

    visited.add(current);

    for (const edge of graph[current] ?? []) {
      const nextDistance = distances[current] + edge.weight;
      if (nextDistance < distances[edge.node]) {
        distances[edge.node] = nextDistance;
      }
    }
  }

  return distances;
}

5. 实现要点

  • 邻接表节省空间，适合大规模稀疏图。
  • BFS 适用于最短路径（无权图）和层次遍历。
  • DFS 适用于连通性、路径搜索和拓扑排序。
  • Dijkstra 适合非负权重图，复杂度可用优先队列进一步优化。
算法图JavaScript