Chapter14 그래프(Graph)

2018/03/07 - [프로그래밍/자료구조] - Chapter13 테이블(Table)과 해쉬(Hash)

14-1 그래프의 이해와 종류

그래프의 역사와 이야깃거리
버스와 지하철의 노선도, 출발지와 목적지를 정하면 그에 맞는 최적의 경로등 이러한 프로그램의 구현에 사용되는 것이 바로 그래프 알고리즘이다.

그래프 알고리즘은 수학자 '오일러(Euler)'에 의해 고안되었다. 오일러는 1736년도에 그 유명한 '쾨니히스베르크의 다리 문제'를 풀기 위해서 그래프 이론을 사용하였다.

"정점 별로 연결된 간선의 수가 모두 짝수이어야, 간선을 한 번씩만 지나서 처음 출발했던 정점으로 돌아올 수 있다."

정점 별로 연결된 간선의 수가 모두 짝수가 아니기 때문에 쾨니히스베르크의 다리에서는 처음 출발한 장소로 돌아오지 못하는 것이다.

그래프의 이해와 종류

연결 관계에 있어서 방향성이 없는 그래프를 가리켜 '무방향 그래프(undirected graph)'라 한다.

간선에 방향정보가 포함된 그래프를 가리켜 '방향 그래프(directed graph)' 또는 '다이그래프(digraph)'라 한다. 그리고 이러한 '무방향 그래프'와 '방향 그래프'는 간선의 연결형태에 따라서 '완전 그래프(complete graph)'로 구분이 된다.

이렇듯 완전 그래프란 '각각의 정점에서 다른 모든 정점을 연결한 그래프'를 뜻한다. 때문에 정점의 수가 동일한 완전 그래프라 하더라도, 방향 그래프의 간선의 수는 무방향 그래프의 간선의 수에 두배가 된다.

가중치 그래프(Weight Graph)와 부분 그래프(Sub Graph)

가중치는 두 정점 사이의 거리, 이동하는 시간 같은 정보가 될 수 있다. 원 그래프를 구성하는 정점과 간선의 일부로 이뤄진 그래프는 모두 부분 그래프가 된다.

그래프의 집합 표현

그래프는 정점과 간선의 집합이다. 따라서 집합의 표기법을 이용해서 표현할 수 있다.

그래프는 정점과 간서으로 이루어지므로, 다음과 같이 정점의 집합과 간선의 집합으로 나누어서 표현을 한다.

- 그래프 G의 정점 집합        V(G)로 표시함

- 그래프 G의 간선 집합        E(G)로 표시함

- 무방향 그래프에서 정점 A와 정점 B를 연결하는 간선을 (A, B)로 표시

- 방향 그래프에서 정점 A와 정점 B를 연결하는 간선을 <A, B>로 표시

그래프 ADT

"그래프를 생성 및 초기화 할 때 간선의 방향성 여부를 선택할 수 있고, 가중치의 부여 여부도 선택할 수 있다. 뿐만 아니라, 이후에 얼마든지 그리고 언제든지 정점과 간섭을 삽입하고 삭제할 수 있다." - 그래프의 구성이 최종목표라면 이 정도의 ADT를 기대할만하다.

그래프를 구현하는 두 가지 방법

- 인접 행렬(adjacent matirx) 기반 그래프        정방 행렬을 활용

- 인전 리스트(adjacent list) 기반 그래프           연결 리스트를 활용

14-3 그래프의 탐색

깊이 우선 탐색(Depth First Search: DFS)
연결 리스트는 노드의 연결 방향이 명확하기 때문에 탐색을 진행하는 것이 어렵지 않다. 반면 트리는 노드의 연결 방향이 일정치 않기 때문에 탐색을 진행하는 것이 복잡한 편이다.

그래프의 탐색은 그 어떤 자료구조보다도 탐색이 복잡한 편이다. 그래프의 모든 정점을 돌아다니기 위한 별도의 알고리즘 두 가지를 소개하고자 한다.

- 깊이 우선 탐색 Depth First Search: DFS

- 너비 우선 탐색 Breadth First Search: BFS

DFS의 핵심 세 가지를 비상연락망에 빗대어 정리하면

- 한 사람에게만 연락을 한다

- 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알린다.

- 처음 연락을 시작한 사람의 위치에서 연락은 끝이 안다.

너비 우선 탐색(Breadth First Search: BFS)

DFS가 한 사람에게 연락을 취하는 방식이라면, BFS는 자신에게 연결된 모든 사람에게 연락을 취하는 방식이다.

"한 사람을 기준으로 메시지를 전달하는 사람의 수(폭)"

14-4 최소 비용 신장 트리

사이클(Cycle)을 형성하지 않는 그래프

두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로'라 한다. 동일한 간선을 중복하여 포함하지 않는 경로를 가리켜 '단순 경로(simple path)'라 한다. 단순 경로이면서 시작과 끝이 같은 경로를 가리켜 '사이클(cycle)'이라 한다. 사이클을 형성하지 않는 그래프들을 가리켜 '신장 트리(spannig tree)'라 한다.

최소 비용 신장 트리의 이해와 적용

사이클을 형성하지 않는 그래프, 신장 트리의 특징 두 가지

- 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.

- 그래프 내에서 사이클을 형성하지 않는다.

가증치 그래프를 대상으로도, 간선에 방향성이 부여된 방향 그래프를 대상으로도 신장 트리를 구성할 수 있다.

그리고 신장 트리의 모든 간선의 가중치 합이 최소인 그래프를 가리켜 '최소 비용 신장 트리(minimum cost spanning tree)' 또는 '최소 신장 트리(minimum spanning tree)'라 한다. 이렇듯 줄여서 MST라 표현되는 '최소 비용 신장 트리'는 개념적으로 간단하다.

최소 비용 신장 트리의 구성을 위한 크루스칼 알고리즘1

최소 비용 신장 트리의 구성에 사용되는 대표적인 알고리즘 두 가지

- 크루스칼(Kruskal) 알고리즘

가중치를 기준으로 간선을 정렬한 후 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식

- 프림(Prim) 알고리즘

하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

크루스칼 알고리즘의 흐름에 있어서 핵심이 되는 사항

- 가중치를 기준으로 간선을 오름차순으로 정렬한다.

- 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다.

- 사이클을 형성하는 간선은 추가하지 않는다.

- 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다.

최소 비용 신장 트리의 구성을 위한 크루스칼 알고리즘2

간선을 내림차순으로 정렬하면 낮은 가중치의 간선을 하나씩 추가하는 방식이 아니라, 높은 가중치의 간선을 하나씩 빼는 방식으로 알고리즘이 전개된다. 때문에 크루스칼 알고리즘을 두 가지로 구분하기도 한다.

두 번째 크루스칼 알고리즘의 핵심

- 가중치를 기준으로 간선을 내림차순으로 정렬한다.

- 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거한다.

- 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선을 제거하지 않는다.

- 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다.