Các thuật toán đồ thị mọi kỹ sư nên biết

Đồ thị xuất hiện ở mọi nơi mà quan hệ quan trọng hơn từng dòng dữ liệu: dịch vụ triển khai lần theo dependency, hệ thống dẫn đường đi theo mạng đường, bộ máy phân quyền đi theo quan hệ thành viên, còn công cụ build đi theo các lệnh import. Các câu hỏi cứ lặp lại: Từ đỉnh này tới được đâu? Tuyến nào rẻ nhất? Công việc có thể chạy theo thứ tự nào? Thêm liên kết có tạo chu trình không?

Code production đòi hỏi nhiều hơn việc nhớ tên thuật toán. Ta phải khớp giả định với dữ liệu, giữ invariant khi cài đặt và định nghĩa hành vi cho component rời rạc, chu trình, cạnh trùng hay trọng số âm. Bài viết xây dựng một toolkit TypeScript nhỏ trên adjacency list để giải thích BFS, DFS, Dijkstra và topological sort theo góc nhìn đó.

Mô hình hóa đồ thị trước khi chọn thuật toán #

Đồ thị $G = (V, E)$ gồm đỉnh $V$ và cạnh $E$. Hướng và trọng số thuộc contract bài toán: dependency của package chỉ theo một hướng, trong khi quan hệ bạn bè có thể đối xứng. Mô hình sai loại cạnh sẽ đổi đáp án.

Adjacency list lưu các cạnh đi ra với $O(|V| + |E|)$ bộ nhớ, phù hợp với đồ thị thưa trong production. Adjacency matrix tốn $O(|V|^2)$ nhưng kiểm tra một cạnh trong thời gian hằng số, nên hợp với đồ thị nhỏ và dày.

type NodeId = string;

type Edge = Readonly<{
  to: NodeId;
  weight: number;
}>;

class Graph {
  private readonly adjacency = new Map<NodeId, Edge[]>();

  constructor(readonly directed: boolean) {}

  addNode(node: NodeId): void {
    if (!this.adjacency.has(node)) this.adjacency.set(node, []);
  }

  addEdge(from: NodeId, to: NodeId, weight = 1): void {
    if (!Number.isFinite(weight)) throw new Error('Weight must be finite');
    this.addNode(from);
    this.addNode(to);
    this.adjacency.get(from)!.push({ to, weight });
    if (!this.directed) this.adjacency.get(to)!.push({ to: from, weight });
  }

  nodes(): readonly NodeId[] {
    return [...this.adjacency.keys()];
  }

  neighbors(node: NodeId): readonly Edge[] {
    return this.adjacency.get(node) ?? [];
  }
}

addNode giữ được đỉnh cô lập; nếu đỉnh chỉ sinh ra cùng cạnh, component một đỉnh sẽ biến mất. Hãy quy định riêng cạnh song song và self-loop có hợp lệ hay không, thay vì để cấu trúc lưu trữ âm thầm quyết định policy domain.

Audit store cô lập sẽ không được tìm thấy khi duyệt từ API. Muốn duyệt toàn graph, phải bắt đầu lại từ mỗi đỉnh chưa thăm.

Tìm khả năng kết nối bằng BFS và DFS #

BFS khám phá theo lớp. Queue lấy đỉnh theo khoảng cách không giảm, nên trong graph không trọng số, đường đầu tiên tới một đỉnh có ít cạnh nhất. Nó phù hợp cho minimum hop và trạng thái gần nhất.

DFS đi sâu một nhánh rồi quay lui. Đỉnh phải được đánh dấu trước khi đường khác lên lịch lại. DFS hợp với reachability, component, phát hiện chu trình và thời điểm vào-ra, nhưng không đảm bảo đường ngắn nhất.

type Traversal = Readonly<{
  order: readonly NodeId[];
  parent: ReadonlyMap<NodeId, NodeId>;
}>;

function bfs(graph: Graph, start: NodeId): Traversal & {
  distance: ReadonlyMap<NodeId, number>;
} {
  const order: NodeId[] = [];
  const parent = new Map<NodeId, NodeId>();
  const distance = new Map<NodeId, number>([[start, 0]]);
  const queue: NodeId[] = [start];

  for (let head = 0; head < queue.length; head += 1) {
    const node = queue[head]!;
    order.push(node);

    for (const { to } of graph.neighbors(node)) {
      if (distance.has(to)) continue;
      distance.set(to, distance.get(node)! + 1);
      parent.set(to, node);
      queue.push(to);
    }
  }

  return { order, parent, distance };
}

