The Prufer Code and the Floyd-Warshall Algorithm - Decoding Prufer
(Page 3 of 4 )
If we code something and fail to decode it, that probably would be meaningless, so here we will go in the other direction. First, we have to add the n to the last position. As I said before, the last item is there by default, so it is not added to the sequence (even if we do not know the number of vertexes, this will be the length of the sequence plus two).
The algorithm will try, and it will succeed, to determine at every step another edge of the tree. Therefore, this also will have n-1 steps. When we add the n to the sequence, the length of the sequence will turn into n-1.
The algorithm is simple. When we wrote down at code time the "i"th item that was not cut before, it will not be cut in the future either; it was the smallest indexed vertex at that time that still was related to the tree.
In conclusion, we need to find the smallest index in the sequence containing the points that were cut down, and the one present in the Prüfer code. Look at the image below in order to comprehend it better.
The upper row is the Prüfer code, and for the next item we will always choose the smallest not-existing index from the grayed numbers (those that will be added later and those that were already added to the code). In the end, the two- dimensional array will hold one edge in each column. Here is everything coded in C:
for ( j =0; j < n-1; ++j)
{
memset(present,0, n*sizeof(int) ) ; // reset the count // array - here present[i] will be zero if it's grayed
for( k = j ; k < n-2; ++k)
present[prufer[k]] = 1; // the items in the code
for( k = 0; k < j; k++) // points already added
present[temp[k]] = 1;
for( k =0 ; k < n; ++k)
if(!present[k]) // first not present
{
// add to our edge list
edgeList[j].from = prufer[j] ;
edgeList[j].to = k;
temp[j] = k; // add it as already deduced vertex
break; // end this loop...
}
}
With one input of:
8
1 2
1 6
1 7
0 1
0 3
0 4
4 5
The result:
Edges:
1 - 2
1 - 6
1 - 7
0 - 1
0 - 3
0 - 4
4 - 5
$$$$$$$$$$ 0 1 2 3 4 5 6 7
A Degrees: 3 4 1 1 2 1 1 1
The prufer code:
1 0 4 0 1 1 7
The prufer code transformed back: edges
1 - 2
0 - 3
4 - 5
0 - 4
1 - 0
1 - 6
7 - 1
Press any key to continue . . .
Here is the code if you want to have a look at it; it's a simple C file, so just compile it. Assure that you have a valid input within the In.txt file and it should work perfectly:
Download Source
Next: Floyd-Warshall Algorithm >>
More Code Examples Articles
More By Gabor Bernat
