[C++자료구조]DFS(깊이우선탐색)와 BFS(너비우선탐색)

 

DFS(Depth-first Search)깊이 우선 탐색은 출발 정점 v를 방문함으로써 시작된다. 다음으로 v에 인접하면서 아직 방문하지 않은 한 정점 w를 선택하여 이 w에서 다시 깊이-우선 탐색을 시작한다. 인접 정점들을 이미 모두 방문한 정점 u에 도달하면, 마지막으로 방문한 정점 중 아직 방문하지 않은 인접 정점 w를 가지고 있는 정점까지 되돌아가서 정점 w로부터 깊이-우선 탐색을 다시 시작한다. 이러한 탐색은 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을때 종료된다. 

인접리스트 쓰는 경우 복잡도는 O(e)이다. e는 간선개수다.

인접행렬 쓰는 경우 인접한 모든 정점들을 결정하는 데 O(n)의 시간이 걸린다. 그러므로 최대 n개의 점을 방문해야하므로 복잡도는 O(n^2)이다. 

-스택 또는 재귀함수로 구현

 

BFS(Breadth-first Search)너비 우선 탐색은 시작 정점 v를 방문하는 것으로 시작한다. 다음으로 v에 인접한 방문하지 않은 모든 정점들을 방문한다. 그리고 다시 이 새로 방문한 정점들에 인접하면서 방문하지 않은 정점들을 방문하는 방식으로 계속한다.

-큐로 구현