https://www.youtube.com/watch?v=MOZUzB8w2LA&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=28

📌 그래프

• 노드와 에지로 구성된 집합
  * 노드 : 데이터를 표현하는 단위
  * 에지 : 노드를 연결

◾ 유니온 파인드

• 그래프의 사이클이 생성되는지 판별하는 알고리즘
  
  

◾ 위상 정렬

• 사이클이 없고 방향이 있는 그래프의 노드를 정렬 해주는 알고리즘
• 정렬 결과가 꼭 1개가 아님 (값이 유일하지 않음.)
• 사용 예시
  수강 신청 (전후 관계가 있어야 함 ex. 수1 들은 후 수2 듣는다.)
  
  

◾ 다익스트라

• 최단거리 알고리즘
• 시작점(S)이 있고 시작점에서 다른 모든 노드로 가는 최단거리를 구함
• 선 제약 사항 : 음수 간선은 있어서는 안됨.
  
  

◾ 벨만-포드

• 최단거리 알고리즘
  시작점(S)이 있고 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘
  음수 간선 사용 가능
• 사용 예시
  음수 사이클이 있는지를 체크하는 문제에서 많이 사용
  시간 여행 (과거로 돌아갈 수 있는지), 웜홀(워프) 등
  
  

◾ 플로드-워셜

• 최단거리 알고리즘
• 시작점이 없음. 모든 노드에 대해 최단거리를 구함.
  단 , 시간 복잡도가 안좋다.
• 사용 예시
  모든 도시 간 최단거리를 구해라. 단, 도시의 개수는 100개이다 (도시 수가 작아 시간복잡도 상관x)
  모든 도시를 가는데 필요한 최단거리를 구하시오 (시작점이 없음)
  
  

◾ 최소 신장 트리(MST)

• 최소의 가중치 합으로 모든 노드를 연결 할 수 있게 해주는 알고리즘
• 사이클이 있어서는 안됨 → 유니온 파인드 사용
• 사용 예시
  최소의 비용으로 간선을 써서 모든 노드를 연결하고 싶을 때