회원가입

[그래프] 25. BFS predecessor

NULL 2021-09-27

BFS를 할 때는 각 Node 는 그 Node 를 방문한 적이 있는지 없는지 표시하는 목적으로 visited라는 변수를 저장한다.

 

사진에서는 이 visited 를 변수를 Node의 색으로 나타냈다.

 

최단 경로를 구할 때는 이 visited 변수에 추가로 predecessor 라는 변수도 저장해 줄 것이다.

predecessor는 한국말로 '~이전에 온 것' 이라는 뜻이다.

여기서 '~이전에 온 것' 이라는 건 무엇을 뜻하는 것일까?

 

BFS에서 Node를 방문하기 위해서는 어떤 다른 Node에서 왔어야 했나?

predecessor : BFS를 할 때 특정 Node에 오기 직전 Node

 

예를 들어서 시작점 A에서 탐색을 한다고 하자.

 

그러면 먼저 A 에서 인접한 Node들인 BC를 방문할 것이다.

이때 BCA를 통해서 온 것이다.

그럼 BCpredecessorA 를 저장하는 것이다.

 

그 다음은 B 에 인접한 Node 들을 방문할 차례이다.

D가 있다. 그럼 DB를 통해서 온 것이기 때문에 DpredecessorB로 저장한다.

 

이런 식으로 각 Nodepredecessor를 저장해 주면 BFS 알고리즘을 이용해서 최단 경로를 구할 수 있다.

 

다음 장에서 이 predecessor 변수가 어떻게 활용되는지 살펴보자

0 0