DFS && BFS

그래프의 탐색

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

한 사람에게만 연락을 취하는 방식

• 한 쪽으로만 탐색한다.
• 탐색할 곳이 없다면, 그 전 탐색했던 곳으로 돌아간다.
• 처음 시작한 곳에서 탐색이 끝난다.

DFS 구현

• 스택
  경로 정보의 추적을 목적으로 한다.
• 배열
  방문 정보의 기록을 목적으로 한다.

BFS(Breadth First Search: DFS, 너비 우선 탐색)

자신에게 연결된 모든 사람에게 연락을 취하는 방식

BFS 구현

• 큐
  방문 차례의 기록을 목적으로 한다.
• 배열
  방문 정보의 기록을 목적으로 한다.

최소 비용 신장 트리

트리는 그래프의 한 유형이다.

사이클을 형성하지 않는 그래프

• 경로
  두 개의 정점을 잇는 간선을 순서대로 나열한 것

• 단순 경로
  동일한 간선을 중복하여 포함하지 않는 경로

• 사이클
  단순 경로이면서 시작과 끝이 같은 경로

• 신장 트리(spanning tree)
  사이클을 형성하지 않는 그래프
  그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.
  그래프 내에서 사이클을 형성하지 않는다.

• 최소 비용 신장 트리(Minimum Cost Spanning Tree), 최소 신장 트리(Minimum Spanning Tree, MST)
  신장 트리의 모든 간선의 가중치 합이 최소인 그래프
  가중치가 있는 신장 트리에서 모든 정점을 지나는 경로의 가중치의 합이 가장 작은 서브 그래프
  간선의 수 + 1 = 정점의 수

최소 비용 신장 트리의 구성을 위한 크루스칼 알고리즘

최소 비용 신장 트리의 구성에 사용되는 대표적인 알고리즘 두 가지

• 크루스칼 알고리즘
  가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식
• 프림 알고리즘
  하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

크루스칼 알고리즘1

• 가중치를 기준으로 간선을 오름차순으로 정렬한다.
• 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다.
• 사이클을 형성하는 간선은 추가하지 않는다.
• 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다.

크루스칼 알고리즘2

• 가중치를 기준으로 간선을 내림차순으로 정렬한다.
• 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거한다.
• 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않는다.
• 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다.