회원가입

[그래프] 27. BFS로 찾은 경로가 최단 경로인 이유

NULL 2021-09-27

BFS 알고리즘을 이용한 predecessor 방식이 진짜 최단 경로가 맞는지 어떻게 확신할 수 있을까?

이번 장에서는 증명해보겠다.

 

이것을 이해하기 위해서는 BFS가 Node를 방문하는 순서를 살펴봐야 한다.

 

BFS는 시작 Node 를 먼저 본다.

 

그리고 이 시작점에서 인접한 Node 들을 모두 방문한다.

 

그리고 방문한 순서대로 큐에 넣는다.

 

시작점에서 인접한 Node 들을 다 방문했으면 큐 맨 앞에 있는 Node 를 뺀다.

그리고 이 Node에 인접한 걸 다 볼 것이다.

 

마찬가지로 방문한 순서대로 큐에 넣는다.

다 보고 나면 큐에서 또 하나를 빼서 인접한 것을 다 볼 것이다.

 

이런 식으로 진행이 되는데, 이것을 하다 보면 패턴이 보일 것이다.

 

처음에 시작 Node 를 방문하고, 그 다음에는 시작 Node 에서 인접한 Node들을 순서대로 방문한다.

얘네들은 시작점에서 거리가 1인 Node 들이라고 할 수 있다.

그러니까 처음에는 거리가 1인 Node 들 부터 다 본다는 것이다.

 

그러고 나서는 방금 그 Node 들에서 인접한 Node 들을 보는 것인데, 이것들은 시작 점에서 거리가 2인 Node 들이라고 할 수 있다.

 

그 다음으로 방문하는 Node 들은 어떨까?

얘네는 시작점에서 거리가 3인 Node 들이다.

 

이런 식으로 거리가 1인 Node 를 먼저 다 방문하고, 그 다음에 거리가 2인 Node 들을 다 방문하고, 그 다음에는 거리가 3인 Node 를 모두 방문하고, 이런 순서대로 방문을 하는 것이다.

증명


BFS가 찾은 경로가 정말로 최단 경로가 맞는지 증명하고 싶었던 것이다.

시작점 A 에서 F 까지의 최단 경로를 알고 싶다고 하자.

 

BFS를 진행하면서 F 를 처음 딱 방문하는 순간이 있을 것이다.

그 순간에 거리가 1인 Node 들은 이미 다 방문했고, 거리가 2인 Node 들을 방문하고 있다.

만약 A 에서 F 까지의 최단 거리가 1이라면 거리가 1인 Node 들을 찾을 때, 이미 F 를 방문했을 것이다.

그런데 거리가 2인 Node 들을 방문했을 때 발견했다는 건, A 에서 F 까지의 최단 거리가 2일 수밖에 없다는 것이다.

F 를 처음 방문한 그 순간이 F 를 가장 빠르게 찾은 것이다.

그럼 이때의 시작점에서부터 F 까지의 경로를 저장해 놓으면 최단 경로를 구할 수 있다.

 

그걸 하는 게 바로 predecessor 변수이다.

F 가 가장 빨리 발견되는 경우는 predecessor C 를 통해서이다.

C 도 마찬가지이다.

predecessor A 에서 C 로 오는 게 가장 빠른 경로이다.

이렇게 predecessor 를 통해 각 Node 는 어떤 Node 를 통해서 오는 게 가장 빠른 건지를 저장하고 있다.

0 0