그래프

그래프는 노드와 간선(엣지edge)로 구성된 집합이다.
노드 : 데이터를 표현하는 단위
엣지edge : 노드를 연결하는 선

크게, 유니온 파인드, 위상 정렬, 다익스트라, 벨만-포드, 플로이드-워셜, MST(최소신장트리) 가 있습니다.

유니온 파인드

(그래프에서) 그래프의 사이클이 생성되는지 판별하는 알고리즘
--> 사이클의 유무를 판별한다고 보면됩니다.

위상 정렬

사용 가능한 조건이 있습니다.

1. 싸이클이 없어야한다.
2. 방향이 있는 그래프여야한다. (단방향)
   --> 어찌보면 당연한 말입니다. 싸이클이 없으니까, 방향이 있다는 소리

특징 : 값이 유일하지 않다.

다시 말해,
조건 -> 사이클 x, 방향 간선이며,
노드를 연결해주는 알고리즘이다.
--> 정렬 결과가 꼭 1개 X
Ex) 수강신청, 게임 빌드오더 --> 수1 ->수2

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

다익스 트라, 벨만-포드는 S 라는 시작점이 있다.
--> 이 시작점으로부터, 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘이다.

But 아래와 같이 각각의 차이점이 존재합니다.

다익스트라

음수간선이 x --> 가중치가 음수라는 소리

벨만 포드

음수간선 o --> 보통 음수사이클이 있는지 check하는 문제들이 나온다.

플로이드-워셜

시작점이 없으며, 시간복잡도가 안좋음. 모든 도시에 가는 최단거리를 나타낼 때 쓰임.
--> 즉, 임의의 모든 쌍의 최단거리를 구한다.

최소신장트리 MST

MST의 전제조건은 유니온 파인드입니다.
유니온 파인드는 싸이클이 있기 때문입니다.
만약

     O							O
    | 							|
   O  - O       = = >   		O - O
   |  / |						|	
   | -  O						O - O
   O

이런식으로 싸이클이 존재하는 곳에서 엣지를 지우는 것이라고 이해하면됩니다.