[Algorithm] 깊이 우선 탐색 DFS , 너비 우선 탐색 BFS

깊이 우선 탐색 

정의

그래프의 시작 노드에서 출발

탐색할 한쪽 분기를 정해 최대 깊이까지 탐색 후

다른쪽 분기로 이동하여 다시 탐색

 

- 재귀함수로 구현

- 스택 자료구조 이용

- 시간복잡도 O(V+E)

 

*스택 오버플로우에 유의 

 

핵심 이론 

DFS는 한 번 방문한 노드를 다시 방문하면 안됨 -> 노드 방문 여부를 체크할 배열 필요

그래프 - 인접 리스트로 표현

DFS의 탐색방식은 후입선출 의 특성을 가지므로 스택의 성질을 갖는 재귀함수로 주로 구현함

 

1.DFS를 시작할 노드를 하나 정하고 자료구조 초기화 

인접 리스트로 그래프 표현하기

방문 배열 초기화하기

시작 노드 스택에 삽입하기 

스택에 시작 노드를 1로 삽입할때 1의 방문배열을 true 로 

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입

스택에서 노드를 꺼내고 꺼낸 노드를 탐색 순서에 기입하고 해당 노드의 인접 노드들을 스택에 삽입하여 방문배열을 체크 

 

3. 스택 자료구조에서 값이 없을 때까지 반복

 

 

---

너비 우선 탐색

정의

시작 노드에서 출발해 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

 

- FIFO 탐색

- Queue 자료구조 이용

- 시간복잡도 O(V+E)

 

핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

방문한 노드를 다시 방문하지 않기 위해 체크할 배열이 필요함

그래프를 인접리스트로 표현하고 탐색을 위해 큐를 사용함

 

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입함 

방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않도록 함 

 

3. 큐 자료구조에 값이 없을 때까지 반복하기