그래프

그래프 개념 이해하기

그래프란?

노드 vertex와 간선 edge을 이용한 비선형 데이터 구조. 노드는 정점(vertex)으로 표시된다.

• 동그라미로 표시된 것 | 노드 vertex
• 화살표로 표시된 것 | 간선 edge
• 간선 위에 숫자로 표시된 것 | 가중치 weight

그래프의 특징과 종류

방향성, 가중치, 순환 특성에 따라 종류를 구분한다.

• 방향 그래프 directed graph와 무방향 그래프 undirected graph
• 가중치 그래프 weighted graph
• 순환 그래프 cycle graph와 비순환 그래프 acyclic graph

그래프 구현 방식

인접 행렬 adjacency matrix과 인접 리스트 adjacency list가 있다.

인접 행렬 그래프

2차원 배열을 활용하여 구현하는 경우가 많다. 배열의 인덱스는 노드, 배열의 값은 노드의 가중치로 생각하고 인덱스의 세로 방향을 출발, 노드, 가로 방향을 도착 노드로 생각하면 자연스럽게 그래프를 표현할 수 있다.

장단점

• 희소 그래프(= 노드 수에 비해 간선 수가 매우 적은 그래프)를 표현하는 경우, 인접행렬은 크기가 고정되어있으므로 최악의 상황을 고려해서 노드가 n개 있을 때 n*n 크기의 인접 행렬이 필요하다. 희소그래프일 경우 대부분 공간을 실제로 사용하지 않으므로 비효율적이다.
• 노드 값의 차이가 매우 크고, 순차적으로 증가하지 않고 1, 2, 999와 같이 간격이 클 경우에는 가장 큰 노드의 값인 999를 기준으로 잡아야하므로 역시 사용되지 않는 공간이 많아 비효율적이다.
• 장점은 시간복잡도가 O(1)인 것이다. 간선의 정보를 확인할 때, 인덱스로 접근이 가능하므로 간선 정보를 바로 확인할 수 있다는점과 구현 난이도가 낮다는 장점도 있다.

인접 리스트 그래프

인접 리스트용으로 정의해야 한다. 값(v), 가중치(w), 다음 노드(next)로 묶어 관리한다. 구현 방법은 아래와 같다.

1. 노드 개수만큼 배열을 준비한다.
2. 배열의 인덱스는 각 시간 노드를 의미하며 배열의 값은 다음 노드를 연결한다.

해당 그래프를 인접리스트 그래프로 표현하면 아래 그림과 같다.

장단점

인접리스트는 인접 행렬과 정반대의 장단점을 가진다.

• 실제 연결된 노드에 대해서만 노드 값을 노드에 담아 연결하기만 하면 된다. 최악의 경우 각 노드에서 모든 노드에 간선이 연결되어 있을 때는 효율이 떨어질 수 있다.
• 간선 정보를 확인할 때는 특정 노드에서 시작하여 연결된 노드 개수가 많으면 많을수록 노드를 연결한 리스트의 길이만큼 탐색해야 하므로 탐색 시간이 O(N)이다.

인접행렬과 인접리스트

	메모리 사용	시간복잡도	기타
인접행렬	O(N^2)	O(1)	구현이 상대적으로 쉽다.
인접 리스트	O(N + M)	O(M)	M은 간선의 개수

알고리즘을 풀때 노드 개수가 1,000개 미만으로 주어지는 겨웅에는 인접 행렬을 사용하면 된다.

그래프 탐색

탐색 방법은 깊이 우선 탐색, 너비 우선 탐색이 있다.

• 깊이 우선 탐색 : 더 이상 탐색할 노드가 없을 때까지 갔다가 더 이상 탐색할 노드가 없으면 최근 방문했던 노드로 되돌아간 다음 가지 않은 노드를 방문한다.
• 너비 우선 탐색 : 현재 위치에서 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어간다. 그 노드에서 다시 가장 가까운 노드부터 모두 방문한다.

깊이 우선 탐색 depth-first search, DFS

깊이 우선 탐색을 구현하는 방법은 스택의 LIFO구조를 이용하여 탐색하는 것과 재귀를 활용하는 방법이 있다. 재귀를 활용하는 방법이 더 많이 쓰인다. 깊이 우선 탐색은 가장 깊은 노드까지 방문한 후에 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 도느가 있는지 확인하는 것이다. 탐색하고 있는 방향의 역방향으로 돌아가는 동작을 백트래킹(back tracking)이라고 한다. 코드로 구현할 때 유의 사항은 아래와 같다.

• 탐색할 노드가 없을 때까지 간선을 타고 내려갈 수 있어야 한다.
• 가장 최근에 방문한 노드르 알아야 한다.
• 이미 방문한 노드인지 확인할 수 있어야 한다.

스택을 활용한 깊이 우선 탐색

재귀 함수를 활용한 깊이 우선 탐색

재귀 함수는 호출할 때마다 호출한 함수는 콜 스택이라는 곳에 쌓이므로 깊이 우선 탐색에 활용할 수 있다.

너비 우선 탐색 breadth first search, BFS

너비 우선 탐색을 할 때 큐를 활용한다.

깊이 우선 탐색과 너비 우선 탐색 비교

깊이 우선 탐색은 깊게 탐색 후 되돌아오는 특성이 있고, 너비 우선 탐색은 시작 노드에서 인접한 노드부터 방문하는 특성을 가진다. 알고리즘 문제에서 최단 경로를 찾는 문제가 아니면 깊이 우선 탐색을 우선 고려해보는 것이 좋다. 답이 많은 경우에는 너비 우선 탐색은 답 중에서도 가장 가까운 답을 찾기 때문에, 최단 경로임을 보장한다. 너비 우선 탐색은 미로 찾기 문제에서 최단 경로를 찾거나, 네트워크 분석 문제를 풀 때 활용할 수 있다.

그래프 최단 경로( shortest path ) 구하기

최단 경로는 그래프의 종료에 따라 다르게 해석될 수도 있는 주제이다.

	목적	장단점 및 특징	시간 복잡도
다익스트라 알고리즘	출발 노드로부터 도착 노드들까지 최단 경로 찾기	음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 없다(그리디 방식)	O(V^2), 우선 순위 큐로 개선하면 O(E*logV)
벨만-포드 알고리즘	출발 노드로부터 도착 노드들까지의 최단 경로 찾기	음의 가중치를 가지는 그래프에서 최단 경로를 구할 수 있고, 음의 순환도 감지할 수 있다.	O(V*E)

참고

• 코딩테스트 합격자되기 자바스크립트편