개념
그래프는 객체를 표현하는 정점(vertex)과 객체를 연결하는 간선(edge)으로 구성한다. G = (V, E)로 표현하는데 V와 E의 두 집합으로 구성된다. 여기서 V는 공집합이 아닌 정점(vertex)들의 유한 집합, E는 두 정점을 잇는 간선(Edge)들의 집합이다. V(G)는 그래프 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합을 의미한다.
종류
- 무방향 그래프(undirected graph)는 간선을 나타내는 정점의 쌍에 순서가 없는 그래프이다. 간선 (vi, vj)와 간선 (vj, vi) 는 동일한 간선으로 본다.
- 방향 그래프(directed graph)는 각 간선을 방향이 표시된 정점의 쌍 (vi, vj)으로 나타낸다. 간선 (vi, vj)와 간선 (vj, vi)는 서로 다른 간선으로 본다.간선 (vi, vj)에서 vi를 꼬리(tail), vj를 머리(head)라 한다.
- 다중 그래프(multigraph)는 두 정점 사이에 2개 이상의 간선이 존재하는 그래프이다.
- 완전 그래프(complete graph)는 정점이 n개인 무방향 그래프에서 최대 간선의 수가 n(n-1)/2인 그래프를 의미하며 방향 그래프에서는 최대 간선의 수가 n(n-1)인 그래프이다.
- 부 그래프(sub graph)는 원래 그래프에서 정점이나 간선 일부를 제외하여 만든 그래프이다.
- 가중 그래프(weight graph)는 정점을 연결하는 간선에 가중치를 부여한 그래프이다.
용어
- 경로(path)는 그래프 G의 정점 vi에서 vj에 이르는 순서이다.
- 차수(degree)는 정점에 속한 간선의 수이다.
구현
그래프는 array를 이용한 인접행렬, linked list를 이용한 인접 리스트, struct, vector 등을 이용하여 구현할 수 있다.
운행(Traversal) 방식
그래프의 운행(graph traversal)이란 그래프에 있는 모든 정점을 한 번씩 방문하는 것을 말한다. 즉, 무방향성 그래프 G(V, E)에서 V(G)에 속한 정점 V가 주어졌을 때 V에 연결된 모든 정점을 방문할 필요가 있다. 그래프의 운행 방식이란 체계적으로 그래프의 정점들을 방문하는 방법을 말한다. 그래프의 순회, 그래프의 검색, 그래프의 탐색이라고도 한다.
그래프의 운행방식에는 깊이 우선 검색(DFS)와 너비 우선 검색(BFS)의 두 가지 방법이 있다.
깊이 우선 검색(DFS, Depth First Search)
무방향성 그래프 G(V, E)에서 시작 정점 V를 결정하여 검색한다. 정점 V에 인접된 정점 중에서 검색되지 않은 정점 W를 선택한다. 모든 인접 정점을 검색한 정점 V를 만나면 검색되지 않은 인접 정점을 가졌던 마지막 정점으로 되돌아가서 시작한다. 더 이상 검색할 정점이 없으면 종료한다. 즉, 한 정점으로부터 시작하여 그것에 인접한 노드를 방문하고 그 노드에서 다 방문하지 않은 노드를 계속 방문하여 전 노드를 방문한다. DFS 알고리즘은 순환적이고, 스택을 이용한다.
너비 우선 검색(BFS, Breadth First Search)
무방향성 그래프 G(V, E)에서 시작 정점 V를 결정하여 검색한다. 정점 V에 인접된 정점 중에서 검색하지 않은 모든 정점을 검색하고, 다시 이 정점에 대하여 인접하여 검색하지 않은 모든 정점에 대하여 검색을 계속한다. 더 이상 검색할 정점이 없으면 종료한다. BFS 알고리즘은 반복적이고, 큐를 이용한다.
신장 트리(Spanning Tree)
그래프 G가 연결되어 있을 때, DFS나 BFS을 통해 어떤 점에서 시작하든 G에 있는 모든 정점을 방문한다. 이 경우에 G의 간선들은 2개의 집합 T와 B로 나눌 수 있는데, T는 검색 중에 지나간 간선들의 집합이고, B는 나머지 간선들의 집합이다. 집합 T에 있는 간선들은 G의 모든 정점을 포함하는 트리를 형성한다. 이때 G에 있는 간선과 G의 모든 정점으로 구성된 트리를 신장 트리(spanning tree)라고 한다. 정점이 n개이고 간선이 n-1인 사이클이 없는 단순 연결 그래프를 말하며, 그래프에 있는 간선과 모든 정점으로 구성된 트리로 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다.
DFS를 통해 만든 신장 트리를 깊이 우선 신장 트리(depth first spanning tree)라고 한다. BFS를 통해 만든 신장 트리를 너비 우선 신장 트리(breadth first spanning tree)라고 한다.
최소 비용 신장 트리(MST, Minimum-cost Spanning Tree)
간선이 가중값(weight)을 갖는 그래프를 네트워크(network)라고 한다. 간선에 비용이 부여되어 있을 때 신장 트리의 비용이란 그 트리의 모든 간선 비용의 총합을 말한다. 다수의 신장 트리 중에서 그 비용의 총합이 최소가 되는 트리를 최소 비용 신장 트리(MST, Minimum-cost Spanning Tree)라고 한다. 최소 비용 신장 트리를 찾는 방법에는 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim Algorithm)이 있다.
크루스칼 알고리즘(Kruskal Algorithm)
그래프 G(V, E)에 대하여 매 단계에서 최소 가중치를 갖는 간선을 택하여 신장 트리의 간선이 되게 한다. 이 떄 선택된 간선이 사이클이 되면 배제시킨다. 이와 같은 과정을 n-1개의 간선이 신장 트리에 포함될 때까지 수행한다.
프림 알고리즘(Prim Algorithm)
그래프 G=(V, E)에 대하여 어떤 시작 정점에서부터 출발하여 신장 트리의 집합을 확장해 나가는 방법이다. n개의 정점을 가진 신장 트리의 집합에서 처음에는 시작 정점만을 신장 트리 집합에 포함시키며, 인접한 정점들과의 최소 비용 간선을 선택하고 그 간선을 포함하는 정점을 선택해 나가서 트리가 n-1개의 간선을 가질 때까지 완성시키는 방식이다.
최단 경로(Shortest Paths)
그래프에서 두 정점 사이에 있는 각 간선에 가중값(weight)이 주어지고 정점 Vi와 Vj 사이에 하나 이상의 경로가 존재할 때 그 경로 중에서 값의 합계가 최소인 경로를 최단 경로라고 한다. 최단 경로를 찾는 방법에는 다익스트라 알고리즘(Dijkstra Algorithm)과 플로이드 알고리즘(Floyd Algorithm)이 있다.
다익스트라 알고리즘(Dijkstra Algorithm)
하나의 출발점에서 모든 종착점(Single Source All Destination)을 구하는 방식이며, 방향 그래프 G=(V, E)에서 두 정점 사이의 각 간선에 가중값(weight)이 주어지고 출발 정점 V0가 주어졌을 때 V0부터 시작하여 그래프 G의 남은 정점들로 가는 각각의 경로들 중에서 가장 짧은 경로들을 찾는 문제이다.
플로이드 알고리즘(Floyd Algorithm)
모든 쌍의 최단 경로(All Pair Shortest Paths)를 구하는 방식이며, 방향 그래프 G=(V, E)에서 i ≠ j인 모든 정점들의 쌍 Vi, Vj 사이에 최단 경로를 찾는 문제이다. k-최단 경로라고도 한다.
댓글