그래프(Graph)
연결 관계를 표현하기 위해 사용. 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조.
Node와 Node 사이에 Edge가 있는 경우, 서로 인접해있다고 표현할 수 있다.
Node와 Node를 잇는 길을 경로라고 한다. 경로 안에 있는 Edge의 수는 거리가 된다. 이때, 거리가 최소가 되는 경로를 최단 경로라고 한다.
특정 Node에서 시작해 같은 Node로 끝나는 경우를 사이클(Cycle)이라고 한다.
하나의 Node에 인접해있는 Node의 수를 차수(degree)라고 한다.
그래프 종류
1. 무방향 그래프(Undirected Graph)
무방향 그래프의 간선은 간선을 통해서 양방향으로 갈 수 있다.
정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B)는 (B, A) 동일
2. 방향 그래프(Directed Graph)
간선에 방향성이 존재하는 그래프
A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B>는 <B, A>는 다름
진입(입력) 차수(in-degree): 외부에서 오는 간선의 수 (내차수 라고도 부름)
진출(출력) 차수(out-degree): 외부로 향하는 간선의 수 (외차수 라고도 부름)
가중치 그래프(Weighted Graph)
간선에 비용이나 가중치가 할당된 그래프 ‘네트워크(Network)’ 라고도 한다.
가중치 그래프에서는 경로 안에 있는 Edge의 수가 아닌 가중치의 합이 거리가 된다.
연결 그래프(Connected Graph)
무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프
비연결 그래프(Disconnected Graph)
무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
사이클(Cycle)
단순 경로의 시작 정점과 종료 정점이 동일한 경우
단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우
비순환 그래프(Acyclic Graph)
사이클이 없는 그래프
완전 그래프(Complete Graph)
그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프, 무방향 완전 그래프
정점 수 = n이면 간선의 수: n * (n-1) / 2
그래프 구현
그래프를 구현하는 대표적인 방법은 인접 행렬과 인접 리스트가 있다.
인접 행렬 (Adjacency Matrix)
2차원 배열로 정점간의 간선 존재 여부를 1과 0으로 저장하는 방법이다.
구현이 빠르고, 검색 속도가 O(1)이다.
생성 시 O(n^2)의 시간 복잡도를 갖는다.
무조건 2차원 배열 이상의 공간이 필요하기에, 공간 낭비가 심하다.
class Graph {
constructor() {
this.matrix = [];
}
addNode() {
const currentLength = this.matrix.length;
for(let i=0; i<currentLength; i++) {
this.matrix[i].push(0);
}
this.matrix.push(new Array(currentLength+1).fill(0));
}
contains(node) {
return !!this.matrix[node];
}
addEdge(from, to) {
const currentLength = this.matrix.length;
if(from > currentLength || to > currentLength || from < 0 || to < 0) return;
this.matrix[from][to] = 1;
}
removeEdge(from, to) {
if(from > currentLength || to > currentLength || from < 0 || to < 0) return;
this.matrix[from][to] = 0;
}
hasEdge(from, to) {
return !!this.matrix[from][to];
}
}인접 리스트 (Adjacency Matrix)
모든 정점에 연결된 정점들을 리스트로 표현하는 방식이다.
필요한 만큼만 공간을 사용하기 때문에, 공간 낭비가 적다.
검색 속도가 O(n)으로 인접행렬(Adjacency Matrix)에 비해 느리다.
구현이 비교적 어렵다.
무방향 그래프에서 (a, b) 간선은 두 번 저장된다.
정점의 수: N, 간선의 수: E인 무방향 그래프의 경우 -> N개의 리스트, N개의 배열, 2E개의 노드가 필요
인접하는 정점이 두 개 이상일 경우, 리스트에 담을 때 순서는 중요하지 않다. 단, 우선 순위를 고려해 구현하여 정렬할 수는 있다. 만약, 우선 순위를 다뤄야하는 경우라면 인접리스트가 아니라 queue, heap를 사용하는 것이 합리적이다.
class Graph {
constructor() {
this.nodes = {};
}
addNode(node) {
this.nodes[node] = this.nodes[node] || [];
}
removeNode(node) {
if(this.contains(node)) {
while (this.nodes[node].length > 0) {
this.removeEdge(this.nodes[node][0], node);
}
delete this.nodes[node];
}
}
contains(node) {
return !!this.nodes[node];
}
addEdge(from, to) {
if(!this.contains(from) || !this.contains(to)) return;
if(!this.hasEdge(from, to)) this.nodes[from].push(to);
}
removeEdge(from, to) {
if(!this.contains(from) || !this.contains(to)) return;
if(this.hasEdge(from, to)) {
const index = this.nodes[from].indexOf(to);
this.nodes[from].splice(index, 1);
}
}
hasEdge(from, to) {
if(!this.contains(from)) return false;
return !!this.nodes[from].includes(to);
}
}행렬 vs 리스트
그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 -> List
노드에 인접한 노드들을 쉽게 찾을 수 있다. 그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알 수 있다.
간선의 존재 여부와 정점의 차수는 정점 i의 리스트에 있는 노드의 수 즉, 정점 차수만큼의 시간이 필요
그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 의 경우 -> 행렬
두 정점을 연결하는 간선의 존재 여부 (M[i][j])를 O(1) 안에 즉시 알 수 있다.
정점의 차수는 O(N) 안에 알 수 있지만, 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다.
그래프에 존재하는 모든 간선의 수는 O(N^2) 안에 알 수 있다.
그래프 탐색
하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것
깊이 우선 탐색(Depth-First Search)
넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것.
인접 노드 하나를 방문한 후 다음은 그 인접 노드의 인접 노드를 방문하여 그 방향으로 최대한 깊게 먼저 탐색하는 방법이다. 재귀와 스택(Stack)을 이용해 구현할 수 있다.
노드를 방문하면 Stack에 인접 노드들을 추가하는 방법으로 이루어지고, 이미 방문한 노드는 추가하지 않는다.
모든 노드를 방문하는 경우에 사용한다.
전처리: O(V) -> 모든 노드를 다 돌면서 visited 변수를 False로 만든다.
큐에서 노드 넣고 빼기: O(V) -> 최대 V개의 노드들이 큐에 들어갔다 나온다.
인접한 노드들을 도는데 걸리는 시간 : O(E) -> 엣지 수가 E이므로 E에 비례하는 만큼 실행된다.
O(2V+E) 즉, O(V+E)의 시간 복잡도가 걸린다.
너비 우선 탐색(Breadth-First Search)
깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것.
인접 노드들을 방문할 때 그 노드의 인접 노드들을 우선적으로 전부 방문하여 탐색 범위를 점점 넓히며 탐색하는 방법이다. 큐(Queue)를 이용해 구현할 수 있다.
노드를 방문하면 Queue에 인접 노드들을 추가하는 방법으로 이루어지고, 이미 방문한 노드는 추가하지 않는다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
전처리: O(V) -> 모든 노드를 다 돌면서 visited 변수를 False로 만든다.
큐에서 노드 넣고 빼기: O(V) -> 최대 V개의 노드들이 큐에 들어갔다 나온다.
인접한 노드들을 도는데 걸리는 시간 : O(E) -> 엣지 수가 E이므로 E에 비례하는 만큼 실행된다.
O(2V+E) 즉, O(V+E)의 시간 복잡도가 걸린다.
최단 경로
두 노드 사이 경로 중 가장 거리가 짧은 경로
BFS
탐색을 위한 BFS에서 predecessor(특정 Node에 오기 직전 Node)변수를 추가해준다.
즉, predecessor는 해당 노드까지 오는 방법 중 가장 빠르게 올 수 있는 직전 Node를 알려준다.
Backtracking을 이용하여 도착 지점의 predecessor를 이용하여 출발 지점까지 되돌아간다.
비가중치 그래프에서 최단 경로를 구할 수 있다.
Dijkstra
가중치 그래프에서 최단 경로를 구하기 위함. 단, 음의 간선이 없는 경우에만 가능하다. distance, predecessor, complete 변수를 사용해준다.
distance : 특정 노드까지의 최단 거리 예상치 (현재까지 계산된 최단 거리)
predecessor : 현재까지 최단 경로에서 바로 직전 노드
complete : 노드까지의 최단 경로를 찾았음을 표시
모든 노드의 distance를 infinity, predecessor를 none으로 설정한 뒤, 현재 distance보다 짧은 경로를 발견할 시 distance와 predecessor를 relax 해준다. 해당 노드의 인접 노드를 모두 확인했을 시 complete를 true로 바꾸어준다.
참고 자료
[자료구조] 그래프(Graph)란
[Kotlin] Graph
[Javascript 자료구조] 그래프(Graph)
[JavaScript-자료구조] Graph
