그래프 이론과 알고리즘 개념정리

1. 그래프의 개념

그래프(graph)는 원소 간의 관계를 표현하는 비선형 자료구조이다.

그래프는 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다.

 

G=(V,E) 에서

G - 그래프

V - 정점의 집합

E - 정점을 연결하는 간선의 집합

 

2. 그래프의 종류

2.1 무방향 그래프

무방향 그래프(Undirected Graph)는 두 정점을 연결하는 간선에 방향이 없는 그래프이다.

 

2.2 방향 그래프

방향 그래프(Directed Graph)는 간선에 방향..0이 있는 그래프이다.

정점 V(i) 에서 정점V(j)를 연결하는 경우 V(i)를 꼬리(tail) 이라 하고 V(j)를 머리(head) 라고 한다.

 

2.3 완전 그래프

완전 그래프(Complete Graph)는 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프이다.

정점이 n개인 완전 그래프중에서 무방향그래프의 최대 간선 수의 공식은 n(n-1)/2개 이다.

정점이 n개인 완전 그래프중에서 방향 그래프의 최대 간선 수의 공식은 2배 많은 n(n-1)개 이다.

 

2.4 부분 그래프

원래 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프를 부분 그래프(Subgraph)라고 한다.

 

2.5 가중 그래프

정점을 연결하는 간선에 가중치(weight)를 할당한 그래프를 가중치 그래프(Weight Graph)라고 한다.

여기서 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있다.

 

3. 그래프 관련 용어

인접 - 간선으로 연결되어 있는 두 정점의 관계를 뜻한다.

부속 - 두 정점을 연결한 간선의 관계를 뜻한다.

차수 -정점에 부속되어 있는 간선의 수를 뜻하며 방향 그래프에서는 추가로 진입 차수와 진출차수로 구분한다.

진입 차수 - 방향 그래프에서 정점을 머리로 하는 간선의 수(정점이 B라면 B로 가는 간선의 차수)

진출 차수 -방향그래프에서 정점을 꼬리로 하는 간선의 수 (정점이 B라면 B에서 나가는 간선의 차수)

* 방향 그래프에서 정점의 차수는 진입 차수와 진출 차수의 합이 된다.

 사이클 - 단순 경로 중에서 경로의 시작정점과 마지막 정점이 같은 경로

 

4. 그래프 구현 방식

그래프 구현 방식은 2가지가 있다.

1. 순차 자료구조를 이용하는 2차원 배열의 인접 행렬방법

2. 연결 자료구조인 연결 리스트를 사용한 인접 리스트 방법

 

5. 그래프 순회의 종류

5.1 깊이 우선 탐색(DFS)

DFS란 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속하여 결국 모든 정점을 방문하는 순회 방법이다.

즉, 모든 경우의 수롤 탐색한다고 보면 된다. 탐색과정에서는 후입선출 구조인 stack을 사용한다.

 

5.2 너비 우선 탐색(BFS)

BFS란 시작 정점에 인접한 정점을 모두 차례로 방문하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례로 방문하는 방식으로, 가까운 정점을 먼저 방문하고 멀리 있는 정점을 나중에 방문하는 순회 방법이다. 탐색과정에서는 선입선출의 구조인 Queue를 사용한다.

 

6. 신장트리

6.1 신장트리의 개념

모든 정점이 n개인 무방향 그래프에서 정점이 n개이고 간선이 n-1개인 트리 형태의 부분 그래프를 뜻한다.

즉, 신장트리는 간선을 최소로 이용하여 모든 정점을 연결한 그래프이다.

신장트리의 순회 역시 깊이 우선 신장트리와 너비 우선 신장트리로 나뉜다.

 

6.2 최소비용 신장트리

가중치 합이 최소인 신장트리를 최소 비용 신장트리라고 한다.

이때, 무방향 가중치 그래프에서 신장 트리 비용은 신장 트리를 구성하는 간선 n-1개의 가중치를 합한 값이 된다.

 

6.3 크루스칼 알고리즘1

크루스칼 알고리즘1은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만든다.

1) 그래프의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.

2) 가중치가 가장 높은 간선을 순서대로 제거하되 단절그래프가 되지 않는다는 전제하에 제거한다.

3) 정점이 n개라면 간선이 n-1개가 될 때까지 2번을 반복한다.

 

6.4 크루스칼 알고리즘2

크루스칼 알고리즘2는 가중치가 낮은 간선을 삽입하면서 최소비용 신장 트리를 만든다.

1) 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.

2) 가중치가 낮은 간선을 순서대로 삽입하되 사이클이 생성되지 않는다는 전제하에 삽입한다.

3) 정점이 n개라면 간선이 n-1개가 될 때까지 2번을 반복한다.

 

6.5 프림 알고리즘

프림 알고리즘은 크루스칼 알고리즘과 다르게 간선을 간선을 정렬하지 않고, 하나의 정점에서 시작하여 트리를 확장해 나가는 방법이다.

1) 시작정점을 선택한다.

2) 선택한 정점에서 부속된 간선 중 가중치가 가장 낮은 간선을 연결하여 트리를 확장한다.

3) 현재 연결되어 있는 정점들 중에서 가중치가 낮은 간선을 삽입하되 사이클이 생성되지 않는다는 전제하에 삽입한다.

4. 정점이 n개라면 간선이 n-1개가 될 때까지 3번을 반복한다.

 

7. 최단경로

최단 경로란 신장 트리가 아닌 가중치 그래프에서 가중치의 합이 최소인 경로이다.

최단 경로를 구하려는 가중치 그래프의 가중치는 가중치 인접행렬에 저장하며 저장과정에서 두 정점 사이에 간선이 없다면 무한대 값을 저장하고 자기자신과의 연결 부분 값은 0을 저장한다.

 

7.1 다익스트라 최단 경로 알고리즘

최단 경로를 구할 때 사용하는 알고리즘이다.

1) 경로 길이를 저장할 distance배열을 무한대 값으로 초기화한다.

2) 시작정점의 distance를 0으로 초기화하고 집합 S에 추가한다.

3) 집합 S에 속하지 않은 정점 중에서 distance가 최소인 정점 u를 찾아 집합 S에 추가한다. 

4) 새로운 정점 u가 추가되면 , u에 인접하고 집합 S에 포함되지 않는 정점 w의 값을 해당 점화식에 맞춰 수정하며 모든 정점이 집합 S에 추가될 때 까지 반복한다.

 

점화식

distance[w] <- min(distance[w], distance[u] + weight[u][w])

 

7.2  플로이드 최단 경로 알고리즘

최단 경로를 구할 때 사용하는 알고리즘이다.

1) 인접 행렬을 만든다.

2) 두 정점 사이의 최단경로에서 각 정점을 거쳐서 가는 경로를 고려하여 가중치를 인접행렬에 저장된 가중치 값을 비교하고 최단경로를 수정한다.

3) a~ d의 정점이 있다는 가정하에 2단계에서 a를 거쳐서 가는 경로를 고려하여 인접행렬 값을 수정했다면 다음번에는 정점 b를 거쳐서 가는 경우를 고려하여 최단경로를 수정한다. 이 과정을 d단계 까지 반복한다.