Algorithm : Graph Algorithm (1)

Nekoder

이번에는 graph theory에서 자주 등장하는 문제들을 다룰 예정입니다. 실제로 실행속도를 올리는 데에 자료 구조 선택의 역할이 굉장히 중요합니다. 이번 장에서는 그래프로 변환가능한 실제 문제, 일반적인 그래프 문제를 해결하는 알고리즘, 적절한 자료 구조 선택이 알고리즘 실행 시간에 미치는 영향, DFS(Depth-First Search) 까지 알아보는 시간을 가져보겠습니다.

 

그리고 이번 포스팅 부터는 공간 복잡도도 다룹니다. 표기는  time compelxity와 같이 Big-O 를 사용하지만 개념이 다릅니다. 

Space Complexity

공간 복잡도(space complexity)는 알고리즘이나 데이터 구조가 실행할 때 사용할 메모리 양을 분석하는 걸 말합니다.

쉽게말해, 입력이 커짐에 따라서 메모리(공간)를 얼마나 사용하냐? 입니다.

 

1. 재귀(recursion)

재귀에서는 공간 복잡도에 큰 영향을 미칩니다. 재귀 함수는 우선 호출될 때마다, 로컬 변수 + 리턴 주소 + 실행 컨텍스트가 스택에 쌓입니다. 이게 Stack overflow로 이어질 위험도 있기에 조심해야 합니다.

리턴 주소 : 함수 실행 종료 후 돌아갈 주소.

실행 컨텍스트(execution context) : 현재 함수의 상태(스코프, 포인터 등)를 추적하기 위한 추가 정보.

 

2. 자료 구조 (지역변수 / 배열 / 리스트 등)

알고리즘 내에서 생성하고 사용하는 모든 메모리 요소는 공간 복잡도에 포함됩니다. 왜냐하면 이건 말 그대로 알고리즘이 직접 차지하는 공간이기 때문에, 동적으로 할당되는 배열, STL 컨테이너, 해시맵 등 도 모두 포함됩니다.

추가로 입력 공간과 출력 공간도 있는데 입력은 default가 제외고, 출력은 너무 커지면 포함된다 라고 일단 간략하게 설명하겠습니다.

---

Graph

---

graph는 set of Vertices(정점의 집합) 와 정점 쌍들을 연결하는 set of Edges(간선의 집합) 로 구성됩니다.

\( G = (V, E) \)처럼 정의되고, V는 set of Vertices, E는 set of Edges 입니다.

각 Edge는 \( (v, w) \) 형태의 쌍을 갖고  \( (v, w) \)  는 집합 V에 속합니다. 만약 이 쌍  \( (v, w) \)  가 순서가 없는 경우, 해당 그래프는 undirected graph(무방향 그래프) 라고 부릅니다. 반대로 순서가 있을 경우에는 directed graph(방향 그래프) 이고, edge는 v에서 w로 향합니다.

쉽게 말하면 무방향 그래프는 (A ↔ B) 관계이고, 방향 그래프  (A → B) 관계 입니다.

 

그래프에서 path(경로)는 아래와 같은 정점들의 순서열입니다.

\( w_1, w_2, \ldots, w_N \)에서 \( (w_i, w_{i+1}) \in E \)이고, 모든 i에 대해서 E의 원소가 된다는 게 성립이 되어야 합니다.

이 경로의 길이는 경로 위에 있는 edge의 수입니다. (N - 1)

simple path는 시작점과 끝점은 같아도 되지만, 나머지 모든 vertice가 중복되지 않는 path입니다. 그렇기에 cycle을 포함한 단순한 path도 존재할 수 있습니다. 여기서 말하는 cycle은 path가 1 이상이고, 시작점과 끝점이 같은 path를 말합니다. 

DAG(Directed Acyclic Graph)는 방향 그래프이면서 cycle이 없는 그래프를 말합니다.(비순환 방향 그래프)

