그래프란 무엇인가?
그래프(Graph)는 객체들의 집합에서 일부 객체 쌍이 연결선으로 이어진 관계를 시각적으로 표현한 자료구조입니다. 상호 연결된 객체들은 정점(vertex)이라 부르는 점으로 표현되고, 정점들을 잇는 연결선은 간선(edge)이라고 합니다.
형식적으로 그래프는 두 집합의 쌍 (V, E)로 정의됩니다. 여기서 V는 정점의 집합이며, E는 정점 쌍을 연결하는 간선의 집합입니다. 아래 그래프를 살펴보겠습니다.
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}핵심 용어 정리
수학적 그래프는 데이터 구조로 표현할 수 있습니다. 정점은 배열로, 간선은 2차원 배열로 나타낼 수 있는데요. 본격적인 구현에 앞서 반드시 알아야 할 핵심 용어를 먼저 익혀두겠습니다.
정점(Vertex) − 그래프의 각 노드를 정점이라고 합니다. 예시에서 라벨이 붙은 원 하나하나가 정점이며, A부터 G까지가 모두 정점에 해당합니다. 배열로 표현하면 A는 인덱스 0, B는 인덱스 1처럼 순서대로 식별할 수 있습니다.
간선(Edge) − 두 정점 사이를 잇는 경로 또는 선을 의미합니다. 예시에서 A→B, B→C로 이어지는 선들이 간선입니다. 2차원 배열로 표현하면 AB는 0행 1열의 값 1, BC는 1행 2열의 값 1로 나타내고, 연결되지 않은 조합은 0으로 유지합니다.
인접(Adjacency) − 두 정점이 간선으로 직접 연결되어 있으면 서로 인접(adjacent)하다고 말합니다. 예시에서 B는 A와 인접하고, C는 B와 인접한 관계입니다.
경로(Path) − 한 정점에서 다른 정점까지 이어지는 간선들의 순서를 뜻합니다. 예시에서 ABCD는 A에서 D로 향하는 경로를 나타냅니다.
자바스크립트 Graph 클래스 전체 구현
아래는 자바스크립트로 작성한 Graph 클래스의 전체 구현 코드입니다. 단순히 그래프를 만들고 출력하는 기능뿐 아니라, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS), 위상 정렬, 프림(Prim)과 크루스칼(Kruskal) 최소 신장 트리(MST), 다익스트라(Dijkstra) 최단 경로, 플로이드-워셜(Floyd-Warshall) 알고리즘까지 폭넓게 다룹니다.
const Queue = require("./Queue");
const Stack = require("./Stack");
const PriorityQueue = require("./PriorityQueue");
class Graph {
constructor() {
this.edges = {};
this.nodes = [];
}
addNode(node) {
this.nodes.push(node);
this.edges[node] = [];
}
addEdge(node1, node2, weight = 1) {
this.edges[node1].push({ node: node2, weight: weight });
this.edges[node2].push({ node: node1, weight: weight });
}
addDirectedEdge(node1, node2, weight = 1) {
this.edges[node1].push({ node: node2, weight: weight });
}
display() {
let graph = "";
this.nodes.forEach(node => {
graph += node + "->" + this.edges[node].map(n => n.node).join(", ") + "\n";
});
console.log(graph);
}
// 너비 우선 탐색(BFS)
BFS(node) {
let q = new Queue(this.nodes.length);
let explored = new Set();
q.enqueue(node);
explored.add(node);
while (!q.isEmpty()) {
let t = q.dequeue();
console.log(t);
this.edges[t].filter(n => !explored.has(n)).forEach(n => {
explored.add(n);
q.enqueue(n);
});
}
}
// 깊이 우선 탐색(DFS)
DFS(node) {
// 스택을 생성하고 시작 노드를 넣습니다.
let s = new Stack(this.nodes.length);
let explored = new Set();
s.push(node);
// 첫 번째 노드를 방문 처리합니다.
explored.add(node);
// 스택이 빌 때까지 반복합니다.
while (!s.isEmpty()) {
let t = s.pop();
// 스택에서 꺼낸 요소를 로그로 출력합니다.
console.log(t);
// 1. edges 객체에서 현재 노드와 직접 연결된 노드를 찾습니다.
// 2. 이미 방문한 노드는 제외합니다.
// 3. 방문하지 않은 노드를 방문 처리한 뒤 스택에 push합니다.
this.edges[t].filter(n => !explored.has(n)).forEach(n => {
explored.add(n);
s.push(n);
});
}
}
topologicalSortHelper(node, explored, s) {
explored.add(node);
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
s.push(node);
}
// 위상 정렬(Topological Sort)
topologicalSort() {
let s = new Stack(this.nodes.length);
let explored = new Set();
this.nodes.forEach(node => {
if (!explored.has(node)) {
this.topologicalSortHelper(node, explored, s);
}
});
while (!s.isEmpty()) {
console.log(s.pop());
}
}
// BFS를 활용한 최단 경로 탐색
BFSShortestPath(n1, n2) {
let q = new Queue(this.nodes.length);
let explored = new Set();
let distances = { n1: 0 };
q.enqueue(n1);
explored.add(n1);
while (!q.isEmpty()) {
let t = q.dequeue();
this.edges[t].filter(n => !explored.has(n)).forEach(n => {
explored.add(n);
distances[n] = distances[t] == undefined ? 1 : distances[t] + 1;
q.enqueue(n);
});
}
return distances[n2];
}
// 프림(Prim) 알고리즘으로 최소 신장 트리(MST) 구하기
primsMST() {
// MST를 담을 그래프를 초기화합니다.
const MST = new Graph();
if (this.nodes.length === 0) {
return MST;
}
// 첫 번째 노드를 시작 노드로 선택합니다.
let s = this.nodes[0];
// 우선순위 큐와 방문 집합을 생성합니다.
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
let explored = new Set();
explored.add(s);
MST.addNode(s);
// 시작 노드의 모든 간선을 가중치를 우선순위로 하여 큐에 추가합니다.
this.edges[s].forEach(edge => {
edgeQueue.enqueue([s, edge.node], edge.weight);
});
// 가장 작은 간선을 꺼내 새 그래프에 추가합니다.
let currentMinEdge = edgeQueue.dequeue();
while (!edgeQueue.isEmpty()) {
// 방문하지 않은 노드를 가진 간선을 찾을 때까지 계속 꺼냅니다.
while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
currentMinEdge = edgeQueue.dequeue();
}
let nextNode = currentMinEdge.data[1];
// 큐가 비어 방문하지 않은 요소를 반환하지 못할 수 있으므로 다시 확인합니다.
if (!explored.has(nextNode)) {
MST.addNode(nextNode);
MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
// 해당 노드의 모든 간선을 다시 큐에 추가합니다.
this.edges[nextNode].forEach(edge => {
edgeQueue.enqueue([nextNode, edge.node], edge.weight);
});
// 이 노드를 방문 처리합니다.
explored.add(nextNode);
s = nextNode;
}
}
return MST;
}
// 크루스칼(Kruskal) 알고리즘으로 최소 신장 트리(MST) 구하기
kruskalsMST() {
const MST = new Graph();
this.nodes.forEach(node => MST.addNode(node));
if (this.nodes.length === 0) {
return MST;
}
// 우선순위 큐를 생성합니다.
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
// 모든 간선을 큐에 추가합니다.
for (let node in this.edges) {
this.edges[node].forEach(edge => {
edgeQueue.enqueue([node, edge.node], edge.weight);
});
}
let uf = new UnionFind(this.nodes);
// 모든 노드를 탐색하거나 큐가 빌 때까지 반복합니다.
while (!edgeQueue.isEmpty()) {
// 구조 분해 할당으로 간선 데이터를 가져옵니다.
let nextEdge = edgeQueue.dequeue();
let nodes = nextEdge.data;
let weight = nextEdge.priority;
if (!uf.connected(nodes[0], nodes[1])) {
MST.addEdge(nodes[0], nodes[1], weight);
uf.union(nodes[0], nodes[1]);
}
}
return MST;
}
// 다익스트라(Dijkstra) 최단 경로 알고리즘
djikstraAlgorithm(startNode) {
let distances = {};
// 이전 노드에 대한 참조를 저장합니다.
let prev = {};
let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
// 시작 노드를 제외한 모든 노드의 거리를 무한대로 설정합니다.
distances[startNode] = 0;
pq.enqueue(startNode, 0);
this.nodes.forEach(node => {
if (node !== startNode) distances[node] = Infinity;
prev[node] = null;
});
while (!pq.isEmpty()) {
let minNode = pq.dequeue();
let currNode = minNode.data;
let weight = minNode.priority;
this.edges[currNode].forEach(neighbor => {
let alt = distances[currNode] + neighbor.weight;
if (alt < distances[neighbor.node]) {
distances[neighbor.node] = alt;
prev[neighbor.node] = currNode;
pq.enqueue(neighbor.node, distances[neighbor.node]);
}
});
}
return distances;
}
// 플로이드-워셜(Floyd-Warshall) 알고리즘
floydWarshallAlgorithm() {
let dist = {};
for (let i = 0; i < this.nodes.length; i++) {
dist[this.nodes[i]] = {};
// 기존 간선에는 가중치를 그대로 거리로 할당합니다.
this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
this.nodes.forEach(n => {
// 나머지 노드는 무한대로 설정합니다.
if (dist[this.nodes[i]][n] == undefined)
dist[this.nodes[i]][n] = Infinity;
// 자기 자신으로의 거리는 0으로 설정합니다.
if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
});
}
this.nodes.forEach(i => {
this.nodes.forEach(j => {
this.nodes.forEach(k => {
// i → k → j로 가는 경로가 i → j로 바로 가는 것보다 짧다면 값을 갱신합니다.
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
});
});
});
return dist;
}
}
class UnionFind {
constructor(elements) {
// 분리된 컴포넌트의 개수
this.count = elements.length;
// 연결된 컴포넌트를 추적합니다.
this.parent = {};
// 모든 요소의 부모를 자기 자신으로 초기화합니다.
elements.forEach(e => (this.parent[e] = e));
}
union(a, b) {
let rootA = this.find(a);
let rootB = this.find(b);
// 루트가 같다면 이미 연결되어 있는 상태입니다.
if (rootA === rootB) return;
// 항상 더 작은 루트를 가진 요소를 부모로 만듭니다.
if (rootA < rootB) {
if (this.parent[b] != b) this.union(this.parent[b], a);
this.parent[b] = this.parent[a];
} else {
if (this.parent[a] != a) this.union(this.parent[a], b);
this.parent[a] = this.parent[b];
}
}
// 노드의 최종 부모를 반환합니다.
find(a) {
while (this.parent[a] !== a) {
a = this.parent[a];
}
return a;
}
// 두 노드의 연결 여부를 확인합니다.
connected(a, b) {
return this.find(a) === this.find(b);
}
}