DFS & BFS

DFS와 BFS는 그래프 탐색 알고리즘

 

1. DFS(Depth First Search) : 깊이 우선 탐색

그래프를 탐색 할때 특정한 경로로 쭉 타고 끝까지 내려간 후 특정한 경로의 시작으로 다시 돌아와 다른 경로를 방문

 

- 스택 또는 재귀함수를 사용하여 구현 가능

 

- 탐색 순서(스택)

 1. 시작노드를 스택에 삽입하고 방문표시
 2. 스택의 최상단 노드의 인접 노드 중에 방문하지 않은 노드가 하나라도 있으면 그 노드를 스택에 삽입하고 방문표시

 3. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼내고 최상단 노드의 인접 노드를 계속 확인 

 4. 2~3번 과정을 수행할 수 없을 때까지 반복

 5. 모든 노드를 방문하면 탐색 종료

 

- 탐색 순서(재귀함수)

 1. 재귀함수에 시작노드를 넣어 호출

 2. (시작)노드를 방문표시
 3. 현재 노드의 인접 노드 중에 방문하지 않은 노드가 하나라도 있으면 그 노드로 재귀함수 호출

 4. 2~3번 과정을 수행할 수 없을 때까지 반복

 5. 방문하지 않은 인접노드가 없으면 재귀함수 탈출하여 3번 과정으로 돌아감

 6. 모든 노드를 방문하면 탐색 종료

 

 

- 사용 유형

 : 사이클(순환)의 존재 여부

 : 경로의 특징을 저장할 필요가 있을 때

 : 길 찾기

 : 미로 탈출

 : 그래프가 많이 클 때

 

- 관련 문제

2. BFS(Breadth First Search) : 너비 우선 탐색

그래프를 탐색 할때 가까운 노드들을 우선적으로 방문하고 멀리있는 노드를 나중에 방문

 

- 큐를 사용하여 구현 가능

 

- 탐색 순서

 1. 탐색 시작노드를 큐에 삽입하고 방문표시
 2. 큐에서 노드를 꺼내기

 3. 반복문을 돌며 해당 노드의 인접 노드 중에 방문하지 않은 노드를 모두 큐에 삽입하고 방문표시

 4. 더 이상 방문 가능한 노드가 없으면 반복문을 빠져나와서 2번 과정부터 다시 시작

 5. 완전히 큐가 비게 되면(모든 노드를 방문하면) 탐색 종료

 

- 사용 유형

 : 최단 거리 계산

 : 최단 경로 계산

 : 길 찾기

 : 미로 탈출

 : 최소신장 트리

 : 그래프가 크지 않을 때

 

- 관련 문제

 

3. 공통점

 

(계속 내용 추가 예정)