প্রুফার কোড (Prufer code) একটি ট্রিকে অনন্যভাবে চিহ্নিত করে যা ব্যবহারকারী গ্রাফ রিপ্রেজেন্টেশন হিসেবে ১ থেকে p পর্যন্ত লেবেল দিয়ে দেয়। এই ট্রিতে p (ব্যবহারকারী দেওয়া মান) সংখ্যক নোড লেবেল রয়েছে। এর সিকোয়েন্স p-2 মান ধারণ করে।
অ্যালগরিদম
শুরু
i, j, ver, edg, minimum, p ইন্টিজার টাইপে ডিক্লেয়ার করুন
"Enter the number of vertexes: " প্রিন্ট করুন
ver-এর মান ইনপুট নিন
edg = ver-1 ইনিশিয়ালাইজ করুন
EDG[edg][2], DG[ver+1] ইন্টিজার টাইপে ডিক্লেয়ার করুন
DG[ver+1] = {0} ইনিশিয়ালাইজ করুন
"This tree has (edg) edges for (ver) vertexes" প্রিন্ট করুন
"There are (edg) pairs of vertexes in the tree" প্রিন্ট করুন
for(i = 0; i < edg; i++)
"Enter the value of vertex pair for edge " প্রিন্ট করুন
"Enter the value of V(1) vertex: " প্রিন্ট করুন
EDG[i][0] ইনপুট নিন
"Enter the value of V(2) vertex: " প্রিন্ট করুন
EDG[i][1] ইনপুট নিন
DG[EDG[i][0]]++
DG[EDG[i][1]]++
"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) হয়, তবে
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] প্রিন্ট করুন
অন্যথায়
EDG[p][0] প্রিন্ট করুন
"}" প্রিন্ট করুন
শেষ
উদাহরণ কোড
#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]]--; // নির্বাচিত ভার্টেক্স মুছে ফেলা
DG[EDG[p][1]]--; // 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 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 }