function dfs(graph: Graph, start: NodeId): Traversal {
  const order: NodeId[] = [];
  const parent = new Map<NodeId, NodeId>();
  const visited = new Set<NodeId>([start]);
  const stack: NodeId[] = [start];

  while (stack.length > 0) {
    const node = stack.pop()!;
    order.push(node);
    const neighbors = graph.neighbors(node);

    for (let index = neighbors.length - 1; index >= 0; index -= 1) {
      const next = neighbors[index]!.to;
      if (visited.has(next)) continue;
      visited.add(next);
      parent.set(next, node);
      stack.push(next);
    }
  }

  return { order, parent };
}

Cả hai chạy trong $O(|V| + |E|)$ trên component đạt tới được và dùng $O(|V|)$ bộ nhớ. Con trỏ head tránh chi phí dời mảng của shift(); DFS dạng lặp tránh tràn call stack. Đảo neighbor khi push chỉ tạo thứ tự ổn định, không ảnh hưởng tính đúng.

Phải đánh dấu ngay lúc phát hiện. Nếu chờ tới lúc lấy khỏi queue hoặc stack, nhiều cạnh vào có thể thêm cùng đỉnh nhiều lần và ghi đè parent. Parent map chỉ chứa đỉnh đã tới; caller phải phân biệt start với đỉnh không thể tới.

Đường đi có trọng số với Dijkstra #

BFS tối thiểu số cạnh, không tối thiểu chi phí. Với trọng số không âm, Dijkstra liên tục chốt đỉnh có khoảng cách tạm thời nhỏ nhất. Invariant là khi entry nhỏ nhất rời priority queue, không đường xét sau nào có thể cải thiện nó.

Bước relaxation kiểm tra xem đi tới to qua đỉnh hiện tại có rẻ hơn không:

Nếu $alt < dist[v]$, cập nhật khoảng cách và predecessor. Binary heap cho thời gian $O((|V| + |E|) \log |V|)$.

type QueueEntry = { node: NodeId; priority: number };

class MinQueue {
  private readonly heap: QueueEntry[] = [];

  push(entry: QueueEntry): void {
    this.heap.push(entry);
    for (let index = this.heap.length - 1; index > 0; ) {
      const parent = Math.floor((index - 1) / 2);
      if (this.heap[parent]!.priority <= entry.priority) break;
      this.heap[index] = this.heap[parent]!;
      index = parent;
      this.heap[index] = entry;
    }
  }

  pop(): QueueEntry | undefined {
    const first = this.heap[0];
    const last = this.heap.pop();
    if (!first || !last || this.heap.length === 0) return first;
    this.heap[0] = last;

    for (let index = 0; ; ) {
      const left = index * 2 + 1;
      const right = left + 1;
      let smallest = index;
      if (left < this.heap.length &&
          this.heap[left]!.priority < this.heap[smallest]!.priority) smallest = left;
      if (right < this.heap.length &&
          this.heap[right]!.priority < this.heap[smallest]!.priority) smallest = right;
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] =
        [this.heap[smallest]!, this.heap[index]!];
      index = smallest;
    }
    return first;
  }

  get size(): number {
    return this.heap.length;
  }
}

function dijkstra(graph: Graph, start: NodeId): {
  distance: ReadonlyMap<NodeId, number>;
  parent: ReadonlyMap<NodeId, NodeId>;
} {
  const distance = new Map(graph.nodes().map((node) => [node, Infinity]));
  const parent = new Map<NodeId, NodeId>();
  const queue = new MinQueue();

  for (const node of graph.nodes()) {
    for (const edge of graph.neighbors(node)) {
      if (edge.weight < 0) throw new Error('Dijkstra requires nonnegative weights');
    }
  }

  distance.set(start, 0);
  queue.push({ node: start, priority: 0 });

  while (queue.size > 0) {
    const current = queue.pop()!;
    if (current.priority !== distance.get(current.node)) continue;

    for (const edge of graph.neighbors(current.node)) {
      const candidate = current.priority + edge.weight;
      if (candidate >= (distance.get(edge.to) ?? Infinity)) continue;
      distance.set(edge.to, candidate);
      parent.set(edge.to, current.node);
      queue.push({ node: edge.to, priority: candidate });
    }
  }

  return { distance, parent };
}

Heap không có decrease-key: mỗi cải thiện thêm một entry, còn phép so sánh bỏ entry cũ. Đỉnh không tới được giữ Infinity. Chỉ dựng path bằng cách lần ngược parent rồi đảo kết quả khi khoảng cách hữu hạn.

Dependency, chu trình và tính liên thông #

Topological order đặt mọi cạnh từ đỉnh đứng trước tới đỉnh đứng sau và chỉ tồn tại với DAG. Thuật toán Kahn theo dõi indegree, đưa đỉnh indegree bằng không vào queue rồi coi như xóa cạnh đi ra. Invariant: đỉnh trong queue không còn prerequisite chưa xử lý.

