[알고리즘-이론]그래프의 검색 알고리즘 - DFS(Stack)와 BFS(Queue)

그래프 자료구조에서 노드의 Data를 검색하는 방법에는 여러 방법이 있겠지만 대표적인 DFS, BFS를 학습해보자.

그래프

 

그래프란?

 

위와 같은 모습으로 노드들 간의 관계를 간선으로 연결 혹은 비연결 되어있는 자료구조 이다.

 

지금은 자료구조에 대한 설명을 하는 시간이 아니므로 넘어가서 바로 그래프의 검색 알고리즘을 알아보자.

 

Depth-First-Search(DFS)

 

 

깊이 우선 검색인 DFS는

• Inorder
• Preorder*
• Postorder
  과 같은 것들이 포함되며 시작 노드에서부터 해당 노드의 자식 노드로 끝까지 내려가며 검색하는 방식을 뜻한다.

 

Breath-First-Search(BFS)

 

넓이 우선 검색인 BFS는

 

 

시작 노드에서 자신의 형제노드 (Level) 단위로 검색하는 방법을 뜻한다.

 

DFS와 BFS의 차이

 

 

DFS의 구현

 

다음과 같은 그래프가 있다고 가정하였을 때 DFS와 BFS를 이용하여 그래프를 순회해보자.

 

Stack

 

깊이 우선 검색 인 DFS는 주로 Stack으로 구현을 한다.

 

스택에 시작 노드부터 넣고 노드를 Pop 할 때 해당 노드의 자식을 스택에 넣어준다.

 

1. 0을 스택에서 pop 그의 자식인 1을 push 한다.

 

2. 1을 스택에서 pop하고 그의 자식인 2와 3을 push 한다.

 

3. 3을 스택에서 Pop하고 그의 자식인 4와 5를 push 한다.

 

4. 5를 스택에서 pop 하고 그의 자식인 7과 6을 push 한다.

 

5. 6을 스택에서 pop하고 그의 자식인 8을 push 한다.

 

6. 나머지 노드를 pop한다.

 

BFS의 구현

 

Queue

 

넓이 우선 검색인 BFS는 주로 Queue로 구현을 한다.

 

0을 시작노드로 하여 그의 자식인 1을 enqueue 한다.

 

 

큐에서 1을 dequeue 하고 그의 자식인 2와 3을 enqueue 한다.

 

큐에서 2를 dequeue하고 그의 자식인 4를 enqueue한다.

 

큐에서 3을 dequeue 하고 그의 자식인 5를 enqueue 한다.

 

큐에서 4를 dequeue 하고 그의 자식을 enqueue 해야하지만 이미 출력되어 있으므로 넘어간다.

 

큐에서 5를 dequeue 하고 그의 자식을 enqueue 해준다.

모든 노드를 방문하여 더 이상 큐에 남은 노드가 없을 때 까지 위와 같은 과정을 반복하여 결과를 출력한다.