트리의 활용

생성트리

• Spanning Tree, 신장트리
• 그래프의 모든 노드를 포함하는 트리
• 최소생성트리: 가중 그래프에 대하여 연결선의 가중치의 합을 최소로 하는 생성트리
  • 네트워크나 도로망 설계 시 비용을 최소로 하거나 효율성을 최대로 하는 경로를 고려할 때 유용
  • 최소생성트리를 구하는 알고리즘: 프림 알고리즘, 크루스칼 알고리즘

프림 알고리즘

• Prim Algorithm
• 주어진 가중치 그래프 G에서 최소신장트리를 프림 알고리즘으로 구하는 규칙
  1. 그래프에서 임의의 노드 하나를 선택
  2. 선택된(연결된) 노드들과 연결된 모든 변들 중 가중치가 가장 작은 변을 선택
  3. 가중치가 같은 변은 임의로 하나를 선택
  4. 순환이 형성되는 경우는 그 변은 선택하지 않음
  5. 그래프 G에 포함된 모든 꼭짓점의 수가 n개일 때, n-1개의 변이 연결될 때까지 2~4의 과정을 반복

크루스칼 알고리즘

• Kruskal Algorithm
• 주어진 가중치 그래프 G에서 최소신장트리를 크루스칼 알고리즘으로 구하는 규칙
  • 가중치가 가장 작은 모서리를 차례로 선택
  • 가중치가 같은 모서리는 모두 선택
  • 선택된 모서리에 의해 순환이 형성되는 경우는 선택하지 않음
  • 그래프 G에 포함된 모든 꼭짓점의 수가 n개일 때, n-1개의 모서리가 연결되면 종료

허프만 알고리즘

• 발생 빈도가 높은 문자는 적은 비트를 할당하고 발생 빈도가 낮은 문자에는 많은 비트를 할당하는 알고리즘
  1. 발생 빈도가 가장 낮은 두 문자를 선택하여 하나의 이진트리를 생성
     • 왼쪽 노드에 빈도 수가 낮은 문자, 오른쪽 노드에 빈도 수가 높은 문자를 위치시킴
     • 빈도 수가 같은 경우에는 사전적으로 앞에 오는 문자를 왼쪽에 위치시킴
     • 두 문자의 빈도의 합을 그 문자들의 부모 노드로 함
  2. (1)의 과정을 모든 문자가 하나의 이진트리로 묶일 때까지 반복
  3. 생성된 이진트리의 왼쪽 노드에는 0, 오른쪽 노드에는 1을 부여
  4. 루트부터 해당 문자까지의 0 또는 1을 순서대로 나열
• 0과 1로 나열된 코드를 허프만 코드라고 함 (허프만 코딩 트리) → 이진트리는 각 글자의 빈도가 알려져 있는 메시지의 내용을 압축하는데 사용될 수 있음