C++ Programming Code Examples C++ > Sorting Searching Code Examples C++ Program to Create the Prufer Code for a Tree C++ Program to Create the Prufer Code for a Tree - This algorithm generates a prufer code for the given tree. - For a given tree of v vertexes, a prufer code is a unique sequence of v-2 vertex indexes. - The time complexity to generate this code is O(v*e). - This algorithm takes the input of the number of vertexes for the tree. - Then it takes the input if vertex pairs which have an edge between them. - To generate prufer code it removes the leaf vertex which has lowest index value. - It simultaneously adds the other vertex to the prufer code from which this leaf vertex was connected. - This process is done till two vertex remains in the tree. - Exit. #include<iostream> using namespace std; int main() { int i, j, v, e, min, x; // Take the input of the number of vertexes of the tree. cout<<"Enter the number of vertexes of the tree: "; cin>>v; // Calculate the number of edges in the tree as 'v-1'. e = v-1; int edge[e][2], deg[v+1] = {0}; cout<<"\nFor "<<v<<" vertexes this connected tree must have exactly "<<e<<" edges.\n"; // Enter the vertex pairs which have an edge between them. cout<<"\nEnter "<<e<<" pair of vertexes for the tree.\n"; for(i = 0; i < e; i++) { cout<<"Enter the vertex pair for edge "<<i+1<<":"; cout<<"\nV(1): "; cin>>edge[i][0]; cout<<"V(2): "; cin>>edge[i][1]; deg[edge[i][0]]++; deg[edge[i][1]]++; } // Print the prufer code of the given tree. cout<<"\nThe Prufer code for the given tree is: { "; for(i = 0; i < v-2; i++) { min = 10000; // Select the vertex which have lowest index and degree as 1. for(j = 0; j < e; j++) { if(deg[edge[j][0]] == 1) { if(min > edge[j][0]) { min = edge[j][0]; x = j; } } if(deg[edge[j][1]] == 1) { if(min > edge[j][1]) { min = edge[j][1]; x = j; } } } // Remove the selected vertex by decreasing its degree to 0. deg[edge[x][0]]--; // Decrement the degree of other vertex, since we have removed the edge. deg[edge[x][1]]--; // Print the vertex from which leaf vertex is removed. if(deg[edge[x][0]] == 0) cout<<edge[x][1]<<" "; else cout<<edge[x][0]<<" "; } cout<<"}"; return 0; }