[알고리즘] [16] 그래프 순회2

1. DFS

• 시작 지점의 한 방향으로 갈 수 있는 경로까지 깊이 탐색하다가 더 이상 갈 수 없을 때 이전 갈림길 간선으로 되돌아가 다른 정점을 탐색하는 순회 방법
• 재귀적으로 혹은 스택 자료구조를 이용하여 구현한다.
• 인접 행렬 또는 인접 리스트를 적절히 사용하여 DFS를 구현한다.

2. Flood Fill 알고리즘

• 플러드 필 혹은 시드 필(seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다.
• 그림 프로그램에서의 '채우기' 도구 또는 지뢰 찾기 등에 사용된다.
• 4방향 델타 배열 혹은 8방향 델타 배열을 사용할 수 있다.
• DFS 혹은 BFS로 구현된다.

3. 위상 정렬 (Topology Sort)

• 유향 그래프의 정점들을 간선의 방향을 거스르지 않도록 나열하는 것
• 순서가 정해진 작업들의 순서를 결정하는 알고리즘이다.
• 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 없는 비순환 유향 그래프여야 한다.
• 주로 BFS를 이용하여 구현한다.

BFS를 이용한 위상 정렬 구현

• 진입 차수가 0인 노드(시작점)을 큐에 모두 넣는다.
  >> 차수 : 노드에 연결된 간선의 수
  >> 진입 차수 : 노드로 들어오는 간선의 수
  
  
• 큐에서 진입 차수가 0인 노드를 꺼내, 자신과 인접한 노드의 간선을 제거한다.
  >> 인접 노드의 진입 차수를 1 감소시킨다.
• 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.
• 큐가 비어있지 않을 동안 반복한다.
• 모든 노드가 전부 처리되었다면 위상 정렬
• 모든 노드가 전부 처리되지 않았다면 사이클 발생