JavaScript 그래프 구현: 인접 리스트·인접 행렬 비교와 BFS

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

그래프의 표현과 탐색은 서로 다른 선택입니다

그래프는 정점과 정점 사이의 간선을 저장합니다. 도로망, 의존 관계, 사람 사이의 연결처럼 부모 하나로 표현할 수 없는 관계를 다룹니다. 인접 리스트와 인접 행렬은 이 관계를 보관하는 형식이며, BFS는 그 형식에서 이웃을 읽어 방문 순서를 정하는 알고리즘입니다.

인접 리스트는 각 정점에 이웃 배열을 연결합니다. 정점이 많고 간선이 적은 희소 그래프에서 없는 간선을 저장하지 않아 공간을 아낍니다. 인접 행렬은 정점 쌍마다 칸을 만들어 간선 존재를 바로 확인하지만 간선이 없어도 V×V칸을 확보합니다.

정점·간선·방향 계약

정점 식별자는 문자열입니다. 생성자의 directed=false가 기본이므로 addEdge(A,B)는 A의 이웃에 B, B의 이웃에 A를 넣습니다. directed=true면 A→B 하나만 기록합니다. addVertex는 같은 정점을 다시 추가해도 기존 이웃을 지우지 않고, addEdge는 없는 끝점도 자동 생성합니다.

중복 간선은 제거하지 않고 그대로 저장합니다. 무방향 자기 루프 A-A는 같은 이웃 배열에 A를 두 번 넣습니다. 따라서 E를 입력 간선 수로 셀 때 무방향 인접 항목 수는 자기 루프를 포함해 2E입니다. 이 정책이 BFS의 방문 횟수를 늘리지 않도록 방문 집합을 별도로 사용합니다.

내부 Map의 키 순서는 정점 최초 추가 순서이며 각 이웃은 간선 입력 순서입니다. BFS 출력도 이 순서의 영향을 받습니다. 결과를 사전순이라고 가정하지 않습니다. adj는 학습을 위해 보여 주지만 외부에서 수정해 존재하지 않는 이웃을 넣으면 계약을 깨므로 메서드로만 갱신합니다.

전체 코드와 실행

graph.cjs로 아래 전체를 저장하고 Node.js에서 node ./graph.cjs를 실행합니다. 외부 패키지가 없는 CommonJS 예제입니다. 같은 A-B-C 삼각형과 고립 정점 D를 인접 리스트·행렬로 출력한 뒤 A에서 BFS를 실행합니다.

'use strict';

class Graph {
  constructor(directed = false) {
    this.directed = directed;
    this.adj = new Map();
  }

  addVertex(vertex) {
    if (typeof vertex !== 'string') throw new TypeError('vertex must be a string');
    if (!this.adj.has(vertex)) this.adj.set(vertex, []);
    return this;
  }

  addEdge(from, to) {
    this.addVertex(from);
    this.addVertex(to);
    this.adj.get(from).push(to);
    if (!this.directed) this.adj.get(to).push(from);
    return this;
  }

  hasEdge(from, to) {
    return this.adj.get(from)?.includes(to) ?? false;
  }

  toMatrix() {
    const vertices = [...this.adj.keys()];
    const indices = new Map(vertices.map((vertex, index) => [vertex, index]));
    const matrix = Array.from({ length: vertices.length },
      () => new Array(vertices.length).fill(0));
    for (const [from, neighbors] of this.adj) {
      for (const to of neighbors) matrix[indices.get(from)][indices.get(to)] = 1;
    }
    return { vertices, matrix };
  }

  bfs(start) {
    if (!this.adj.has(start)) return [];
    const visited = new Set([start]);
    const queue = [start];
    let head = 0;
    while (head < queue.length) {
      const vertex = queue[head];
      head += 1;
      for (const next of this.adj.get(vertex)) {
        if (visited.has(next)) continue;
        visited.add(next);
        queue.push(next);
      }
    }
    return queue;
  }
}

module.exports = { Graph };

if (require.main === module) {
  const graph = new Graph();
  graph.addEdge('A', 'B').addEdge('A', 'C').addEdge('B', 'C');
  graph.addVertex('D');
  console.log(JSON.stringify({
    list: [...graph.adj],
    ...graph.toMatrix(),
    bfs: graph.bfs('A'),
    hasAD: graph.hasEdge('A', 'D')
  }));
}

실행 출력

{"list":[["A",["B","C"]],["B",["A","C"]],["C",["A","B"]],["D",[]]],"vertices":["A","B","C","D"],"matrix":[[0,1,1,0],[1,0,1,0],[1,1,0,0],[0,0,0,0]],"bfs":["A","B","C"],"hasAD":false}

리스트를 행렬로 바꾸는 데 필요한 인덱스

