그래프와 탐색

그래프(graph)는 정점(vertex)과 정점을 잇는 간선(edge)으로 '여럿과 여럿'의 관계를 나타내는 비선형 구조입니다. 트리는 위아래가 정해져 있고 돌아오는 길이 없지만, 지하철 노선도나 친구 관계처럼 아무 쪽으로나 이어지고 돌아오는 길이 있는 관계는 그래프로 담습니다. 돌아오는 길이 있어서 그래프를 탐색할 때는 이미 간 정점을 다시 가지 않게 챙겨야 하고, 어느 정점부터 가느냐에 따라 깊이 우선 탐색과 너비 우선 탐색으로 나뉩니다. 아래 그림은 같은 그래프에서 깊이 우선 탐색이 한 갈래를 끝까지 따라가고, 너비 우선 탐색이 가까운 정점부터 퍼지는 모습을 보입니다.

1정점과 간선 — 방향과 최대 간선 수

간선에 방향이 없어 양쪽으로 오갈 수 있으면 무방향 그래프(undirected graph), 간선이 화살표라 한쪽으로만 가면 방향 그래프(directed graph)입니다. 한 정점에 이어진 간선의 수를 그 정점의 차수라 합니다. 그림의 B는 A·C·E와 이어져 차수가 3입니다. 출발한 정점으로 돌아오는 길을 사이클(cycle)이라 합니다. 그림의 A → B → E → D → A가 사이클입니다.

모든 정점 쌍이 간선으로 이어진 그래프를 완전 그래프(complete graph)라 하고, 이때 간선 수가 가장 많습니다.

정점마다 나머지 n − 1개와 이어집니다. 무방향은 한 간선을 양 끝에서 두 번 세게 되니 2로 나누고, 방향은 쌍마다 오는 길과 가는 길이 따로라 나누지 않습니다.

2깊이 우선 탐색 — 한 갈래를 끝까지

깊이 우선 탐색(DFS, Depth First Search)은 갈 수 있는 데까지 한 갈래로 깊이 들어가고, 막히면 지나온 길을 거꾸로 밟아 아직 안 간 이웃이 있는 정점으로 돌아갑니다. 지나온 길을 마지막에 지난 정점부터 거꾸로 꺼내므로 스택(스택과 큐)을 씁니다.

시험 문제는 보통 '이웃이 여럿이면 알파벳·번호가 앞선 정점부터'를 약속으로 둡니다. 그림도 이 약속을 따릅니다. 문제에 다른 약속이 있으면 그것을 따릅니다.

3너비 우선 탐색 — 가까운 정점부터

너비 우선 탐색(BFS, Breadth First Search)은 출발 정점의 이웃을 모두 방문한 뒤, 그 이웃들의 이웃으로 넓혀 갑니다. 먼저 찾은 정점의 이웃을 먼저 넓혀야 하므로, 다음에 갈 정점을 큐(스택과 큐)에 넣었다가 넣은 차례대로 꺼냅니다. 그래서 출발 정점에서 간선 하나 거리, 둘 거리, 셋 거리의 차례로 방문합니다.

4신장 트리 — 정점은 모두, 사이클은 없이

신장 트리(spanning tree)는 그래프의 정점을 모두 잇되 사이클이 없도록 간선을 골라 만든 트리입니다. 정점이 n개면 간선은 n − 1개입니다. 그림의 그래프는 정점 6개에 간선이 6개라, 사이클을 끊는 간선 하나를 빼면 신장 트리가 됩니다. 탐색이 지나간 간선만 남기면 신장 트리가 되므로, 한 그래프에 신장 트리가 여럿 있을 수 있습니다. 간선마다 비용이 붙어 있을 때 비용 합이 가장 작은 신장 트리를 최소 비용 신장 트리라 합니다.

예제

그림의 그래프를 A에서 출발해 탐색합니다. 이웃은 A: B·D, B: A·C·E, C: B, D: A·E, E: B·D·F, F: E입니다.

깊이 우선 탐색 — 스택으로

F에서 다시 막히고, 스택을 거꾸로 꺼내 가는 동안 남은 이웃이 없어 탐색이 끝납니다.

너비 우선 탐색 — 큐로

꺼낸 차례가 방문 차례입니다 — A B D C E F. 큐는 넣은 차례대로 꺼내므로, 넣은 차례를 방문 차례로 보아도 같습니다. D의 이웃 E는 B를 꺼낼 때 이미 큐에 들어가 다시 넣지 않습니다.

시험 포인트

• 필기: 정점 n개의 최대 간선 수는 무방향 n(n − 1)/2개, 방향 n(n − 1)개입니다. 깊이 우선 탐색은 한 갈래를 끝까지 가고 막히면 되돌아가며 스택을 쓰고, 너비 우선 탐색은 가까운 정점부터 넓혀 가며 큐를 씁니다. 두 탐색이 쓰는 구조를 맞바꾼 보기가 함정입니다. 탐색 차례는 이웃이 여럿일 때 알파벳·번호가 앞선 정점부터 가는 약속으로 풉니다. 신장 트리는 모든 정점을 사이클 없이 잇는 트리라 간선이 n − 1개입니다.
• 실기: 탐색 차례를 정점 이름의 차례로 씁니다. 이름은 깊이 우선 탐색(DFS, Depth First Search)·너비 우선 탐색(BFS, Breadth First Search)·신장 트리(Spanning Tree)로 씁니다.

확인 문제

1. 정점이 5개인 방향 그래프가 가질 수 있는 간선은 최대 몇 개일까요? 같은 방향의 간선은 한 쌍에 하나뿐이고, 자기 자신으로 가는 간선은 없습니다.

• ① 4개
• ② 10개
• ③ 20개
• ④ 25개

2. 다음 (가)~(다)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 약어가 있으면 약어와 원어를 모두 씁니다. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 미로에서 한 길을 막다른 곳까지 따라가고, 막히면 마지막 갈림길로 돌아와 아직 안 간 길로 들어갑니다.
• (나) 소문을 퍼뜨릴 때, 출발한 사람과 바로 아는 사람에게 모두 알린 뒤에야 그 사람들이 아는 사람에게 알립니다.
• (다) 도시 여섯을 모두 오갈 수 있게 하되, 같은 도시로 되돌아오는 고리가 없도록 도로 다섯 개만 남겼습니다.

3. 그림의 그래프에서 출발 정점을 E로 바꿨습니다. 깊이 우선 탐색과 너비 우선 탐색의 방문 차례를 각각 쓰세요. 이웃이 여럿이면 알파벳이 앞선 정점부터 갑니다. 답을 끝까지 쓴 뒤 정답을 펼치세요.