알고리즘(14) - 그래프

그래프는 정점 vertex와 간선 edge로 사물과 현상을 표현한 것이다. 이전에 다뤘기에 세세한 것은 넘어가겠다.

 

그래프의 표현

---

그래프를 표현하는 방법 중에는 인접 행렬, 인접 리스트, 인접 배열, 인접 해시테이블이 있다. 

 

인접행렬은 간선 수 이상의 공간을 차지하고, 인접리스트는 특정 간선 존재 여부를 검사하는 데에 오래 걸린다. 이 두 단점을 커버할 수 있는 표현은 인접 배열이다.

인접배열은 정점 N개일 때 N개의 인접배열로 표현하는 것이다. 즉, 인접한 정점의 갯수만큼 배열을 또 생성한다. 인접리스트를 배열로 표현한다면 이해가 쉬울 것이다. 이때 간선 존재 여부의 수행시간은 O(log k)이다.

 

인접 해시테이블은 각 정점마다 인접배열을 두는 대신 하나의 해시 테이블을 사용하는 것이다. 인접한 정점이 n개이면 n개의 해시테이블을 사용하므로 간선 존재 여부를 알아내는 연산은 효율적이다. 다만 인접한 정점을 차례로 봐야 하는 경우는 적합하지 않다.

 

 

그래프 관련 알고리즘

---

그래프 순회

대표적으로 두 가지가 있다. BFS와 DFS. 모든 정점을 한 번씩 방문하도록 순회 알고리즘을 짜야 한다면 이 두 방법이 있다. 빠른 이해를 위해 큐를 이용하여 구현한 BFS의 작동 예를 알아보자.

너비우선탐색 BFS

BFS와는 다르게 DFS는 인접한 정점 하나를 정하고 그 정점의 인접한 마지막 정점까지 본 뒤에 다시 처음으로 돌아와 다른 정점들을 살펴본다. 

이 두 방법의 수행시간은 다음과 같다.

Θ(V+E) 정점의 갯수와 간선의 갯수를 합친 시간과 같다.

 

 

최소 신장 트리

신장트리란 무향 연결 그래프 undirected connected graph이어야 하며, 트리로써는 사이클이 없는 연결 그래프이어야 한다.

최소 신장 트리란, 무향 가중 연결 그래프의 신장 트리들 중 간선의 가중치 합이 최소인 것이다. 

이러한 최소 신장 트리를 구하는 알고리즘을 알아보자.

 

• Prim 알고리즘 : 임시적인 정점 집합 S를 공집합에서 시작하여 그래프의 모든 정점을 포함할 때까지, 즉 S=V가 될 때까지 키워간다. 
  • 공집합 S에서 시작정점을 r을 넣는다고 했을 때 r에 연결된 간선 중에 최소비용인 간선을 채택하고, 모든 간선이 연결될 때까지 반복한다.
  • 수행시간은 O(E log V)
• kruskal 알고리즘 : 공집합인 간선 집합 T를 사이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 추가해 나가서 V-1개가 되면 완료한다.
  • 모든 간선을 가중치 크기로 오름차순 정렬해 배열 A에 저장한다.
  • 수행시간은 O(E log V)다.

 

 

위상 정렬

위상정렬이란,  모든 정점을 일렬로 나열하되, 정점 x에서 정점 y로 가는 간선이 있으면 x를 y보다 앞에 놓도록 한다.

기본적인 조건으로 사이클이 없는 유향그래프, 즉 DAG여야 한다.

한 가지 참고사항은 DAG에 하나 이상의 위상 순서가 존재할 수 있다. 이는 즉슨 위상정렬 결과는 여러 가지일 수 있다.

 

연결 그래프

위의 그래프를 위상정렬하면 다음과 같다.

 

 

위상정렬 알고리즘은 2가지로 구현할 수 있다.

topologicalSort1(G)
{
	for i ← 1 to n { ▷ n : 정점 수
	진입간선이 없는 정점 u 선택;
	A[i] ← u;
	정점 u와, u의 모든 진출간선 제거;
	}
}

topologicalSort2(G)
{
	for each v∈V
		visited[v] ← NO;
	for each v∈V 
		if (visited[v] = NO) then DFS-TS(v) ;
}
DFS-TS(v) //기존 DFS와 동일하다.
{
	visited[v] ← YES;
	for each x∈L(v) ▷ L(v): v의 인접 리스트
		if (visited[x] = NO) then DFS-TS(x) ;
	연결 리스트 R의 맨 앞에 정점 v를 삽입; -> DFS에 이 부분만 추가해야 한다.
}

위 둘 다 수행시간은 Θ(|V| + |E|)이다.

 

 

 

최단 경로

간선 가중치가 있는 유향 그래프여야 하며, 무향 그래프라면 양쪽으로 유향간선이 있다고 간주하면 된다.

최단 경로는 두 정점 사이의 가중치 합이 최소인 경로를 의미한다. 허나 간선 가중치의 합이 음인 사이클이 있다면 문제가 정의되지 않는다.

 

• 하나의 시작 정점에서 각 정점에 이르는 최단 경로를 구할 수 있다.
  • 다익스트라 알고리즘 - 음의 가중치를 허용하지 않는다.
  • 벨만-포드 알고리즘
  • DAG의 최단 경로
• 모든 정점 쌍 사이의 최단 경로를 구할 수 있다.
  • 플로이드-워샬 알고리즘 

 

이제 각 알고리즘을 알아보겠다.

 

• 다익스트라 알고리즘 : 모든 간선의 가중치는 음이 아니어야 한다는 조건이 필요한다. 최단경로를 구하려면 prim알고리즘과 비슷한데, 시작 정점에서 정점 v에 이르는 최단거리를 골라야 한다. 수행시간은 O(|E|logV)
• 벨만-포드 알고리즘 : 간선 가중치가 임의의 실수인 경우에 사용하며 음의 가중치를 허용한다. 간선을 최대 |V|-1개를 사용하는 최단 경로를 구한다. 음의 사이클이 존재하지 않으면 최종해답이 된다. 수행시간은 O(|E||V|)
• 플로이드-워샬 알고리즘 : 모든 정점들간의 상호 최단경로를 구하는 알고리즘이다. 동적프로그래밍을 이용하기 때문에 수행시간은 Θ(n^3)이 걸린다.