理解二分图

看起来您只提供了来源链接，而没有贴出需要翻译的正文内容。请把要翻译的文本（包括任何 Markdown 格式）粘贴在这里，我就可以为您完成简体中文翻译。

介绍

在图算法方面的能力提升可以磨练你的编程技巧，并对诸如队列、栈和优先队列等众多数据结构产生连锁效应。本文将简要探讨 二分图 的概念，并提供使用 BFS 和 DFS 的 TypeScript 实现示例。

什么是二分图？

如果一个图的顶点可以使用两种不同的颜色着色，使得没有任何边连接两个颜色相同的顶点，则该图是二分的。换句话说，图的顶点可以划分为两个不相交的集合，并且每条边都只在这两个集合之间连接。

使用 BFS 检查二分性

广度优先搜索（BFS）按层遍历图。用于二分图检查的算法：

1. 将起始节点入队并为其分配一种颜色（例如 0）。
2. 当队列不为空时，出队一个节点。
3. 对每个邻居：
   • 若邻居已经拥有相同的颜色，则图 不是 二分图。
   • 若邻居尚未着色，则为其分配相反的颜色并入队。
4. 若队列在没有冲突的情况下清空，则图是二分图。

BFS 实现（TypeScript）

enum COLORS {
  COLORED_RED = 0,
  COLORED_GREEN = 1,
  NOT_COLORED = -1,
}

/**
 * Checks whether a graph is bipartite using BFS.
 *
 * @param startingNode - Index of the node to start the BFS from.
 * @param adj          - Adjacency list where adj[i] is an array of neighbors of node i.
 * @param colors       - Array storing the color of each node (initialized with NOT_COLORED).
 * @returns true if the graph is bipartite, false otherwise.
 */
const checkBipartiteBFS = (
  startingNode: number,
  adj: number[][],
  colors: COLORS[]
): boolean => {
  const queue: number[] = [];

  // Color the starting node and enqueue it
  colors[startingNode] = COLORS.COLORED_RED;
  queue.push(startingNode);

  while (queue.length !== 0) {
    const node = queue.shift() as number;

    for (const neighbourNode of adj[node]) {
      // Same color on both ends → not bipartite
      if (colors[neighbourNode] === colors[node]) {
        return false;
      }

      // Uncolored neighbor → assign opposite color and enqueue
      if (colors[neighbourNode] === COLORS.NOT_COLORED) {
        colors[neighbourNode] = (colors[node] + 1) % 2; // toggle between 0 and 1
        queue.push(neighbourNode);
      }
    }
  }

  // No conflicts found
  return true;
};

Source: …

使用 DFS 检查二分性

深度优先搜索 (DFS) 会在回溯之前尽可能深入每一条分支。DFS 的递归特性使得二分图的检查非常直接：

1. 为当前节点分配一种颜色。
2. 递归访问每个邻居：
   • 如果邻居已经拥有相同的颜色，则图 不是 二分图。
   • 如果邻居尚未着色，则使用相反的颜色递归检查。
3. 若所有递归调用都成功，则图是二分图。

DFS 实现 (TypeScript)

/**
 * Recursively checks bipartiteness using DFS.
 *
 * @param node   - Current node index.
 * @param color  - Color to assign to the current node (0 or 1).
 * @param colors - Array storing colors of nodes (initialized with NOT_COLORED).
 * @param adj    - Adjacency list.
 * @returns true if the subgraph rooted at `node` is bipartite, false otherwise.
 */
const checkBipartiteDFS = (
  node: number,
  color: 0 | 1,
  colors: COLORS[],
  adj: number[][]
): boolean => {
  colors[node] = color;

  for (const neighbourNode of adj[node]) {
    // Conflict: same color on both ends
    if (colors[neighbourNode] === colors[node]) return false;

    // Uncolored neighbor → recurse with opposite color
    if (
      colors[neighbourNode] === COLORS.NOT_COLORED &&
      !checkBipartiteDFS(
        neighbourNode,
        color === 0 ? 1 : 0,
        colors,
        adj
      )
    ) {
      return false;
    }
  }

  // No conflicts in this branch
  return true;
};

结论

BFS 和 DFS 提供了验证图是否为二分图的高效方法。BFS 使用显式队列并迭代地为节点着色，而 DFS 则利用递归实现相同的目标。请选择最适合您现有代码库或个人偏好的方法。

祝编码愉快！