이분 그래프 이해하기

Source: Dev.to

번역을 진행하려면 번역하고자 하는 전체 텍스트를 제공해 주시겠어요?
텍스트를 알려주시면 원본 형식과 마크다운을 그대로 유지하면서 한국어로 번역해 드리겠습니다.

소개

그래프 알고리즘에 대한 역량을 키우면 프로그래밍 실력이 향상될 뿐만 아니라 큐, 스택, 우선순위 큐와 같은 다양한 자료구조에도 긍정적인 영향을 미칩니다. 이 글에서는 이분 그래프 개념을 간략히 살펴보고, TypeScript를 사용한 BFS와 DFS 구현을 부드럽게 소개합니다.

이분 그래프란 무엇인가?

그래프의 정점을 두 가지 서로 다른 색으로 색칠할 수 있고, 같은 색의 두 정점을 연결하는 간선이 없을 경우 그 그래프는 이분 그래프라고 합니다. 즉, 그래프의 정점을 두 개의 서로 겹치지 않는 집합으로 나눌 수 있으며, 모든 간선은 두 집합 사이에만 존재합니다.

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;
};

DFS로 이분 그래프 확인

Depth‑First Search (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는 재귀를 활용해 동일한 목표를 달성합니다. 주변 코드베이스나 개인 선호에 가장 잘 맞는 접근 방식을 선택하세요.

코딩을 즐기세요!