그래프 위를 걷는 두 방법

한 점에서 출발

지난 시간에 그래프를 봤죠.
점은 노드, 선은 엣지,
고리 없는 그래프가 트리고요.
이번엔 그 위를 걸어봐요.
걸으려면 먼저
어디서 출발할지 정해야죠.
한 점을 고르면,
바로 이어진 이웃부터 보여요.

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

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

가까운 순, 너비 우선

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

클릭할 때마다 한 겹씩 물결처럼 퍼져요. (밟은 점 = 색 · 같은 겹은 같은 거리)

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

끝까지, 깊이 우선

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

클릭으로 한 길을 끝까지 갔다가, 막히면 되돌아와요. (지금 점 = 파랑 · 되돌아온 길 = 흐리게)

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

너비 우선이 최단을 줘요

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

클릭으로 두 걸음걸이의 도착 차례를 견줘요. (너비 우선 겹 번호 = 곧 최단 거리)

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

정리

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

두 걸음걸이를 눌러 켜 보세요. (너비 우선 = 물결 · 깊이 우선 = 끝까지)

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