그래프(Graph)란?

그래프(Grpah)란 연결 관계를 저장할 수 있는 자료 구조를 의미한다.

그래프에서 하나의 데이터 단위를 나타내는 객체를 노드라고 한다. 위 그림에서 하나의 유저가 하나의 노드다. 

두 노드의 직접적인 연결 관계를 엣지라고 한다. 위 그림에서 흰 선들이 그래프의 엣지에 해당한다.

두 노드 사이에 엣지가 있을 때 두 노드는 인접해 있다고 표현한다.

 

엣지가 갖는 특성에 따라 그래프의 종류를 세부적으로 구분할 수 있다.

우선, 엣지들이 방향을 가지고 있을 경우 방향 그래프라고 한다.

방향 그래프를 통해 인스타그램의 팔로우 관계처럼 한 유저가 다른 유저를 팔로우하는 일방적인 관계를 나타낼 수 있다.

엣지들의 연결 관계뿐만 아니라 어떤 정보를 나타내는 수치를 갖는 그래프를 가중치 그래프라고 한다.

예를 들어, 인천-LA는 9시간, 인천-뉴욕은 13시간이 걸린다고 했을 때, 각각의 시간들이 두 도시 간의 가중치가 될 수 있다.

 

하나의 노드에 연결된 엣지들의 수를 차수라고 한다. 위 그림에서 현승 노드의 차수는 3, 영훈 노드의 차수는 2이다.

한 노드에서 다른 노드까지 가는 길을 경로라고 한다. 예를 들어 지웅에서 규리까지 가는 길은 지웅-소원-규리 노드 순으로 표현할 수 있는데 이런 길을 경로라고 한다. 경로의 거리는 비가중치 그래프의 경우 한 경로에 있는 엣지의 수로서 가중치 그래프의 경우 한 경로에 있는 엣지의 가중치의 합으로 계산한다.

 

그래프에서 탐색이란 하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것을 의미한다.

대표적인 두 가지 탐색 방법으로 BFS와 DFS가 있다. 그 과정을 간단히 정리하자면 아래와 같다.

BFS
시작 노드를 방문 표시 후, 큐에 넣는다.
큐에 아무 노드가 없을 때까지 아래 과정을 반복한다.
1) 큐의 가장 앞 노드를 꺼낸다. 
2) 꺼낸 노드에 인접한 노드들을 모두 확인한다.
3) 처음 방문한 노드면 방문한 노드 표시를 하고 큐에 넣는다.

DFS
시작 노드를 스택에 넣는다.
스택에 아무 노드가 없을 때까지 아래 과정을 반복한다.
1) 스택 가장 위 노드를 꺼낸다.
2) 노드를 방문 표시한다.
3) 인접한 노드를 모두 확인하면서 처음 방문하거나 스택에 없는 노드면 스택에 넣어준다.

 

최단 경로란 두 노드 사이 경로 중 가장 거리가 짧은 경로를 의미한다.

최단 경로 알고리즘은 일반적으로 비가중치 그래프에서는 BFS를, 가중치 그래프에서는 Dijkstra를 이용한다.

BFS
시작 노드를 방문 표시 후, 큐에 넣는다.
큐에 아무 노드가 없을 때까지 아래 과정을 반복한다.
1) 큐의 가장 앞 노드를 꺼낸다.
2) 꺼낸 노드에 인접한 노드들을 모두 확인한다.
3) 처음 방문한 노드면 방문한 노드 표시를 한다.
4) predecessor 변수를 큐에서 꺼낸 노드로 설정하고 큐에 넣어준다.

Dijkstra
시작 노드의 distance를 0으로 predecessor를 None으로 지정한다.
모든 노드가 complete 될 때까지 아래 과정을 반복한다.
1) complete하지 않은 노드 중 distance가 가장 작은 노드를 선택한다.
2) 이 노드에 인접한 노드 중 complete하지 않은 노드를 돌면서 각 엣지를 relax 한다.
3) 현재 노드를 complete 처리한다.

 

BFS와 Dijkstra 모두 최단 경로를 확인하기 위해서 아래의 Backtracking 과정을 갖는다.

Backtracking
현재 노드를 경로에 추가한다.
현재 노드의 predecessor로 간다.
predecessor가 없을 때까지 위 단계를 반복한다.

 

▶ 관련 링크