[알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색)

DFS (깊이 우선탐색)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조( or 재귀함수)를 이용한다

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
3. 더이상 2번의 과정을 수행할수 없을 때까지 반복합니다.

BFS (너비 우선 탐색)

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용한다.

1. 탐색 시작노드를 큐에 삽입하고 방문처리를 합니다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다.
3. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복합니다.