학습개요
그래프에 대해서 할 수 있는 가장 기본적인 연산은 특정 정점이 그래프 내에 있는지 찾는 것입니다. 그러기 위해서는 그래프내의 모든 정점을 빠짐없이 그리고 중복 없이 돌아다녀야 합니다. 그것을 그래프 순회라고 합니다. 그래프 순회에는 두 가지 방법이 있습니다. 15장에서는 깊이 우선 탐색(Depth First Search; DFS)과 너비 우선 탐색(Breadth First Search; BFS)이라는 그래프 순회에 대해 설명합니다. 마지막으로 가중 그래프에서 비용이 최소인 트리를 생성하는 3가지 (프림, 크루스컬, 솔린)알고리즘을 상세하게 다루어 보겠습니다.
학습목표
- 주어진 그래프에 대해 깊이 우선 순회와 너비 우선 순회를 할 수 있다.
- 최소 비용 신장 트리가 무엇인지를 설명할 수 있다.
- 프림 크루스컬, 솔린 알고리즘을 적용하여 주어진 그래프에서 최소 비용 신장 트리를 생성할 수 있다.
연습문제
- 그래프의 모든 정점을 포함하는 사이클이 없는 부분 그래프중에서 비용이 최소인 그래프를 무엇이라고 하는가 ?
- 비용 우선 탐색 그래프
- 깊이 우선 탐색 그래프
- 너비 우선 탐색 크래프
- 최소 비용 신장 트리
–
- 그래프 순회 알고리즘의 하나로 특정 점정에서 시작하여 자손을 먼저 방문 한 후 (더 이상 방문 할 자손이 없으면) 전 단계 형제를 방문하는 탐색 방법을 무엇이라고 하는가 ?
- 너비 우선 탐색
- 깊이 우선 탐색
- 이진 탐색
- 높이 우선 탐색
–
- n개의 정점을 갖는 연결 그래프에 대한 최소 비용 신장 트리를 구하는 알고리즘이 아닌 것은 ?
- 솔린 알고리즘
- 프림 알고리즘
- 그래프 복귀 알고리즘
- 크루스컬 알고리즘
정리하기
- 그래프 내 특정 정점을 찾는 연산을 그래프 탐색이라 합니다. 그래프는 트리와 다르게 루트노드가 없으므로 시작을 나타내는 특정 정점이 주어집니다. (트리에서 노드로 부르는 것을 그래프에서는 보통 정점이라 합니다. 이 책은 그렇게 용어를 사용했습니다.)
- 특정 정점에서 시작하여 그래프의 모든 정점을 빠짐없이 그리고 중복 없이 방문하는 것을 그래프 순회라고 합니다. 그래프 탐색은 순회를 통하여 정점을 방문하다가 정해진 정점을 만나면 탐색 성공이고 모든 정점을 방문해도 정해진 정점을 만나지 못하면 실패입니다.
- 깊이 우선 탐색은 특정 점정에서 시작하여 자손을 먼저 방문 한 후 (더 이상 방문 할 자손이 없으면) 전 단계 형제를 방문하는 알고리즘입니다. 그래프는 루트가 없고 간선에 방향도 없으므로 어려워합니다. 시작 정점을 위에 올려놓고 생각하면 다소 쉬워집니다. 특히 시각적으로 더 위에 있는 것이 더 깊은 곳일 수 도 있음을 받아들이면 이해에 도움이 됩니다.
- 너비 우선 탐색은 특정 정점에서 시작하여 모든 형제를 방문한 후 자손을 방문하는 순서를 따릅니다. 자식이 여러 개인 경우 그것들의 순서를 정하는 규칙만 정하면 역시 어렵지 않게 이해 할 수 있습니다.
- 그래프의 모든 정점을 포함하는 사이클이 없는 부분 그래프 즉, 트리를 신장트리라 합니다. 그리고 가중 그래프에서 비용이 최소인 신장 트리를 최소 비용 신장 트리라 합니다. 대표적으로 프림, 크루스컬, 및 솔린 알고리즘을 사용합니다. 모두 사람 이름입니다.
- 프림 알고리즘은 최소비용을 갖는 간선을 차례로 추가하는 방법으로 트리를 구축합니다. 물론 사이클이 형성되면 해당 간선은 포기합니다. 비용이 적은 것을 합치면 그들의 합이 최소가 될 것이라는 (항상 옳지는 않은) 가정을 근거로 합니다.
- 크루스컬 알고리즘 프림 알고리즘처럼 현재 완성한 트리에 간선을 붙여 트리를 키워나가는 것이 아닙니다. 이 알고리즘은 매 단계 최소 비용 간선을 선택해 사이클만 형성하지 않으면 받아 들이는 것입니다. 그러니까 중간 과정은 (트리가 아니고) 숲 일 수 있습니다.
- 솔린 알고리즘은 앞 두 방법과 다르게 매 단계에 다수의 간선을 선택합니다. 먼저 간선이 하나도 없고 그래프의 모든 정점들로 구성된 숲에서 시작합니다. 그리고 단계가 거듭되면서 숲 내의 트리를 최소 비용을 갖는 간선으로 연결합니다. 이 과정을 남은 간선이 없거나 완전한 트리가 생성될 때까지 반복하면 신장 트리를 얻습니다.