Mã Prufer xác định duy nhất một cây được cho bởi người dùng dưới dạng biểu diễn đồ thị với nhãn từ 1 đến p. Cây này gồm p nhãn nút (giá trị p do người dùng cung cấp). Nó có chuỗi p - 2 giá trị.
Thuật toán
Bắt đầu
Khai báo i, j, ver, edg, minimum, p kiểu nguyên.
In "Enter the number of vertexes: ".
Nhập giá trị ver.
Khởi tạo edg = ver - 1.
Khai báo EDG[edg][2], DG[ver+1] kiểu nguyên.
Khởi tạo DG[ver+1] = {0}.
In "This tree has (giá trị edg) edges for (giá trị ver) vertexes".
In "There are (giá trị edg) pairs of vertexes in the tree".
for(i = 0; i < edg; i++)
In "Enter the value of vertex pair for edge ".
In "Enter the value of V(1) vertex: ".
Nhập giá trị EDG[i][0].
In "Enter the value of V(2) vertex: ".
Nhập giá trị EDG[i][1].
DG[EDG[i][0]]++.
DG[EDG[i][1]]++.
In "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) thì
nếu(minimum > EDG[j][0]) thì
minimum = EDG[j][0].
p = j.
nếu(DG[EDG[j][1]] == 1) thì
nếu(minimum > EDG[j][1]) thì
minimum = EDG[j][1].
p = j.
DG[EDG[p][0]]--.
DG[EDG[p][1]]--.
nếu(DG[EDG[p][0]] == 0) thì
In giá trị EDG[p][1].
ngược lại
In giá trị EDG[p][0].
In "}".
Kết thúc.
Ví dụ
#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 tree.\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: { ";
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]]--; // Loại bỏ đỉnh đã chọn bằng cách giảm bậc về 0.
DG[EDG[p][1]]--; // Giảm bậc của đỉnh kia, vì đã loại bỏ cạnh.
if(DG[EDG[p][0]] == 0)
cout << EDG[p][1] << " ";
else
cout << EDG[p][0] << " ";
}
cout << "}";
return 0;
}
Kết quả
Enter the number of vertexes: 5
This tree has 4 edges for 5 vertexes.
There are 4 pairs of vertexes in the tree.
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 }