그래프는 노드와 간선(엣지edge)로 구성된 집합이다.
노드 : 데이터를 표현하는 단위
엣지edge : 노드를 연결하는 선
크게, 유니온 파인드, 위상 정렬, 다익스트라, 벨만-포드, 플로이드-워셜, MST(최소신장트리) 가 있습니다.
(그래프에서) 그래프의 사이클이 생성되는지 판별하는 알고리즘
--> 사이클의 유무를 판별한다고 보면됩니다.
사용 가능한 조건이 있습니다.
특징 : 값이 유일하지 않다.
다시 말해,
조건 -> 사이클 x, 방향 간선이며,
노드를 연결해주는 알고리즘이다.
--> 정렬 결과가 꼭 1개 X
Ex) 수강신청, 게임 빌드오더 --> 수1 ->수2
다익스 트라, 벨만-포드는 S 라는 시작점이 있다.
--> 이 시작점으로부터, 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘이다.
But 아래와 같이 각각의 차이점이 존재합니다.
음수간선이 x --> 가중치가 음수라는 소리
음수간선 o --> 보통 음수사이클이 있는지 check하는 문제들이 나온다.
시작점이 없으며, 시간복잡도가 안좋음. 모든 도시에 가는 최단거리를 나타낼 때 쓰임.
--> 즉, 임의의 모든 쌍의 최단거리를 구한다.
MST의 전제조건은 유니온 파인드입니다.
유니온 파인드는 싸이클이 있기 때문입니다.
만약
O O
| |
O - O = = > O - O
| / | |
| - O O - O
O
이런식으로 싸이클이 존재하는 곳에서 엣지를 지우는 것이라고 이해하면됩니다.