이 글에서는 가중치(weight)를 지원하고 방향 그래프와 무방향 그래프를 모두 다룰 수 있는 그래프 클래스를 만들어 보겠습니다. 구현은 인접 리스트(Adjacency List) 방식을 사용하며, 이후 BFS, 최단 경로 같은 고급 알고리즘을 학습할 때 가중치와 방향성 정보가 유용하게 활용됩니다.
인접 리스트란?
인접 리스트는 개별 리스트들을 담고 있는 배열 A입니다. 배열의 각 원소 A[i]는 하나의 리스트로, 정점 i에 인접한(연결된) 모든 정점들을 포함합니다. 우리는 이 인접 리스트를 nodes(정점 목록)와 edges(간선 정보) 두 멤버 변수로 정의할 것입니다.
그래프 클래스 설계
그래프 클래스를 정의하고, 노드와 간선을 추가하는 데 사용할 메서드들을 먼저 준비하겠습니다. 초기 단계에서 정의할 메서드는 다음과 같습니다.
- addNode: 그래프에 새로운 노드를 추가합니다.
- addEdge: 무방향 간선(양방향 연결)을 추가합니다.
- addDirectedEdge: 방향 간선(단방향 연결)을 추가합니다.
예제 코드
class Graph {
constructor() {
this.edges = {};
this.nodes = [];
}
addNode(node) {
this.nodes.push(node);
this.edges[node] = [];
}
addEdge(node1, node2) {
this.edges[node1].push(node2);
this.edges[node2].push(node1);
}
addDirectedEdge(node1, node2) {
this.edges[node1].push(node2);
}
display() {
let graph = ""; this.nodes.forEach(node => {
graph += node + "->" + this.edges[node].join(", ") + "\n";
});
console.log(graph);
}
}edges 객체에는 각 노드를 키로 하여 인접 노드들의 배열이 저장되며, nodes 배열은 그래프에 존재하는 모든 정점의 목록을 관리합니다. display() 메서드는 각 노드와 그에 연결된 노드들을 화살표 형태로 출력해 전체 그래프 구조를 한눈에 확인할 수 있게 해줍니다.
클래스 테스트하기
작성한 메서드와 클래스를 아래와 같이 테스트해 볼 수 있습니다.
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addEdge("D", "E");
g.display();실행 결과
위 코드를 실행하면 다음과 같은 출력 결과를 얻습니다.
A->C, B, D B->A C->A D->E E->D
출력 결과를 살펴보면, addEdge로 추가한 간선은 양쪽 노드 모두에 기록되어 양방향으로 표시되지만, addDirectedEdge로 추가한 A→D 간선은 A 쪽에만 기록되어 D→A로는 이동할 수 없습니다. 이처럼 인접 리스트 기반의 그래프 구현은 간선의 방향성과 가중치 정보를 손쉽게 확장할 수 있어, 다익스트라 알고리즘이나 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 등 다양한 그래프 알고리즘의 기반으로 활용하기 좋습니다.