그래프(Graph)

 

그래프^(graph) - 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조

그래프 G - 객체를 나타내는 정점^(vertex)과 객체를 연결하는 간선^(edge)의 집합

---

그래프의 종류

• 무방향 그래프^{(undirected graph)} - 두 정점을 연결하는 간선에 방향이 없는 그래프
• 방향 그래프^{(directed graph)}, 다이 그래프^(digraph) - 두 정점을 연결하는 간선에 방향이 있는 그래프
• 완전 그래프^{(complete graph)} - 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선의 수를 갖는 그래프
• 부분 그래프^(subgraph) - 원래 그래프에서 간선이나 정점을 일부만 제외하여 만든 그래프
• 가중 그래프^{(weight graph)}, 네트워크^(network) - 정점을 연결하는 간선에 가중치^(weight)를 할당한 그래프
• 연결 그래프^{(connected graph)} - 모든 정점이 간선으로 연결되어 있는 그래프
• 단절 그래프^{(disconnected graph)} - 연결되지 않은 정점이 있는 그래프

---

그래프의 차수^(degree) - 정점에 부속^(incident)되어 있는 간선의 수

방향 그래프의 차수 : 진출차수^(in-degree) + 진입차수^(out-degree)

---

그래프의 경로^(path) - 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것

단순 경로^{(simple path)} - 모두 다른 정점으로 구성된 경로

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

DAG^{(Directed Acyclic Graph)} - 방향 그래프이면서 사이클이 없는 그래프

---

그래프의 순회^{(graph traversal)()}, 탐색^{(graph search)} - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산

 

그래프 순회, 탐색 방법

깊이 우선 탐색^{(DFS : Depth First Search)}

1. 시작 정점 v를 선택하여 방문한다.
2. v에 인접한 정점 중에서 방문하지 않은 정점 w가 있다면, 스택에 정점 v를 push하고, w를 방문한 후 w를 v로 하여 2번을 다시 수행한다. 
3. v에 인접한 정점 중에서 방문하지 않은 정점이 없다면, 스택을 pop하여 얻어진 가장 마지막으로 방문한 정점을 v로 하여 2번을 다시 수행한다.
4. 스택이 공백이 될 때까지 2, 3번을 반복한다.

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

1.  시작 정점 v를 선택하여 방문한다.
2. v에 인접한 정점 중에서 방문하지 않은 정점을 차례대로 방문하여 큐에 enQueue한다.
3. 방문하지 않은 정점이 없다면, 큐를 deQueue하여 얻어진 정점을 v로 하여 2번을 다시 수행한다.
4. 큐가 공백이 될 때까지 2, 3번을 반복한다.

---

신장 트리^{(spanning tree)} - n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리

• 깊이 우선 신장 트리^{(depth first spanning tree)} - 깊이 우선 탐색을 이용하여 생성된 신장 트리
• 너비 우선 신장 트리^{(breadth first spanning tree)} - 너비 우선 탐색을 이용하여 생성된 신장 트리
• 최소 비용 신장 트리^{(minimum cost spanning tree)} - 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

최소 비용 신장 트리를 만드는 알고리즘

• 크루스칼^(Kruskal)의 알고리즘 Ⅰ, Ⅱ
• 프림^(Prime)의 알고리즘

크루스칼 알고리즘 Ⅰ

1. 그래프 G를 구성하는 모든 간선들을 가중치에 따라 내림차순으로 정렬한다.
2. 그래프 G에서 가중치가 가장 높은 간선을 삭제한다. 이때 정점을 그래프와 분리시키는 간선을 삭제하면 안되기 때문에 이럴 경우 다음으로 가중치가 높은 간선을 삭제한다.
3. 그래프 G의 간선의 수가 n-1개가 될 때까지 2번을 반복한다.
4. 그래프 G의 간선의 수가 n-1개가 되면 최소 비용 신장 트리가 완성된다.

크루스칼 알고리즘 Ⅱ

1. 그래프 G를 구성하는 모든 간선들을 가중치에 따라 오름차순으로 정렬한다.
2. 그래프 G에서 가중치가 가장 낮은 간선을 삽입한다. 이때 사이클이 생성되는 간선이 삽입되면 안되기 때문에 이럴 경우 다음으로 가중치가 낮은 간선을 삽입한다.
3. 그래프 G의 간선의 수가 n-1개가 될 때까지 2번을 반복한다.
4. 그래프 G의 간선의 수가 n-1개가 되면 최소 비용 신장 트리가 완성된다. 

프림 알고리즘

1. 그래프 G에서 시작 정점을 선택한다.
2. 선택된 정점에 부속되어 있는 모든 간선들 중에서 가중치가 가장 낮은 간선을 삽입하여 트리를 확장한다.
3. 이전에 선택되었던 정점과 새로 확장된 정점에 부속되어 있는 모든 간선들 중에서 가중치가 가장 낮은 간선을 삽입한다. 이때 사이클이 생성되는 간선이 삽입되면 안되기 때문에 이럴 경우 다음으로 가중치가 낮은 간선을 삽입한다.
4. 그래프 G의 간선의 수가 n-1개가 될 때까지 3번을 반복한다.
5. 그래프 G의 간선의 수가 n-1개가 되면 최소 비용 신장 트리가 완성된다.