[Introduction to Algorithms] DFS 와 BFS

1. 개요

DFS와 BFS에 대해서 공부해 보는 시간을 가지게 되었다.

 

2. DFS & BFS

 

위 sudo code는 공유 정점이 있더라도 적용할 수 있는 코드이다.

이는 3가지 색을 이용해서 방문 전, 방문 중, 방문 후 노드를 나타내어 주었다.

흰색 : not visited

회색 : visiting

검정 : visited를 나타낸다.

 

시작 정점을 제외한 모든 정점에 대해서 색을 흰색과, parent node는 NIL 그리고 거리는 무한으로 설정해 주었다.

시작 노드 색을 grey로 설정하고, 시작 노드는 부모 노드가 없으므로 pi 또한 NIL로 설정해 주었다.

시작 노드와의 거리도 0으로 설정해 주었따.

 

BFS 는 queue로도 구현이 가능하기에, Q에 대하서 deque를 선언해 주었다. 

또한 queue에서 pop 된 노드의 인접 노드를 가져와서 색을 회색으로 바꾸어 주었다. 

위 사진에는 생략이 되었지만 노드 v에 대해서 for -> if 문 안에서 enque 를 해주어야 한다.

 

해당 수도 코드는 공유 정점에 대한 처리도 가능하다는 점에서 의의가 있는 것 같다.

 

DFS의 경우 distance를 나타내진 않았다.

DFS는 재귀로 나타내었기 때문에, 처음 호출 된 이후, 인접 노드들이 방문되고 다시 돌아왔을 때까지 시간이 얼마나 걸리는 지를 파악하도록 하였다.

 

u.f 는 끝나는 시간, u.d는 시작 시간을 의미한다.

우선 모든 정점에 대해서 색을 흰색과 pi를 nil로 설정해 주었다. 

시간은 전역 변수를 설정하여, 함수가 재귀적으로 선언되더라도 시간 변수를 유지할 수 있도록 하였다.

 

재귀가 호출되면 시간을 + 1 하고 시작 시간을 기록해 주었다. 

또한 인접 노드가 흰색이라면 재귀적으로 dfs_recursive 함수를 불러주었다.

for 문이 끝났을 떄의 시간 또한 u.f로 기록해주고, u.color를 검정으로 바꾸어 주었다.