[Java] DFS/BFS 탐색 알고리즘

 

DFS : Depth-First Search : 깊이 우선 탐색

- 스택과 재귀함수를 이용하여 구현

 - 데이터의 개수가 N개 인 경우 O(N) 시간 소요

( 스택을 가로로 눕혀놨다고 생각하고 보기 ㅠ 오른쪽이 상단임..) 

 

 - 탐색 시작 노드를 스택에 삽입 & 방문처리 -> 최상단 노드에 방문하지 않은 인접노드 스택에 넣고 방문처리. 없으면 스택에서 최상단 노드 꺼내기. 반복

 

시작 노드 1 스택에 넣고 방문 처리 ( boolean [] visited= false; )

1 

 

스택의 최상단 노드 1 에 방문하지 않은 인접 2, 3, 8 존재

이 중 가장 작은 2 스택에 넣고 방문 처리

1 - 2 

 

스택의 최상단 노드 2 에 인접 1,7 중 방문하지 않은 7 스택에 넣고 방문 처리

1 - 2 - 7 

 

스택의 최상단 노드 7 에 방문하지 않은 인접노드 6, 8 존재

가장 작은 6 스택에 넣고 방문처리

1 - 2 - 7 - 6 

 

스택의 최상단 노드 6 에 방문하지 않은 인접 노드 없으므로 스택에서 꺼내기

1 - 2 - 7 

 

스택의 최상단 노드 7에 방문하지 않은 인접 노드 8 존재  - 스택에 넣고 방문 처리

1 - 2 - 7 - 8

 

스택의 최상단 노드 8에 방문하지 않은 인접 노드 없으므로 스택에서 꺼내기

1 - 2 - 7

 

스택의 최상단 노드 7에 방문하지 않은 인접 노드 없으므로 스택에서 꺼내기

1 - 2

스택의 최상단 노드 2에 방문하지 않은 인접 노드 없으므로 스택에서 꺼내기

1 

스택의 최상단 노드 1에 방문하지 않은 인접노드 3 스택에 넣고 방문 처리

1 - 3

스택의 최상단 노드 3에 방문하지 않은 인접노드 4, 5 중 가장 작은 4를 스택에 넣고 방문 처리

1 - 3 - 4

스택의 최상단 노드 4에 방문하지 않은 인접노드 5 스택에 넣고 방문 처리

1 - 3 - 4 - 5

남아 있는 노드에 방문하지 않은 인접 노드 없으므로 모든 노드 차례대로 꺼내기

==> 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5   ( 노드의 탐색 순서)

 

 

위로 스크롤 올리기 힘드니까 한 번 더 첨부 ㅎㅅㅎ

BFS : Breadth-First Search : 너비 우선 탐색

- 가까운 노드부터 탐색하기 위하여 큐를 이용하여 구현

 - 데이터의 개수가 N개 인 경우 O(N) 시간 소요 - 일반 적인 경우 실제 수행 시간은 DFS보다 좋은 편.

- 탐색 시작 노드 큐에 삽입& 방문처리 -> 큐에서 노드 꺼내 방문하지 않은 인접 노드 모두 큐에 삽입 & 방문처리. 반복

 

 

시작 노드 1 큐에 넣고 방문 처리

1

큐에서 1 꺼내고 1의 방문하지 않은 인접노드 2, 3, 8 모두 큐에 삽입 & 방문처리

2 - 3 - 8

큐에서 2 꺼내고 방문하지 않은 인접노드 7 큐에 삽입 & 방문처리

 - 3 - 8 - 7

큐에서 3 꺼내고 방문하지 않은 인접노드 4, 5 큐에 삽입 & 방문처리

 -  - 8 - 7 - 4 - 5

큐에서 8 꺼내고 방문하지 않은 인접노드 없으므로 무시

 -  -  - 7 - 4 - 5

큐에서 7 꺼내고 방문하지 않은 인접노드 6 큐에 삽입 & 방문처리

 -  -  -  - 4 - 5 - 6

남아있는 노드에 방문하지 않은 인접 노드 없으므로 모두 차례대로 꺼내기

-  -  -  -  -  - 

==> 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6   ( 노드의 탐색 순서)