[알고리즘/그래프] 그래프 알고리즘

*노드 수 V, 에지 수 E

 

유니온 파인드

Union 연산 : 특정 2개의 노드를 연결해 하나의 집합으로 묶는 연산

Find 연산 : 두 노드가 같은 집합에 속해 있는지 확인하는 연산

 

위상 정렬

'사이클이 없는' 방향 그래프에서 노드 순서를 찾는 알고리즘

사이클이 존재하면 안됨!

 

다익스트라

'에지가 모두 양수'인 그래프에서 그래프에서 최단 거리를 구하는 알고리즘

시간복잡도 : O(E logV)  

 

벨만-포드

그래프에서 최단 거리를 구하는 알고리즘.

음수 가중치 에지가 있어도 가능.

음수 사이클의 존재 여부를 판단할 수도 있다.

시간복잡도 : O(VE)

 

플로이드-워셜

그래프에서 모든 노드 간에 최단 경로를 탐색하는 알고리즘

음수 가중치 에지 있어도 가능

DP원리를 이용해 접근

시간복잡도 : O(V^3)

 

최소신장트리

그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리