그래프 기본

• 그래프는 노드와 엣지로 구성된 집합이다.
• 노드는 데이터를 표현하는 단위이고, 에지는 노드를 연결한다.
• 트리도 그래프의 일종이며, 그래프는 여러 알고리즘에 많이 사용되는 자료구조이므로 코딩 테스트에 자주 등장한다.

유니온 파인드

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

위상 정렬

• 알고리즘 조건 : 사이클 x, 방향이 있는 그래프
• 그래프의 노드들을 선형으로 정렬하는 알고리즘
• 대표적인 문제 : 수강신청(수1을 듣고 수2를 신청해야하는), 롤 아이템 업그레이드

다익스트라, 벨만-포드, 플로이드-워셜

• 최단거리를 구하는 알고리즘
  • 다익스트라
    • 시작점이 있고 다른 모든 노드로 가는 최단거리를 구하는 알고리즘
    • 음수간선이 있으면 x
  • 벨만-포드
    • 음수사이클이 있는지를 체크하는 문제로 많이 나옴
    • ex) 시간여행, 워프
    • 음수간선도 ok
  • 플로이드-워셜
    • 시작점이 없음
    • 모든 노드 쌍의 최단거리를 구한다. → 시간 복잡도가 안좋음

최소 신장 트리

• 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘
• 사이클 x
• 최소 신장 트리를 쓰려면 유니온 파인드가 필요하다(트리특 : 사이클이 없음).

출처 - 하루코딩