The Prufer Code and the Floyd-Warshall Algorithm - How Prufer Works
(Page 2 of 4 )
This algorithm works in both directions. We can code a tree into a sequence of n-2 numbers and we can decode it back. The representation we are going to use is of the edge list. Therefore the input file will contain the number of vertexes used, followed by n-1 lines with a pair of numbers, each representing an edge.
The algorithm is simple; it contains n-1 steps. We get the smallest indexed leaf from the tree and add it to the sequence. Delete the vertex from the tree (and with it the edge also) and repeat the step n-2 times.
In the end, we should add the n to the sequence. The n-2 sequence will represent the Prüfer code, as the last element (the n) is always at the end, and if we know the number of vertexes in the tree, we do not need it.
This n-1 th element will take always take up the n; for proof, think that we always cut off of the tree the vertex that has the smallest index. So think about what would happen if the nth element remains there until the end of our algorithm (n-1th step), if we will still have to choose the smaller one, and with it, the n remains there as a vertex with no additional edges to the others.
When we code the algorithm inside a language, we need to determine which vertexes are leaves, so we can choose the smallest one from them. I have opted to count the degree of all points and search within this list for the smallest vertex that has a degree equal to one (as this is, by definition, a leaf).
Deleting the vertex and the edge related to it is a job to set to an invalid vertex pair in the edge list, and to decrease the degree of the item at the other end. The deletion of the vertex itself that we just cut off will be achieved by setting the degree of that point to zero. Here it is the code snippet:
Count the degree at read time.
++degre[edgeList[i].from];
++degre[edgeList[i].to];
for( j= 0; j < n-2; ++j)
{
// find the vertex with the smallest grad
for( k=0; k < n;k++)
{
if(degre[k] == 1)
{
l = k;
break;
}
}
// ok find the pair/edge of this
for( k =0; k < n-1; ++k)
{
if( edgeList[k].from == l || edgeList[k].to == l)
{
// cut it off
// delete the edge
// decrease the degree of the vertex
if(edgeList[k].from ==l)
{
--degre[prufer[j] = edgeList[k].to];
}
else
{
--degre[prufer[j] = edgeList[k].from];
}
edgeList[k].from = -1;
edgeList[k].to = -1;
break;
}
}
degre[l] = 0; // no more additional edge on this vertex
}
prufer[n-2] = n-1; //set the last item
Okay, the first thing I need to clarify is that I counted the vertexes from zero to n-1, so decrease by one from everything that I said in the upper description of the algorithm. It is just another way of representing it; everything else remains the same, and I think it is straightforward enough for you to understand.
Next: Decoding Prufer >>
More Code Examples Articles
More By Gabor Bernat