\( v \rightarrow v \) 형태로 자기 자신을 향하는 edge를 loop라고 합니다. 

마지막 개념은 연결성인데

• connected : 모든 정점 쌍이 연결됨(무방향),
• strongly connected: 방향 그래프에서 모든 정점이 path를 가짐.
• weakly connected: 방향성 무시하면 연결됨.
• complete graph: 모든 V(set of vertice) 사이에 간선이 존재.(실제로는 선이 너무 많아서 dense라고도 부름)

---

Representation

---

1부터 시작해서 vertice에 번호를 매긴다고 해봅시다. 아래 그림은 7 vertices 와 12 edges 로 구성된 그래프입니다.

A directed graph

인접 행렬(Adjacency Matrix)

그래프를 간단한 2차원 배열을 사용하여 \( A[u][v] \) 로 표현하는 방식을 인접 행렬이라고 합니다. 이러한 인접 행렬을 사용할 때,

edge (u, v)가 존재하면 : true / 1 or weight(가중치) 값 저장.

edge가 없으면 : false / 0 or sentinel 값( ∞, −∞, 0 등) 사용

장점

구현이 매우 단순하고 두 정점 \(u, v \) 간 간선이 존재하는 지 여부를 \(O(1)\) 시간에 확인할 수있습니다.

단점

Space complexity(공간 복잡도)가 \( O(|V|^2) \) 입니다. 그래서 sparse에는 비효율적입니다. 그럼에도 적합하게 사용하는 경우가 있는데,

1. 밀집 그래프(dense) 에 적합합니다. \(|E| = \Theta(|V|^2) \)

2. 정점 간 간선 연결 여부를 매우 빠르게 확인해야 하는 상황에도 적합합니다.

인접 행렬은

모든 정점끼리 전부 한 번씩 연결됐는지 표로 나타내는 방식입니다.

정점이 \(n\) 개 라면, \(n x n\) 짜리 2차원 배열(표)를 만듭니다.

\(A[i][j]\) 는 정점\(i\)에서 정점 \(j\)로 가는 간선이 있는지 표시합니다.

있으면 : `true`.`1`, 또는 `weight`(가중치)

없으면: `false`. `0`, 또는 ` ∞` 같은 특별한 값.

정점 수가 많으면 매우 많은 공간을 사용합니다.

어떤 정점 사이에 간선이 있는지 확인하는 속도는 빠릅니다.

구현도 쉽습니다.

 

인접 리스트(Adjacency List)

보통 이런 구조를 사용합니다.

`unordered_map<string, vector<string>> adjList;`

각 정점마다 인접한 정점들의 리스트를 따로 저장하는 개념입니다.

장점

Space complexity : \(O (|V| + |E|) \rightarrow \) 실제 데이터 크기만큼만 메모리 사용.

가중치가 있을 경우, 리스트에 weight 정보도 함께 저장 가능

특정 정점 \(v\)의 인접 정점들을 탐색할 때 매우 효율적

단점

정점 간 존재 여부 조회 시 \(O(k) \) 시간 필요합니다.(\(k = \)인접 정점 수)

구현이 약간 더 복잡합니다.

인접 리스트는

필요한 간선만 기록하는 방식입니다. 정점마다 연결된 정점 목록만 저장하여,

정점이 \(n\) 개면, 각 정점마다 리스트를 하나씩 갖습니다.

그 리스트에는 해당 정점에서 연결된 다른 정점들만 들어 있습니다.

 

이렇게 되면 간선이 적으면 공간을 아낄 수 있습니다.

한 정점과 연결된 정점들만 확인하면 되기 때문에 순회도 빠릅니다.

하지만 \(A[i][j]\) 같은 빠른 접근은 안됩니다.

 

결국 알고리즘 요구에 따른 성능 차이는 

인접 행렬 : 전체 열을 훑어야 하므로 \(O(|V|)\)

인접 리스트 : 리스트 스캔 \(\rightarrow O(deg(v)) \)  훨씬 빠릅니다.