[Algorithm]Traversal of Graph

Graph traversal(그래프 순회)

= 모든 Node와 Edge를 한 번씩 지정된 순서로 방문

Graph Traversal 종류
1. 깊이 우선 탐색 (DFS: Depth First Search)
2. 너비 우선 탐색 (BFS: Breath First Search)

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

=> 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

1.1 동작 방식

1. 시작 노드를 방문하고, 방문 표시
2. 인접한 노드 중 방문하지 않은 노드로 이동
3. 더 이상 갈 수 없을 경우 되돌아가며 다른 경로 탐색
4. 모든 노드를 방문할 때까지 반복

1.2 구현 방식

• 재귀(Recursion)
• 스택(Stack)

ex)

• Step 1. 시작 노드를 스택에 push
• Step 2. 스택의 맨 위에 있는 노드 0을 pop하고 방문 표시
  
• Step 3. pop된 노드 0에서 방문하지 않은 인접한 노드 1,2,3을 스택에 push(3,2,1순으로 스택에 저장된다고 가정)
• Step 4. 스택의 맨 위에 있는 노드 1을 pop하고 방문 표시
  
• Step 5. pop된 노드 1에서 방문하지 않은 인접한 노드 4를 스택에 push
• Step 6. 스택 맨 위에 있는 노드 4를 pop하고 방문 표시
  
• Step 7. pop된 노드 4에서 방문하지 않은 인접 노드가 없기 때문에 스택 맨 위에 있는 노드 2를 pop하고 방문 표시
• Step 8. pop된 노드 2에서 방문하지 않은 노드가 없기 때문에 스택 맨 위에 있는 노드 3을 pop하고 방문 표시, 탐색 종료

2. 너비 우선 탐색 (BFS: Breath First Search)

=> 가까운 노드부터 탐색하는 알고리즘

2.1 동작 방식

1. 시작 노드를 큐에 넣고 방문 표시
2. 큐에서 하나 꺼내서 인접한 노드 중 방문하지 않은 노드를 큐에 추가
3. 큐가 빌 때까지 반복

2.2 구현 방식

큐(Queue)

ex)

• Step 1. 모든 노드를 방문하지 않은 상태로 표시
• Step 2. 시작 노드를 방문하여 방문 표시를 한 뒤 큐에 삽입
  
• Step 3. 큐에서 첫 번째 노드를 제거
• Step 4. 노드 0에서 인접한 노드들 중 방문한 적 없는 노드 1,2,3을 방문하여 방문 표시한 뒤 큐에 삽입
  
• Step 5. 큐에서 첫 번째 노드(1)을 제거
• Step 6. 노드 1에서 인접한 노드들 중 방문한 적 없는 노드 4를 방문하여 방문 표시한 뒤 큐에 삽입
  
• Step 7~9. 모든 노드를 방문하였기 때문에 큐에서 노드들을 하나씩 제거