[CDS] chapter 10 : 그래프 ①

1. 그래프 개념

그래프(graph)는 객체들 사이의 관계를 표현할 수 있는 자료구조이다. 이전에 공부했던 트리는 계층적인 자료를 표현하는데 적합한 자료구조인데, 결국 이 트리는 그래프의 특수한 한 형태라고 볼 수 있다. 좀 더 엄밀하게 정의하면 그래프는 정점(vertex)과 간선(edge)들의 유한 집합이고, 트리는 사이클이 없는 연결 그래프이다.

https://medium.com/@gwakhyoeun/til-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-graph-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-6f92fd87a0bd

그래프에서는 많은 용어들이 나오는데, 이하에서 정리하고 넘어가자.

• 부분 그래프 : 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 말한다.
• 완전 그래프 : 그래프의 모든 정점이 서로 연결되어 있는 그래프이다. 
• 정점의 차수 : 어떤 정점과 간선에 의해 직접 연결된 정점을 인접 정점이라 하고, 이 인접 정점의 수를 차수라 한다.
• 경로와 사이클 : 간선이 존재하는 정점의 나열이 경로이다. 반복되는 간선이 없으면 단순 경로이고, 단순 경로의 시작 정점과 종료 정점이 동일한 경로를 사이클이라고 한다. 
• 무방향 그래프와 방향 그래프 : 간선에 방향성이 존재하는 그래프는 방향 그래프이다.
• 가중치 그래프(=네트워크) : 간선의 역할이 두 정점간 연결유무 뿐 아니라 연결 강도까지 나타낸 그래프이다.
• 연결 그래프 : 무방향 그래프에서 모든 정점쌍에 대하여 항상 경로가 존재한다면 연결 그래프이다. 방향 그래프에서는 약한 연결(방향성 무시했을때 연결된 경우)과 강한 연결이라는 두 가지 개념이 존재하게 된다.

2. 그래프의 표현

(1) 인접  행렬

https://cinux.tistory.com/9

인접 행렬은 정점들을 행과 열로 놓고 두 정점 사이에 간선이 존재하면 1, 존재하지 않으면 0으로 표현하는 2차원 배열이다. 정점의 수가 n이라면 n * n의 2차원 배열이 된다. 일반적으로 상정하는 그래프는 자체 간선이나 중복된 간선을 허용하지 않기 때문에, 그림과 달리 대각선은 보통 0으로 채워지게 된다. 또한 무방향 그래프의 경우 그 인접 행렬은 대칭행렬이 된다.

 

인접 행렬에 의한 그래프 표현은 다음과 같은 장단점이 있다.

• 장점 : 정점 u와 정점 v를 연결하는 간선의 존재 여부는 M[u][v]의 값을 조사하면 알 수 있으므로 O(1)로 확인 가능
• 장점 : 구현이 간단함
• 단점 : 공간복잡도가 항상 O(V^2)이므로 간선이 적은 희소 그래프에서는 공간 낭비가 큼

(2) 인접 리스트

https://cinux.tistory.com/10

인접 리스트는 각 정점에 인접한 정점들을 연결 리스트로 표시한 것으로, 다음과 같은 장단점이 있다.

• 장점 : 공간복잡도가 O(V + E)로 효율적
• 장점 : 탐색 시 연결된 장점만 순회하게 됨
• 단점 : 특정 간선 존재 여부 확인은 O(정점의 차수)가 됨

3. 그래프 탐색

그래프에서 가장 기본적인 연산인 그래프 탐색은 하나의 정점에서 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 그래프 탐색 방법에는 깊이 우선 탐색(DFS, depth first search)과 너비 우선 탐색(BFS, breadth first search) 두 가지가 있다. 두 방법 모두 시간복잡도는 O(V + E) 가 된다.

https://suminpixel.tistory.com/33

(1) 깊이 우선 탐색

깊이 우선 탐색은 한 정점에서 시작하여 아직 방문하지 않은 인접 정점으로 가능한 깊이까지 재귀적으로 이동하고, 더 이상 방문할 수 없을 경우 직전 정점으로 역추적하여 탐색을 하는 방식이다. 이러한 특성상 깊이 우선 탐색은 재귀 함수 또는 스택을 사용하여 구현하게 된다.

(2) 너비 우선 탐색

너비 우선 탐색은 한 정점에서 시작하여 해당 정점에 인접한 모든 정점을 우선적으로 방문한 뒤, 방문한 정점들의 인접 정점들을 차례로 방문해나가는 방식이다. 너비 우선 탐색은 큐를 사용하여 구현한다.

 

너비 우선 탐색은 깊이 우선 탐색과 달리 그 특성상 경로 최적성을 보장한다. 즉, 시작 정점에서 어떤 정점까지 도달하는 경로 중 가장 짧은 경로를 정확하게 찾아낼 수 있다.