1. Graph

그래프란 일부 쌍들이 연관되어 있는 객체 집합 구조를 말한다. 그래프는 정점 or 노드(vertex)과 간선(edge)으로 이루어져있는데, 정점간의 관계를 표현한 조직도라고 볼 수 있다.

---

2. 그래프의 종류

무방향 그래프 vs 방향 그래프

무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 간선을 통해서 양 방향으로 갈 수 있다.

방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프이다. 간선의 방향으로만 이동할 수 있다.

연결 그래프 VS 비연결 그래프

연결 그래프는 무방향 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 그래프이다.

비연결 그래프는 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프이다.

순환 그래프 VS 비순환 그래프

순환 그래프는 단순 경로의 시작점과 종료점이 같은 그래프이다.

비순환 그래프는 단순 경로의 시작점과 종료점이 같지 않은 그래프이다.

가중치 그래프

가중치 그래프는 두 정점을 이동할때 비용이 드는 그래프이다.

완전 그래프

완전 그래프는 모든 정점이 간선으로 연결되어 있는 그래프이다. 완전 그래프의 정점의 수가 v개 라면 간선의 수는 v*(v-1)/2 개 이다.

---

3. 그래프의 구현

그래프를 구현하는 방법에는 인접행렬(Adjacency Materix)와 인접리스트(Adjacency List)방식이 있다. 두개의 구현 방식은 각각의 상반된 장단점을 가지고 있으며 보통 인접 리스트 방식을 많이 사용한다.

위의 그래프로 구현해보자.

인접 리스트 (Adjacency List)

인접 리스트는 리스트를 사용하는 방식이다.

• 장점
  • 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 리스트에 쉽게 접근하여 O(E) 시간안에 연결 정보를 탐색할 수 있다.
  • 필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적다.
• 단점
  • 특정 두 점이 연결되었는지 확인하려면 연결 리스트를 계속 따라가야 하므로 인접행렬에 비해 시간이 오래 걸린다.
• 시간복잡도

노드의 개수가 V, 간선의 개수가 E인 그래프를 생각해보자. 인접 리스트 이용할 때는 간선의 개수만큼인 O(E)만큼의 메모리 공간이 필요하다. 특정한 노드 A에서 다른 노드 B로 이어진 간선의 비용은 O(V)의 시간으로 알 수 있다.

Node 추가 : O(1)

이중연결리스트 꼬리 nextNode로 지정하기 때문에 상수 시간만큼 소요된다.

Node 삭제 : O(V+E)

노드를 삭제하면 삭제된 공간을 채우기 위해 다시 색인하는 과정이 필요하므로 노드, 정점의 개수를 합한 만큼의 시간이 소요됩니다.

Edge 추가 : O(1)

Edge 삭제 : O(E)

최악의 상황은 한 줄로 노드가 연결되어 있는 경우로 삭제하기 위해 마지막 Edge까지 탐색해야 한다.

인접 행렬 (Adjacency Matrix)

인접 행렬은 2차원 배열을 활용한다. VxV 크기의 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 1이면 i에서 j로의 간선이 있다는 뜻이다.

• 장점
  • 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1) 의 시간 복잡도면 가능하다.
• 단점
  • 모든 정점에 대해 간선 정보를 대입해야 하므로 O(²) 의 시간복잡도가 소요됩니다
  • 무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비된다.
• 시간복잡도

노드의 개수가 V, 간선의 개수가 E인 그래프를 생각해보자. 인접행렬을 이용하면 간선 정보를 저장하기 위해서 $O(v^{2})$ 만큼의 메모리 공간이 필요하다. 특정한 노드 A에서 다른 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다.

Node 추가 : O(V^2)

행과 열을 모두 추가해야 하므로 노드 개수의 제곱만큼의 시간이 필요합니다. 추가로 새로 생긴 행과 열에 대한 각 셀을 채워야 한다.

Node 삭제 : O(V^2)

Edge 추가 : O(1)

Edge 추가는 특정 셀의 값만 0에서 1로 변경하면 되므로 상수 시간만큼 소요된다.

Edge 삭제 : O(1)

Edge 삭제는 특정 셀의 값만 1에서 0으로 변경하면 되므로 상수 시간만큼 소요된다.

활용

인접 리스트는 그래프의 간선 수가 적을 때 유리하며 다익스트라 최단 경로 알고리즘에서 사용한다. 인접 행렬은 그래프에 간선이 많이 존재할 때 유리하며 플로이드 워셜 알고리즘에서 사용한다.

---

4. 그래프 탐색

그래프 순회는 그래프 탐색이라고도 하며 그래프의 각 정점을 방문하는 과정을 말한다. 크게 깊이 우선 탐색, 너비 우선 탐색 알고리즘이 있다. 이 두가지는 Algorithm 파트에서 자세히 살펴볼 것이다.

너비 우선 탐색은 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법이다.

깊이 우선 탐색은 리프에 도달할 때까지 아래쪽으로 내려가면서 검새하는 방법이다. 리프에 도달해서 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤에 다시 자식 노드로 내려간다.

깊이 우선 탐색은 세 가지 방법으로 스캔한다.

전위순회 (preorder)

노드 방문 ➔ 왼쪽 자식 ➔ 오른쪽 자식

A ➔ B ➔ D ➔ H ➔ E ➔ I ➔ J ➔ C ➔ F ➔ K ➔ L ➔ G

중위순회 (inorder)

왼쪽 자식 ➔ 노드방문 ➔ 오른쪽 자식

H ➔ D ➔ B ➔ I ➔ E ➔ J ➔ A ➔ K ➔ F ➔ L ➔ C ➔ G

후위순회 (postorder)

왼쪽 자식 ➔ 오른쪽 자식 ➔ 노드 방문

H ➔ D ➔ I ➔ J ➔ E ➔ B ➔ K ➔ L ➔ F ➔ G ➔ C ➔ A