그래프

그래프

그래프

그래프 G는 노드 V와 간선 E의 집합으로 정의된다.

최소신장트리(Minimum Spanning Trees)

조건: 무향 연결 그래프(connected graph): 모든 정점 간에 경로가 존재하는 그래프

최소 신장 트리를 구하는 대표 알고리즘:

1. Prim's Algorithm
2. Kruskal's Algorithm

필수 용어:

• 트리: 싸이클이 없는 연결 그래프이다. n개의 정점을 가진 트리는 항상 n-1개의 간선을 갖는다.

• 신장: 모든 노드를 포함한다는 의미이다.

• 그래프 (G)의 신장 트리: G의 정점들과 간선들로만 구성된 트리이다.

  • Ex. 만약, 노드가 4개인 그래프 G의 신장 트리를 만든다면, 신장 트리는 반드시 4개의 노드를 포함하고 있어야 한다.
  • 주의할 점: 신장 트리는 트리의 일종이기 때문에 그래프와 트리의 차이인순환 구조를 가지면 안된다.

• G의 최소 신장 트리: G의 신장 트리들 중 간선의 합이 최소인 신장 트리이다.

---

프림(Prim) 알고리즘

• 기본적인 아이디어: S라는 집합을 유지하는 것이다.

• S는 공집합으로 시작하고, 모든 정점 V를 포함할 때 종료(집합 S의 개수 = 정점 V의 개수 )한다.

• 특징:

  • 최적해를 보장하는 그리디 알고리즘이다.

  • 힙을 이용한다.

• 수행시간: O(|E|log|V|)

  cf) E = 간선의 수, V: 정점의 수

알고리즘 사고 순서:

1. S를 공집합으로 만든다.

2. V의 모든 노드 값을 무한대로 설정한다.

3. 임의의 정점(r)을고른 후, 방문했음(=V 노드의 무한 값을 0으로 바꿔준다) 을 표시한다.

4. 해당 정점에 연결된 모든 간선 중에서 가장 **최소 비용을 가진 간선**을 선택한다.

5. 간선에 연결된 새로운 노드(y)를 집합 S에 추가하고, 방문했음(=y 노드의 값을 간선의 비용으로 바꿔준다 = 이완(relaxation))을 표시한다.

   • 더 이상 연결될 수 있는 간선이 없는 경우, y는 배열에서 더이상 신경 쓰지 않아도 된다.
   • 남은 노드의 개수: (V - S)

6. r과 y가 있는 집합 S를 하나의 큰 정점이라고 생각하고, 이를 기준으로 이어져 있는 간선의 값을 리스트에 넣어준다.

   = 골라야 할 선택지를 만들어 준 것이다. 만일 하나의 노드에 연결된 간선이 여러 개라면 작은 값을 넣어준다.

7. 리스트에 넣어준 값들 중 최소 값을 골라준다

8. 만일 S집합에 6번에서 선택지를 만들어주기 넣어준 노드의 값보다 새롭게 구하는 값이 더 작다면, 작은 값을 노드에 바꿔서 넣어준다.

9. S 집합의 개수가 V 정점의 개수와 같을 때까지 반복한다.