[📗c언어 쉽게 풀어쓴 자료구조11] 그래프2

👑 최소 비용 신장트리

신장트리란?
: 그래프 내의 모든 정점들을 포함하는 트리 (싸이클 없는 연결그래프)

• n-1개의 간선 (최소 연결 부분 그래프)
• 깊이 우선, 너비 우선 탐색 도중 사용된 간선을 모아 만들 수 있음

최소 비용 신장트리란?
: 경로에 가중치가 추가되어, 그 가중치의 합이 최소가 되는 신장트리

👑 크루스칼 알고리즘

• 탐욕적인 방법 (그 당시에 가장 최선의 선택을 함)
  & 가중치의 값을 오름차순 정렬-> 간선의 갯수 n-1개 될 때까지, 싸이클이 생기지 않게 선택
  (집합에 추가할 때, 싸이클이 생기는 지 확인해야 함!!)
• union-find(): 싸이클이 생기는지 확인하기 위한 함수 (각 정점이 포함된 집합을 받아, 합집합을 만들어, 같은 집합에 속하는 지 확인함!!)
  -> 루트가 다르면, 다른 집합에 속한 것임

👑 Prim 알고리즘

: 인접한 정점들 중에서 최소거리의 정점을 선택

&& 크루스칼 알고리과의 차이점

• 크루스칼: 간선을 기반으로 선택/ 단지 최저 간선 선택 (마지막에 신장트리 완성)
• 프림: 인접 정점을 기반으로 선택/ 이전 단계의 신장트리를 확장 (정점을 집합에 추가)

👑 Dijkstra 최단 경로 알고리즘

최단경로: 간선들의 가중치의 합이 최소가 되는 경로 찾기

• 탐욕적 알고리즘 (시작 정점으로부터 경로의 합은 집합에 기록하여, 최저의 기록 선택)
  -> 더 작은 값으로 인접한 정점의 간선 길이 update

👑 Floyd 최단 경로 알고리즘

: 모든 정점 사이의 최단 거리를 구하는 알고리즘 (3중 반복)

👑 위상정렬

: 방향 그래프에 존재하는 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

⭕ TIL (Today I learned)

& 신장트리는 모든 정점을 연결하는데, 싸이클을 형성하지 않는 트리이다. 신장트리 중에서도 간선의 가중치의 합을 최소로하는 트리를 최소 비용 신장트리라고 한다. 최소 비용 신장트리를 구하는 것은 간선의 갯수가 n-1이 될 때까지 반복한다. (신장트리는 항상 간선의 개수가 n-1개임!)
최단경로는, 모든 정점을 연결하진 않지만, 가중치의 합이 최소가 되게 하는 경로를 의미한다. 2가지 방법이 있다. 첫번째는 다익스트라 알고리즘인데, 간선을 기준으로 작은 것부터 오름차순으로 정렬하여, 최소의 것부터 싸이클이 생기지 않게 하나씩 선택하는 것이다. 두번째는 플로이드 알고리즘이다. 이것은 인접 정점을 기준으로 간선의 가중치 값이 작은 정점을 선택하여 집합에 추가하는 것이다.
위상정렬은 선행순서에 따라 정렬한 그래프를 말한다.