프뤼퍼(Prüfer) 코드는 레이블이 붙은 트리(tree)를 고유한 수열 하나로 표현하는 방법입니다. 사용자가 그래프 형태로 입력한 트리에서 노드에 1부터 p까지의 레이블이 붙어 있다면, 이 트리는 길이가 p − 2인 수열로 유일하게 식별됩니다. 즉, 정점이 n개인 트리는 항상 n−2개의 값으로 이루어진 프뤼퍼 코드를 가지며, 서로 다른 트리는 반드시 서로 다른 코드를 갖습니다.
프뤼퍼 코드를 만드는 기본 원리는 다음과 같습니다.
① 현재 남아 있는 리프(leaf, 차수가 1인 정점) 중에서 레이블이 가장 작은 정점을 찾습니다.
② 해당 리프를 제거하고, 그 리프와 연결되어 있던 이웃 정점의 번호를 코드에 기록합니다.
③ 정점이 2개만 남을 때까지 이 과정을 반복합니다.
알고리즘
Begin
i, j, ver, edg, minimum, p를 정수형으로 선언한다.
"정점의 개수를 입력하세요: "를 출력한다.
ver 값을 입력받는다.
edg = ver - 1 로 초기화한다.
EDG[edg][2], DG[ver+1]을 정수형으로 선언하고 DG[ver+1] = {0} 으로 초기화한다.
"이 트리는 (ver)개의 정점에 대해 (edg)개의 간선을 가집니다."를 출력한다.
"트리에는 (edg)개의 정점 쌍이 있습니다."를 출력한다.
for(i = 0; i < edg; i++)
"간선 (i+1)의 정점 쌍 값을 입력하세요."를 출력한다.
"V(1) 정점의 값을 입력하세요: "를 출력하고 EDG[i][0] 값을 입력받는다.
"V(2) 정점의 값을 입력하세요: "를 출력하고 EDG[i][1] 값을 입력받는다.
DG[EDG[i][0]]++ , DG[EDG[i][1]]++ 로 각 정점의 차수를 증가시킨다.
"트리의 프뤼퍼 코드는 다음과 같습니다: { "를 출력한다.
for(i = 0; i < ver-2; i++)
minimum = 10000
for(j = 0; j < edg; j++)
if(DG[EDG[j][0]] == 1) 이면
if(minimum > EDG[j][0]) 이면
minimum = EDG[j][0], p = j
if(DG[EDG[j][1]] == 1) 이면
if(minimum > EDG[j][1]) 이면
minimum = EDG[j][1], p = j
DG[EDG[p][0]]-- , DG[EDG[p][1]]-- 로 선택된 간선의 양 끝 정점 차수를 감소시킨다.
if(DG[EDG[p][0]] == 0) 이면
EDG[p][1] 값을 출력한다.
else
EDG[p][0] 값을 출력한다.
"}"를 출력한다.
End.
C++ 예제 코드
#include<iostream>
using namespace std;
int main() {
int i, j, ver, edg, minimum, p;
cout<<"정점의 개수를 입력하세요: ";
cin>>ver;
cout<<endl;
edg = ver-1;
int EDG[edg][2], DG[ver+1] = {0};
cout<<"이 트리는 "<<ver<<"개의 정점에 대해 "<<edg<<"개의 간선을 가집니다.\n";
cout<<"트리에는 "<<edg<<"개의 정점 쌍이 있습니다.\n";
for(i = 0; i < edg; i++) {
cout<<"간선 "<<i+1<<"의 정점 쌍 값을 입력하세요:\n";
cout<<"V(1) 정점의 값을 입력하세요: ";
cin>>EDG[i][0];
cout<<"V(2) 정점의 값을 입력하세요: ";
cin>>EDG[i][1];
DG[EDG[i][0]]++;
DG[EDG[i][1]]++;
}
cout<<"\n트리의 프뤼퍼 코드는 다음과 같습니다: { "; // 주어진 트리의 프뤼퍼 코드를 출력
for(i = 0; i < ver-2; i++) {
minimum = 10000;
for(j = 0; j < edg; j++) {
if(DG[EDG[j][0]] == 1) {
if(minimum > EDG[j][0]) {
minimum = EDG[j][0];
p = j;
}
}
if(DG[EDG[j][1]] == 1) {
if(minimum > EDG[j][1]) {
minimum = EDG[j][1];
p = j;
}
}
}
DG[EDG[p][0]]--; // 선택된 정점의 차수를 0으로 만들어 제거
DG[EDG[p][1]]--; // 간선을 제거했으므로 반대편 정점의 차수도 감소
if(DG[EDG[p][0]] == 0)
cout<<EDG[p][1]<<" ";
else
cout<<EDG[p][0]<<" ";
}
cout<<"}";
return 0;
}
코드 동작 방식
배열 EDG는 간선 정보(두 정점의 쌍)를 저장하고, 배열 DG는 각 정점의 차수(degree)를 저장합니다. 매 반복마다 차수가 1인 정점, 즉 리프 중에서 번호가 가장 작은 것을 찾아 제거하며, 제거된 리프의 이웃 정점 번호를 출력하여 프뤼퍼 코드를 완성합니다.
실행 결과
정점의 개수를 입력하세요: 5
이 트리는 5개의 정점에 대해 4개의 간선을 가집니다.
트리에는 4개의 정점 쌍이 있습니다.
간선 1의 정점 쌍 값을 입력하세요:
V(1) 정점의 값을 입력하세요: 2
V(2) 정점의 값을 입력하세요: 3
간선 2의 정점 쌍 값을 입력하세요:
V(1) 정점의 값을 입력하세요: 5
V(2) 정점의 값을 입력하세요: 6
간선 3의 정점 쌍 값을 입력하세요:
V(1) 정점의 값을 입력하세요: 7
V(2) 정점의 값을 입력하세요: 8
간선 4의 정점 쌍 값을 입력하세요:
V(1) 정점의 값을 입력하세요: 9
V(2) 정점의 값을 입력하세요: 10
트리의 프뤼퍼 코드는 다음과 같습니다: { 4 8 4 }
이처럼 프뤼퍼 코드는 트리를 간결한 수열로 변환해 주기 때문에, 그래프 이론에서 트리의 개수를 세는 케일리 공식(Cayley's formula) 증명이나 트리의 인코딩·디코딩 문제 등 다양한 분야에서 활용됩니다.