[그래프] 그래프의 기본

✔ 그래프의 기본

유니온 파인드

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

위상 정렬

• 사이클이 없는 방향 그래프일 때, 그래프의 각 노드의 순서를 찾는 알고리즘
• 순서 (정렬) 값이 유일하지 않다는 특징
• 수강 신청, 게임 빌드 오더 문제에 활용

다익스트라

• 시작점에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘
• 음수 간선이 존재하지 않아야 함 

벨만-포드

• 시작점에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘
• 음수 간선이 존재해도 됨 
• 음수 사이클이 있는지 확인하는 문제에 활용

플로이드-워셜

• 임의의 모든 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘
• 시간 복잡도가 좋지 않음

최소 신장 트리

• 모든 노드를 연결하는데 최소의 비용(가중치)으로 간선을 연결하는 알고리즘
• 유니온 파인드를 활용

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn