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;
}