[그래프] 그래프 관련 알고리즘 종류 정리

그래프

노드와 엣지로 구성된 집합.

예) 트리

 

노드

데이터 표현 단위

 

엣지

노드를 연결할 때 사용

 

그래프 알고리즘 종류

• 유니온 파인드
• 위상 정렬
• 다익스트라
• 벨만-포드
• 플로이드-워셜
• 최소 신장 트리

---

유니온 파인드

그래프의 `사이클 생성 유무`를 판단하는 알고리즘

그래프에서만 쓰이는 알고리즘은 아님

사용 예) `집합에서 대표 노드 탐색` 혹은 `각 원소들을 유니온 하여 하나의 집합으로 통합`

 

ex) 3개의 노드와 2개의 엣지로 구성되었다고 가정했을 때 엣지를 추가할 경우 현재 그래프에 사이클이 생성되는가

 

 

→ 유니온 파인드로 사이클 생성 여부를 도출한다.

---

위상 정렬

그래프의 각 노드들을 선형으로 정렬하는 알고리즘

알고리즘 사용 선 조건

1. 사이클이 없어야 한다.
2. 방향(간선)이 있는 그래프이다.

ⓐ → ⓑ → ⓒ  ↓ ⓓ	ⓐ → ⓑ → ⓒ → ⓓ
	ⓐ → ⓓ → ⓑ → ⓒ

 

위와 같이 두가지 케이스로 정렬이 되기 때문에 정렬된 값이 유일하지 않다는 특징이 있다.

 

문제 유형

방향이 존재하며 사이클이 존재하지 않는 그래프 이므로 전후 관계 필요

1. 수강 신청 : 수Ⅰ → 수Ⅱ
2. 게임 빌드오더(선 순위 아이템 구매) : 배럭 → 팩토리

---

최단거리 알고리즘

 

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

 

① 다익스트라

ⓢ 시작점이 있고, ⓢ라는 시작점으로 부터 다른 노드로 가는 최단 거리를 구하는 알고리즘

알고리즘 사용 선 조건

• 음수 간선이 있으면 안됨.

간선 : 노드 간 거리를 나타내는 에지와 같은 선 

---

 

② 벨만 - 포드

다익스트라와 같으며 음수 간선을 허용한다.

실제 벨만포드는 음수 간선에 최단거리를 구하는 문제보다는 `음수 간선이 있는지 여부`를 체크하는 문제가 더 많이 출제 된다.

 

문제유형

• 시간 여행 여부 (과거로 돌아갈 수 있는지)
• 웜-홀 (워프)

---

③  플로이드 - 워셜

시작점이 없으며 주어진 노드 중 어떤걸 체크하더라도 체크한 노드 간 최단 거리 도출이 가능하다

단, 다익스트라, 벨만포드에 비해 시간복잡도가 크다

 

 

문제유형

• 모든 도시 간 최단 거리 (도시 개수 100개 이하)
  (시작점이 없고 시간복잡도가 낮으므로 알고리즘 사용 가능)

---

최소 신장 트리 - MST(Minimum Spanning Tree)

Tree형태로, 최소의 비용으로 간선을 사용하여 모든 노드를 연결한다.

트리 이므로 사이클이 없기 때문에 유니온 파인드 알고리즘을 사용한다.

(최소 신장 트리 알고리즘 안에 유니온 파인드 알고리즘이 사용된다.)

트리이기 때문에 세개의 노드를 예로 든다면 세개의 간선으로 연결되지 않더라도(사이클X) 각 노드가 연결된다.

 

그래프에서 최소의 가중치(거리) 합으로 모든 노드를 연결할 수 있게 해 주는 알고리즘이다.