그래프 (Graph)와 DFS/BFS

오늘은 알고리즘 문제를 풀 때 정말 흔히 보이는 <그래프>에 대하여 알아보겠습니다.

DFS, BFS, 다익스트라, 스패닝 트리 등 정말 다양한 문제에서 등장하는 것이 그래프죠.

​

1. 그래프란 ?

가장 기본적인 정의는 정점(Vertex)와 간선(Edge)의 집합입니다.

여기서 간선은, 두 정점을 이어주는 역할을 합니다.

자기자신을 이을 수도 있고, 간선에 방향이 있기도 하고 없기도 하며, 가중치가 있기도 하고 없기도 하는 등 아주

다양한 형태의 그래프가 있습니다.

위의 그래프는 1,2,3,4,5,6의 총 6개의 정점으로 이루어져 있고,

{(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)} 의 총 7개의 간선으로 이루어져 있다고 불 수 있겠습니다.

V(정점의 집합) = {1, 2, 3, 4, 5, 6}

E(간선) = {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)}

​

2. 그래프의 종류

2-1. 무방향 그래프 (Undirected Graph)

가장 기본이 되는 그래프입니다.

가장 큰 특징으로는 간선의 방향이 없다는 점, 어느 정점에서든 다른 정점으로 이동 가능하다는 점이 있겠습니다.

위의 그림처럼 A, B, C, D, E 정점이 모두 이어져 있고 무방향 그래프이므로 어느 정점에서든 다른 어떤 정점으로도 이동이 가능합니다.

​

2-2. 방향 그래프 (Directed Graph)

무방향 그래프가 있다면, 유방향 그래프도 있겠죠? 그게 바로 방향 그래프입니다!

방향 그래프는 무방향 그래프와는 달리, 간선에 방향이 주어져서 어느 정점에서 다른 정점으로의 이동이 제한된다는 점이 있습니다.

또한 방향 그래프에서도 양방향 간선이 존재 가능한데, 이때는 간선을 양쪽 방향으로 나누어 2개의 간선으로 표현합니다. 저희가 문제를 풀게 되면 흔히 보는 그래프죠.

저는 보통 나가는 간선은 Indgree, 들어오는 간선은 Outdegree 라는 변수명을 붙여줍니다.

​

2-3. 가중치 그래프 (Weighted Graph)

가중치 그래프의 특징은 말 그대로 간선들에 가중치가 존재한다는 점입니다. 이 가중치의 양으로 비용(weight), 두 정점 사이의 거리(distance), 한번에 이동 가능한 최대 양인 대역폭(bandwitch) 등 다양한 값들이 문제에 등장합니다. 또한, 종종 방향성을 가지는 가중치 그래프까지 등장하기도 하죠.

2-4. 멀티 그래프(MultiGraph)

멀티 그래프는 똑같은 쌍(A,B) 사이에 간선이 여러 개 존재 가능한 그래프입니다.

정점의 입장에서 반대쪽 정점이 같은 간선이 여러 개 존재 가능한데, 따라서 자기 자신으로 돌아오는 (A,A) 같은 간선도 존재할 수 있습니다.

​

3. 그래프의 활용

3-1. DFS (Depth-First Search)

그래프의 활용이라면 대표적으로 알고리즘의 가장 친근한 친구라고 볼 수 있는 DFS와 BFS 알고리즘이 있겠죠.

DFS 알고리즘은 깊이 우선 탐색 알고리즘으로, 말 그대로 한 우물만 깊게 파다가 막히면 그제서야 돌아가서 다른 우물을 파는 성향이 있는 알고리즘입니다.

​

1. 정점 하나를 선택

2. 그 정점의 아직 방문하지 않은 인접한 정점 중 하나를 방문

3. 이미 방문한 정점은 방문하지 않음.

위 그림같은 그래프가 있다면, DFS 알고리즘을 사용 시

0->1->3->4->5->2->6->7->8 의 순서로 방문하게 될 것입니다.

이런식으로 반복문을 통하여 아래에 방문 가능한 간선이 더 있는지 확인하고 더 이상 방문 가능한 정점이 없다면 빠져나오는 것이 DFS 입니다.

​

3-2. BFS (Breath-First Search)

DFS의 베스트 프렌드인 BFS 입니다.

BFS는 너비 우선 탐색으로, DFS가 한 우물만 깊게 파다가 끝을 보고 나서 다른 곳으로 옮기는 것에 반해 BFS는 모든 곳을 똑같이 조금씩 조금씩 파냅니다.

​

1. 정점 하나를 선택

2. 선택한 정점과 인접한 정점들부터 무조건 다 방문함.

위 그림같은 그래프가 있다면, BFS 알고리즘을 사용 시

0->1->2->3->4->6->8->4->7 의 순서로 방문하게 될 것입니다.

BFS 알고리즘은 이런식으로 큐에 하나씩 넣어준 다음, 인접한 정점들을 하나씩 빼주도록 구현하면 됩니다.

​