DFS와 BFS

그래프를 탐색하는 방법에는 대표적으로 DFS와 BFS가 있다.

• DFS(Depth-First Search): 깊이 우선 탐색
• BFS(Breadth-First Search): 너비 우선 탐색

💡 트리에서 배웠던 전위순회(pre-order), 중위순회(in-order), 후위순회(post-order)는 DFS 방법에 속하고, 레벨순회(level-order)는 BFS 방법에 속한다. 👉 트리 문서 바로가기

출처: Graph 검색 DFS, BFS 구현 in Java - 엔지니어대한민국

DFS(깊이 우선 탐색)

노드의 어떤 자식 노드, 그 노드의 또 어떤 자식 노드, 그 노드의 자식 노드, ... 더이상의 자식 노드가 없을 때까지 깊게 파고들고 다시 되돌아 오며 들르지 않았던 다른 노드를 탐색하는... 이런 방법을 DFS(깊이 우선 탐색)이라고 한다. (📌설명에서 편의상 자식 노드라고 칭했다. 트리가 아닌 그래프에는 자식 노드라는 개념이 없으므로 인접한 노드라는 표현이 더 정확한 표현임을 알아두자.)

DFS 구현 - (1) 스택

DFS는 스택(Stack)을 사용하여 쉽게 구현할 수 있다.

• 최초에 시작할 노드를 정해 스택에 넣는다.
• 스택에서 노드를 꺼내고, 그 노드의 인접 노드들을 모두 넣는다. 그리고 꺼낸 노드는 출력해준다. 이 과정을 반복한다. (단, 스택에 인접 노드를 추가할 때는 한번 스택에 담았던 노드는 다시 넣지 않는다.)

DFS 구현 - (2) 재귀

DFS는 재귀호출(Recursion)을 이용해 구현할 수도 있다. 재귀호출을 이용하면 코드가 훨씬 간결해진다.

• 시작 노드를 정해 함수를 최초 호출한다.
• 노드를 방문하면 데이터를 출력한다. 이후 그 노드의 인접 노드로 재귀호출을 한다. (이때 인접 노드중 무엇을 먼저 호출할지는 노드를 추가할 때 어떤 노드와의 관계를 먼저 입력했느냐에 따라 결정된다.)
• 재귀호출된 노드는 자신의 데이터를 출력하고 또 자신의 인접 노드로 재귀호출을 한다. 이 과정이 반복되며 탐색이 이루어진다.

BFS(너비 우선 탐색)

노드의 자식 노드들을 모두 방문하고 그 다음 층 자식 노드들을 방문하는 식으로 레벨 순서대로 탐색하는 것이 BFS(너비 우선 탐색)이다.

BFS 구현

BFS는 큐(Queue)를 사용하여 쉽게 구현할 수 있다.

• 최초에 시작할 노드를 정해 큐에 넣는다.
• 큐에서 노드를 꺼내고, 그 노드의 인접 노드들을 큐에 넣는다. 그리고 꺼낸 노드는 출력해준다. 이 과정을 반복한다. (단, 큐에 인접 노드를 추가할 때는 한번 스택에 담았던 노드는 다시 넣지 않는다.)

Ref

• Graph 검색 DFS, BFS 구현 in Java - 엔지니어대한민국