javascript - 그래프(graph)

그래프

노드(node)와 그 노드들을 연결하는 간선(edge)으로 이루어진 자료 구조입니다. 그래프는 현실 세계에서 다양한 상호 관계를 표현하는데 사용됩니다. 예를 들면 지도에서 도시들을 노드로, 도로를 간선으로 표현하는 것이 그래프의 한 예입니다.

JavaScript에서 그래프를 구현하는 방법 중 가장 일반적인 두 가지 방법은 "인접 행렬"과 "인접 리스트"입니다.

인접 행렬 (Adjacency Matrix)

인접 행렬은 2차원 배열로 그래프의 연결 정보를 표현합니다. 노드 간 연결 여부를 행렬의 값으로 표현하며, 노드 수가 N개인 그래프라면 NxN 크기의 행렬이 필요합니다.
예를 들어, 노드 1과 노드 2가 간선으로 연결되어 있다면, 인접 행렬의 1행 2열과 2행 1열에 해당하는 값에 연결 정보를 표시합니다.

인접 리스트 (Adjacency List)

인접 리스트는 객체나 배열을 사용하여 그래프의 노드와 해당 노드에 인접한 노드들을 연결합니다. 각 노드마다 연결된 노드들을 리스트로 표현하는 방식입니다.
예를 들어, 그래프의 노드 1과 연결된 노드들을 배열 [2, 3, 4]로 표현하고, 노드 2와 연결된 노드들을 배열 [1, 5]로 표현하는 식으로 구성됩니다.

JavaScript에서 이러한 그래프를 구현하기 위해 객체를 사용하는 경우가 많습니다. 예를 들어, 인접 리스트를 객체로 표현하면 다음과 같습니다.

const graph = {
  1: [2, 3, 4],
  2: [1, 5],
  3: [1],
  4: [1],
  5: [2],
};

이렇게 구현된 그래프를 기반으로 다양한 그래프 알고리즘을 적용할 수 있습니다. 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)은 그래프의 구조를 파악하거나 경로를 찾는 데에 자주 활용되는 알고리즘 중 일부입니다.

이외에도 JavaScript에는 그래프를 구현하는 다양한 라이브러리가 있으며, 이러한 라이브러리를 활용하면 더욱 간편하게 그래프를 다룰 수 있습니다. 예를 들어, D3.js는 데이터 시각화를 위한 라이브러리로서 그래프를 효과적으로 시각화하는데 유용합니다.