[Graph] Breadth-first search vs Depth-first search

아래와 같은 그래프가 있다고 가정합시다.

1번노드를 Root node로 가정하고, Breadth-first search 를 수행해보겠습니다.

1과 이웃된 노드는 2번 노드와 5번 노드가 있습니다.

우선 첫번째로, 2번 노드를 search 하게 됩니다.

다음으로 나머지 이웃 노드인 5번 노드를 search 합니다.

이제 1 번 노드는 explored 되었다고 할 수 있고, 2, 5 번 노드는 search 된 노드입니다.

다시 2번 노드에 대해서 아직 explored 되지 않은 노드를 search 해야 합니다.

3번 노드가 search 되겠네요.

다음은 5번 노드에 대해서 같은 방식으로 4번 노드가 search 됩니다.

이제 2번 노드와 5번 노드는 explored 노드로 변경됩니다.

3번 노드의 입장에서 이웃 노드인 2번 노드와 4번 노드는 이미 search가 되었기 때문에, 더 이상 search가 진행되지 않게됩니다.

반면에 4번 노드 입장에서 6번 노드가 search 될 수 있습니다.

즉, 1-2-5-3-4-6 순서대로 search가 되었습니다.

이처럼 Breadth-first search 는 점점 펼쳐져 나가는 형식으로 search가 진행됩니다.

​

​

하지만 반면에 Depth-first search는 다릅니다.

1과 이웃된 2번 노드를 search 하고, 5번으로 돌아가는 것이 아니라, 계속해서 진행합니다.

2번 노드에서 3번 노드 search, 3번 노드에서 4번 노드 search, 4번 노드에서 6번 노드 search를 진행합니다.

그리고 마지막으로 5번 노드로 돌아가서, search를 진행하지만, 위의 예시에서는 4번 노드가 search 된 노드이므로, 끝이납니다.

즉, 1-2-3-4-6-5 순서대로 search가 진행되었습니다.

Depth-first search 는 먼저 쭉 뻗어 나가는 형식으로 search가 진행됩니다.