BFS, DFS

BFS, DFS

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

: 너비를 우선 순위로 두어 탐색하는 알고리즘. Queue를 이용하여 사용되고 최단 경로를 찾는데 쓰인다.

Queue에 노드를 넣고, 노드를 꺼내면서 그 노드의 가장 인접한 노드들을 다시 Queue에 넣는다.

Queue는 First In First Out으로 먼저 들어간 것이 먼저 나온다.

ex)

Queue : 1

1을 꺼내면서 근접 노드인 2와 3을 넣는다.

Queue : 2, 3

result : 1

2를 꺼내면서 근접 노드인 4와 5을 넣는다.

Queue : 3, 4, 5

result : 1, 2

3을 꺼내면서 근접 노드인 6와 7을 넣는다.

Queue : 4, 5, 6, 7

result : 1, 2, 3

나머지 노드는 인접 노드가 없기 때문에 순서대로 꺼낸다.

Queue :

result : 1, 2, 3, 4, 5, 6, 7

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

: 깊이를 우선 순위로 두어 탐색하는 알고리즘. Stack을 이용하여 사용된다.

Stack에 노드를 넣고, Stack의 최상단 노드를 확인하여 그 노드의 가장 인접한 노드들을 다시 Stack에 넣는다.

이 때 확인하는 순서가 깊이 우선이다.

Stack은 Last In First Out으로 나중에 들어간 것이 먼저 나온다.

ex)

Stack : 1

1을 확인, 1과 인접한 노드인 2를 넣는다.

Stack : 1, 2

result : 1

2를 확인, 2와 인접한 노드인 3을 넣는다. ( 같은 깊이 우선 이기에 4와 5가 아닌 3부터 )

Stack : 1, 2, 3

result : 1, 2,

3을 확인, 3과 인접한 노드인 6을 넣는다.

Stack : 1, 2, 3, 6

result : 1, 2, 3

6을 확인, 6과 인접한 노드인 7을 넣는다.

Stack : 1, 2, 3, 6, 7

result : 1, 2, 3, 6

7을 확인, 인접한 노드가 없기에 Stack에서 나옴.

Stack : 1, 2, 3, 6

result : 1, 2, 3, 6, 7

6을 확인, 인접한 노드가 없기에 Stack에서 나옴.

Stack : 1, 2, 3

result : 1, 2, 3, 6, 7

3을 확인, 인접한 노드가 없기에 Stack에서 나옴.

Stack : 1, 2

result : 1, 2, 3, 6, 7

최상단 노드인 2를 확인하여 확인하지 않는 인접 노드인 4를 넣음

Stack : 1, 2, 4

result : 1, 2, 3, 6, 7

최상단 노드인 4를 확인하여 확인하지 않는 인접 노드인 5를 넣음

Stack : 1, 2, 4, 5

result : 1, 2, 3, 6, 7, 4

5를 확인, 5부터는 확인하지 않은 노드가 없기 때문에 차례대로 최상단 노드를 하나씩 빼낸다.

Stack :

result : 1, 2, 3, 6, 7, 4, 5

BFS와 DFS는 모든 항목을 탐색하는 맹목적인 탐색에 사용된다는 공통점이 있다.

from http://kkamcoffee.tistory.com/240 by ccl(A) rewrite - 2021-09-06 20:00:23