어떻게 그래프 위를 걷는 두 방법

한 점에서 출발

지난 레슨에서 그래프를 보았다. 점은 노드, 선은 엣지이고, 고리 없는 그래프가 트리였다.
이번에는 그 위를 걸어 본다. 걸으려면 먼저 어디서 출발할지 정해야 한다.
한 점을 고르면 바로 이어진 이웃부터 눈에 들어와요.

점을 눌러 출발점을 정해요. (출발점 = 파랑 · 바로 이어진 이웃 = 환하게)

출발점에서 한 발 가면 이웃에 닿고, 거기서 또 한 발 가면 이웃의 이웃이다.
이렇게 선을 따라 발을 옮기며 점을 하나씩 밟는 것이 그래프 위를 걷는 일이에요.

가까운 순서, 너비 우선

첫째 걸음걸이는 물결이다. 출발점 바로 옆을 다 밟고, 그다음 한 겹 멀리, 또 한 겹 멀리 나아간다.
연못에 돌을 던지면 동그라미가 퍼지듯 가까운 곳부터 차례로 바깥으로 번져요.

누를 때마다 한 겹씩 물결처럼 퍼진다. (밟은 점 = 색 · 같은 겹은 같은 거리)

물결이 퍼지는 동안 아직 못 간 점들은 기다리는 줄에 선다. 먼저 줄에 선 점부터 차례차례 들른다.
그래서 가까운 점이 언제나 먼 점보다 먼저다. 겹이 곧 거리예요.

끝까지, 깊이 우선

둘째 걸음걸이는 미로 탐험이다. 한 길을 골라 갈 수 있는 데까지 쭉 간다.
더 갈 곳이 없으면 한 걸음 되돌아와서 안 가 본 옆길로 다시 쭉 간다.
넓게 퍼지는 대신 깊이 파고드는 거예요.

누를 때마다 한 길을 끝까지 갔다가, 막히면 되돌아온다. (지금 점 = 파랑 · 되돌아온 길 = 흐리게)

되돌아올 곳을 잊지 않으려면 지나온 점을 쌓아 둔다.
쌓아 둔 더미에서 맨 위의 것부터 되짚으며 옆길을 찾는다. 그래서 깊이 우선은 가장 최근에 들른 곳으로 먼저 돌아가요.

너비 우선이 최단을 준다

물결은 그냥 퍼지는 것이 아니다. 가까운 겹부터 밟으니, 어떤 점에 처음 닿는 순간이 바로 가장 빠른 길이다.
선마다 거리가 똑같다면 몇 겹째에 닿았는지가 곧 출발점에서의 거리이고, 돌아가는 길이 없어요.

점을 누르면 두 걸음걸이의 도착 거리를 견줄 수 있다. (너비 우선 겹 번호 = 곧 최단 거리)

깊이 우선은 빠르게 멀리 가지만 에둘러 닿을 수도 있다. 그래서 최단 거리는 물결, 곧 너비 우선의 몫이다.
다만 지금은 모든 선의 거리가 똑같다고 보았다. 선마다 거리가 다르면 또 다른 이야기가 되는데, 그건 다음 레슨에서 다뤄요.

정리

그래프 위를 걷는 두 방법을 보았다. 너비 우선은 물결처럼 가까운 곳부터 한 겹씩 퍼지고, 깊이 우선은 한 길을 끝까지 갔다가 되돌아온다.
둘 다 모든 점을 밟지만 차례가 다르다. 거리가 같으면 너비 우선이 최단이에요.

두 걸음걸이를 누르면 각각의 모양이 나타나요. (너비 우선 = 물결 · 깊이 우선 = 끝까지)

지도에서 길 찾기, 친구의 친구 따라가기, 미로 빠져나오기처럼 그래프 위를 걷는 일은 생각보다 가까이 있다.
다음 레슨에서는 선마다 거리가 다른 그래프에서 가장 빠른 길을 찾아요.