The Prufer Code and the Floyd-Warshall Algorithm
(Page 1 of 4 )
Graphs help solve many computer-related problems. They can show us the simplest way to present something, so that it takes up as little memory as possible. In this article, the second part of a multi-part series that covers graphs in detail, you will learn a very clever way to code and decode a tree.
"The whole of science is nothing more than a refinement of everyday thinking," wrote Albert Einstein in Physics and Reality in the year 1936. Much truth lies in these words; you will see this when you read on and find out the ingenious ways to solve a few issues that at first may look too complicated.
Welcome back for anyone who read the first part of this article series about graphs; if you didn't, I invite you to read it. You will find it here on the site under the name of An Insight into Graphs. In essence, it tries to present what graphs are all about and how we can store them in memory.
Today I am going to present another ingenious way to code and decode a tree. This will also allow us to store that tree inside memory with the smallest amount of space used. Before we venture on, let me remind you of a few theoretical statements from my previous article that you will need to understand, so we can speak the same language.
"Graphs inside which there are no circles are called forests. The ones that are also connected are referred to simply as trees. Inside a tree, vertexes that have only one edge attached to them are leafs." Now that we know what a tree is, you should already realize that a tree always has n-1 edges, where n represents the number of vertexes present in the tree.
The Prüfer code is a proof to Cayley's formula, which states that if n is the number of vertexes inside a tree, there exist n^(n-2) different trees. The inventor of the algorithm was Heinz Prüfer and it was invented in 1918. The Prüfer code for each tree allocates a sequence of n-2 numbers, where the numbers are from the range {1, 2, ..., n}.
In this approach, every point of the tree is labeled with a number from one to n. The Prüfer code generated will be unique, and from this we can already deduce that Cayley's Formula is correct. As given, n-2 numbers from the {1, 2, ..., n} can be made n*n*...*n (n-2 times) according to a simple combinatorial point of view. Yet, how Prüfer code guarantees all this and how it is accomplished remain the subjects of the next page.
Next: How Prufer Works >>
More Code Examples Articles
More By Gabor Bernat