function topologicalSort(graph: Graph): readonly NodeId[] {
  if (!graph.directed) throw new Error('Topological sort requires a directed graph');

  const indegree = new Map(graph.nodes().map((node) => [node, 0]));
  for (const node of graph.nodes()) {
    for (const { to } of graph.neighbors(node)) {
      indegree.set(to, (indegree.get(to) ?? 0) + 1);
    }
  }

  const queue = graph.nodes().filter((node) => indegree.get(node) === 0);
  const order: NodeId[] = [];

  for (let head = 0; head < queue.length; head += 1) {
    const node = queue[head]!;
    order.push(node);
    for (const { to } of graph.neighbors(node)) {
      const next = indegree.get(to)! - 1;
      indegree.set(to, next);
      if (next === 0) queue.push(to);
    }
  }

  if (order.length !== graph.nodes().length) {
    throw new Error('Graph contains a cycle');
  }
  return order;
}

Đây là nền tảng của build, migration, spreadsheet và workflow. Partial order có thể có nhiều output đúng, nên test ràng buộc từng cạnh thay vì một chuỗi tùy ý. Muốn output ổn định, dùng priority queue và quy định cách phá hòa.

Lặp BFS hoặc DFS tìm component trong graph tĩnh. Với graph vô hướng chủ yếu thêm cạnh và nhiều truy vấn connectivity, union-find tốt hơn: path compression cùng union by rank đạt $O(\alpha(|V|))$ amortized. Nó không tạo route, xóa cạnh hiệu quả hay xử lý hướng.

Ứng dụng production và chiến lược kiểm thử #

Chọn thuật toán từ output contract. Phân tích ảnh hưởng service cần BFS/DFS; scheduler cần topological order và báo chu trình; định tuyến độ trễ dùng Dijkstra khi chi phí không âm, cộng dồn. Graph phân quyền cần hướng và giới hạn vì fan-out lớn có thể gây cạn tài nguyên.

Graph có thể đổi giữa lúc tính. Hãy chọn snapshot, eventual consistency hoặc chạy lại khi version đổi. Graph quá lớn có thể cần truy vấn frontier trong database hay hệ chuyên dụng. Với traversal do người dùng điều khiển, giới hạn độ sâu, số đỉnh và thời gian; trả trạng thái cắt ngắn riêng.

Test nên khẳng định property, không chỉ kiểm tra vài ví dụ quen thuộc:

• Với mỗi cạnh parent của BFS, khoảng cách của con bằng khoảng cách của cha cộng một.
• Mỗi đỉnh có thể tới được xuất hiện đúng một lần trong output BFS và DFS.
• Với mọi cạnh sau Dijkstra, distance[to] <= distance[from] + weight.
• Dựng lại một đường Dijkstra hữu hạn phải cho tổng trọng số bằng đúng khoảng cách báo cáo.
• Mọi cạnh trong kết quả topological đều hướng về phía trước; đầu vào có chu trình phải throw.
• Graph rỗng, một đỉnh, self-loop, cạnh song song, component rời rạc và đỉnh bậc cao đều có expectation rõ.
• Graph nhỏ sinh ngẫu nhiên có thể so với implementation chậm hơn, chẳng hạn Bellman-Ford cho shortest path không âm.

Determinism phải là quyết định chủ động. Dữ liệu song song có thể đến khác thứ tự; nếu output đi vào cache hay deployment plan, hãy sort neighbor hoặc định nghĩa priority. Đừng coi một traversal hợp lệ là thứ tự duy nhất.

Về observability, ghi kích thước graph, số đỉnh đã thăm, queue lớn nhất, thời gian và trạng thái cắt ngắn. Chúng phát hiện graph quá dày, fan-out bất thường hoặc truy vấn bỗng thành phép quét toàn hệ thống.

Điều cần ghi nhớ #

Hãy mô hình hóa hướng, trọng số và đỉnh cô lập trước. Dùng BFS cho minimum hop, DFS cho cấu trúc theo chiều sâu, Dijkstra cho trọng số không âm, topological sort cho DAG và union-find cho nhiều truy vấn liên thông vô hướng.

Giữ invariant: đánh dấu khi phát hiện, chốt khoảng cách Dijkstra nhỏ nhất và chỉ xuất đỉnh indegree bằng không khi sắp xếp topo. Xem cạnh âm, chu trình và component rời rạc là contract case. Kiểm thử property lẫn giới hạn tài nguyên để biến thuật toán giáo trình thành hành vi production đáng tin cậy.