- 그래프는 여러 자료구조들 중에 표현 능력이 가장 뛰어나며 노드(vertex, node)와 간선(edge)을 이용해 쉽게 모델링을 할 수 있다. 보통 표현의 주가 되는 사물, 대상이 node로 표현되면 대상들간의 관계를 edge로 표현하게 된다. 즉, 그래프는 node와 edge의 집합으로 생각할 수 있다. 방향성에 따라 그래프의 종류를 나눌 수 있는데, 방향이 있으면 directional graph, 없으면 undirectional graph로 볼 수 있다.
- Edge에는 단순 node간의 연결 정보만이 포함된 것이 아니라, “도로의 길이” “이동 시간”등을 표현하는 가중치(weight)를 가지고 있다. 이렇게, Weight를 이용하는 그래프를 가중치 그래프(Weighted graph)라고 한다.
- 각 node에 해당하는 edge의 정보를 나타내는 방법으로는 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)가 있는데, 각각의 시간복잡도가 다르므로 알맞게 사용하면 된다.
주요 알고리즘 1 : 최단경로 구하기
- 두 node 사이의 경로들 중 최소 비용 또는 최소 시간으로 이동할 수 있는 경로를 구하는 것으로 Weighted graph를 이용해서 구할 수 있다. 문제의 종류에 따라 다음과 같은 알고리즘으로 나눌 수 있다.
- 단일 시작점에서 구하기 : Dijkstra algorithm
- 모든 시작점에서 구하기 : Floyd algorithm
- 도달 가능성 구하기 : Floyd algorithm을 응용해서 계산
다이크스트라 알고리즘(Dijkstra)
- 시작 node를 정하면 나머지 node들이 도착 node가 되며 node 사이의 거리(weight)가 모두 양수인 경우에만 사용할 수 있다.
- 주 아이디어는 기존에 알고있는 지름길을 연장시켜 새로운 길을 찾는다는 것이다.
- ex) 시작 node를 r, 도착 node를 w, 중간 node를 v라고 해보자. 다이크스트라 알고리즘은 기존에 최단거리를 알고있는 node v를 선택한 후, v를 통해서 도착 node로 가는 경로를 탐색한다. 탐색 결과, 기존의 길보다 짧다면 경로를 변경한다.
- 기존의 지름길 선택
- 새로운 길 찾기(기존의 지름길을 바탕으로 계산)
- 평가 및 적용
- 구현
- Node들로 이루어진 집합 S를 초기화 한후, 초기에 설정된 값을 바탕으로 각 node 사이의 거리 정보 초기화
- 집합 S 중에서 최단 거리를 가지는 node를 찾아 S에서 제거 후 해당 node를 바탕으로 지름길 탐색
- 집합에 있는 모든 node를 제거할 때까지 위의 과정을 반복
플로이드 알고리즘(Floyd)
- 모든 node를 시작점으로 두고 각각에 대해서 최단 경로를 구하는 알고리즘이다.
- 주된 아이디어는 다이크스트라 알고리즘과 비슷하지만, 중간 node를 loop시켜 모든 경우를 확인한다는 것이 다르며 구현은 간단하다.
- 구현
- 3중 loop (모든 중간 node -> 모든 시작 node -> 모든 도착 node)
- 각각의 경우에 대해 계산한 거리를 평가 및 적용
- 이 알고리즘은 도달 가능성 알고리즘에도 사용될 수 있는데, 거리에 대한 정보대신에 각 중간 node에 대해 도달 가능한지 여부를 나타내는 boolean matrix를 사용하면 된다.