Javascript에서 인접리스트 구현하기

1. 배열 사용

function createAdjacencyList(edges, nodeCount) {
  const adjacencyList = Array.from({ length: nodeCount + 1 }, () => []);

  for (const [u, v] of edges) {
    adjacencyList[u].push(v);
    adjacencyList[v].push(u);
  }

  return adjacencyList;
}

// 입력값
const nodeCount = 6;
const edgeList = [
  [1, 2],
  [2, 5],
  [5, 1],
  [3, 4],
  [4, 6]
];

// 인접 리스트 생성
const adjacencyList = createAdjacencyList(edgeList, nodeCount);

// 출력
adjacencyList.forEach((nodes, index) => {
  if (index !== 0) console.log(index, ":", nodes);
});

 

 

2. Map 객체 사용

function createAdjacencyList(edges, nodeCount) {
  const adjacencyList = new Map();

  // 노드 개수만큼 빈 배열을 미리 초기화
  for (let i = 1; i <= nodeCount; i++) {
    adjacencyList.set(i, []);
  }

  // 양방향 그래프이므로 양쪽에 추가
  for (const [u, v] of edges) {
    adjacencyList.get(u).push(v);
    adjacencyList.get(v).push(u);
  }

  return adjacencyList;
}

// 입력값
const nodeCount = 6;
const edgeList = [
  [1, 2],
  [2, 5],
  [5, 1],
  [3, 4],
  [4, 6]
];

// 인접 리스트 생성
const adjacencyList = createAdjacencyList(edgeList, nodeCount);

// 출력
for (let [key, value] of adjacencyList) {
  console.log(key, ":", value);
}

 

📌 출력 결과

1 : [ 2, 5 ]
2 : [ 1, 5 ]
3 : [ 4 ]
4 : [ 3, 6 ]
5 : [ 2, 1 ]
6 : [ 4 ]

 

배열을 사용하면 메모리 효율이 좋고, Map을 사용하면 키 값을 유연하게 설정할 수 있다.