정점 이름이 A나 서울처럼 문자열이면 행렬의 몇 번째 행인지 결정해야 합니다. toMatrix는 vertices 배열과 이름→인덱스 Map을 함께 만듭니다. 배열 순서가 행과 열의 표제 역할을 하므로 숫자 행렬만 단독으로 보관하면 어떤 정점 관계인지 잃을 수 있습니다.

각 행은 Array.from의 콜백으로 별도 배열을 생성합니다. 같은 내부 배열을 fill로 반복하면 한 칸 수정이 여러 행에 반영되는 참조 공유 오류가 생길 수 있습니다. 이후 모든 이웃을 읽어 해당 칸에 1을 넣습니다. 중복 간선이 여러 번 같은 칸을 1로 만들어도 개수 정보는 추가되지 않습니다.

toMatrix 결과는 그 시점의 복사본입니다. 나중에 graph.addEdge를 호출해도 이미 만든 행렬이 자동 갱신되지 않습니다. 두 표현을 항상 동기화하는 구현이 아니라 표현 변환을 보여 주는 예제라는 점을 구별해야 합니다. 가중치나 다중 간선 개수도 이 0/1 형식에는 담지 않습니다.

BFS는 넣는 순간 방문 처리합니다

bfs(start)는 정점이 없으면 빈 배열을 반환합니다. 정점이 있으면 시작점을 visited와 queue에 동시에 넣습니다. 하나를 꺼내 이웃을 읽을 때 이미 방문한 정점은 건너뛰고 처음 발견한 정점만 표시한 뒤 큐에 추가합니다. 이렇게 하면 한 정점이 여러 경로로 발견되어도 큐에 한 번만 들어갑니다.

방문 표시를 꺼낼 때로 미루면 A-B-C처럼 연결된 그래프에서 같은 정점이 아직 큐에 있는데 다시 들어갈 수 있습니다. 이웃 검사 시점의 visited가 “처리 완료”가 아니라 “이미 발견해서 예약함”이라는 의미라는 점이 중요합니다. 자기 루프와 중복 간선에도 같은 규칙을 적용하므로 무한히 순환하지 않습니다.

queue의 head를 늘리는 방식은 shift로 앞을 삭제하지 않으므로 기존 항목을 당기는 비용을 피합니다. 대신 처리한 정점도 배열에 남고 이 배열 자체를 방문 순서로 반환합니다. 따라서 이 구현의 큐 저장 공간은 방문한 정점 수 O(Vr)이며, 순간 대기열 길이만으로 공간을 계산하면 안 됩니다.

BFS는 가중치가 없는 그래프에서 시작점으로부터 간선 수 기준으로 가까운 층부터 방문합니다. 하지만 이 코드의 반환값은 방문 순서뿐입니다. 거리나 경로를 얻으려면 발견 시 거리와 이전 정점을 별도로 기록해야 합니다. 가중치가 서로 다른 그래프의 최단 경로를 이 순서만으로 구할 수는 없습니다.

전체 그래프를 다루려면 고립 정점도 필요합니다

간선만 입력받아 addEdge를 호출하면 어떤 간선에도 나오지 않는 정점은 존재를 알 수 없습니다. 연결 요소 수처럼 전체 정점이 중요한 문제는 vertices 목록을 받아 addVertex부터 수행해야 합니다. 한 시작점 BFS는 그 시작점의 연결 영역만 방문하므로 나머지 정점에서 다시 시작하는 바깥 반복이 필요합니다.

복잡도와 적용 한계

이 비용은 짧은 정점 식별자의 Map/Set 접근을 통상 상수 시간으로 보는 모델입니다. JavaScript 명세가 모든 Map 연산의 최악 O(1)을 약속한다는 의미는 아닙니다. 긴 문자열 식별자의 처리 비용과 입력 전체 JSON 메모리도 별도 고려해야 합니다. 큰 희소 그래프에서 출력 목적으로 V² 행렬을 만들면 리스트의 공간 이점을 잃습니다.

경계 확인과 연습

빈 그래프, 고립 정점, 중복 간선, 자기 루프, 방향 간선의 역방향 부재를 확인하세요. 작은 무작위 그래프에서는 행렬의 전이 폐쇄로 도달 가능성을 따로 구한 뒤 BFS 결과 집합과 비교하면 표현이나 방문 처리 오류를 독립적으로 검증할 수 있습니다.

JavaScript 그래프 연습: 연결 구역 크기를 작은 순서로 출력하기에서 직접 구현을 적용해 보세요.

함께 연습하고 확인할 자료

Number of Provinces: 행렬로 주어진 연결 관계에서 구역 수를 구하는 외부 연습입니다. 이 글은 정점·간선 목록에서 구역 크기를 출력합니다.

관련 개념 참고: Princeton Algorithms — Undirected Graphs 공식 자료와 문제 페이지는 2026년 9월 10일 확인했습니다. 외부 문제의 지문·예시를 복제하지 않고 이 글의 예제와 창작 문제를 별도로 구성했습니다.