Prufer 코드는 1에서 p까지 레이블이 있는 그래프 표현으로 사용자가 제공한 트리를 고유하게 식별합니다. 이 트리는 노드의 p(값은 사용자가 제공함) 레이블로 구성됩니다. p – 2 값의 시퀀스를 가집니다.
알고리즘
Begin
Declare i, j, ver, edg, minimum, p to the integer datatype.
Print “Enter the number of vertexes: ”.
Enter the value of ver.
Initialize edg = ver-1.
Declare EDG[edg][2], DG[ver+1] to the integer datatype.
Initialize DG[ver+1] = {0}.
Print “This tree has (value of edg) edges for (value of ver) vertexes”.
Print “There are (value of edg) pairs of vertexes in the tree”.
for(i = 0; i < edg; i++)
Print "Enter the value of vertex pair for edge ".
Print "Enter the value of V(1) vertex: ".
Enter the value of EDG[i][0].
Print "Enter the value of V(2) vertex: ".
Enter the value of EDG[i][1].
DG[EDG[i][0]]++.
DG[EDG[i][1]]++.
Print "The Prufer code for the tree is: { ".
for(i = 0; i < ver-2; i++)
minimum = 10000
for(j = 0; j < edg; j++)
if(DG[EDG[j][0]] == 1) then
if(minimum > EDG[j][0]) then
minimum = EDG[j][0].
p = j.
if(DG[EDG[j][1]] == 1) then
if(minimum > EDG[j][1]) then
minimum = EDG[j][1].
p = j.
DG[EDG[p][0]]--.
DG[EDG[p][1]]--.
if(DG[EDG[p][0]] == 0) then
Print the value of EDG[p][1].
else
Print the value of EDG[p][0].
Print "}".
End. 예시
#include<iostream>
using namespace std;
int main() {
int i, j, ver, edg, minimum, p;
cout<<"Enter the number of vertexes: ";
cin>>ver;
cout<<endl;
edg = ver-1;
int EDG[edg][2], DG[ver+1] = {0};
cout<<"This tree has "<<edg<<" edges for "<<ver<<"vertexes.\n";
cout<<"There are "<<edg<<" pairs of vertexes in the three.\n";
for(i = 0; i < edg; i++) {
cout<<"Enter the value of vertex pair for edge "<<i+1<<":\n";
cout<<"Enter the value of V(1) vertex: ";
cin>>EDG[i][0];
cout<<"Enter the value of V(2) vertex: ";
cin>>EDG[i][1];
DG[EDG[i][0]]++;
DG[EDG[i][1]]++;
}
cout<<"\nThe Prufer code for the tree is: { "; // Print the prufer code of the given tree.
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]]--; // Remove the selected vertex by decreasing its degree to 0.
DG[EDG[p][1]]--; // Decrement the degree of other vertex, since we have removed the EDG.
if(DG[EDG[p][0]] == 0)
cout<<EDG[p][1]<<" ";
else
cout<<EDG[p][0]<<" ";
}
cout<<"}";
return 0;
} 출력
Enter the number of vertexes: 5
This tree has 4 edges for 5vertexes.
There are 4 pairs of vertexes in the three.
Enter the value of vertex pair for edge 1:
Enter the value of V(1) vertex: 2
Enter the value of V(2) vertex: 3
Enter the value of vertex pair for edge 2:
Enter the value of V(1) vertex: 5
Enter the value of V(2) vertex: 6
Enter the value of vertex pair for edge 3:
Enter the value of V(1) vertex: 7
Enter the value of V(2) vertex: 8
Enter the value of vertex pair for edge 4:
Enter the value of V(1) vertex: 9
Enter the value of V(2) vertex: 10
The Prufer code for the tree is: { 4 8 4 }