# Prüfer codes and labeled trees in C Arthur Cayley first proved that there are $$n^{n-2}$$ labeled trees on $$n$$ vertices, and in another proof of the same theorem, Heinz Prüfer showed a bijection between trees on $$n$$ vertices and $$(n-2)$$-tuples of integers from 1 to $$n – 2$$, called Prüfer codes. The proof provides an algorithm that allows us to construct an arbitrary labeled tree from its code.

The algorithm proceeds as follows:

1. Initialise an array of node degrees for the nodes, which are numbered from 1 to $$n + 2$$
2. For each occurrence of a node number in the code, increment its degree
3. Add 1 to all degrees
4. For each occurrence of a node number in the code:
1. Find the lowest-numbered node with degree 1
2. Create an edge between that node and the node in the code
3. Decrement the degrees of both nodes by 1
5. There are now 2 nodes left with degree 1, so join them with an edge to complete the tree

Below is an implementation of the algorithm in C. The function prufer_tree() takes a code in the form of an array of unsigned integers and its length, and returns the tree as an array of edges.

#include <stdlib.h>

typedef struct {
unsigned int first;
unsigned int second;
} edge;

edge *prufer_tree(const unsigned int *code, size_t len)
{
unsigned int i, j, e = 0;
const unsigned int n = len + 2; /* Nodes */
edge *tree = malloc((n - 1) * sizeof(edge));
unsigned int *degrees = calloc(n + 1, sizeof(unsigned int)); /* 1-based */
if (tree == NULL || degrees == NULL) {
free(tree);
free(degrees);
return NULL;
}
/* Set the degrees from the occurrences in the code */
for (i = 0; i < len; i++) {
degrees[ code[i]]++;
}
/* Add 1 to them all */
for (i = 1; i <= n; i++) {
degrees[i]++;
}
/* Add edges to nodes in the code */
for (i = 0; i < len; i++) {
/* Find the lowest-numbered node with degree 1 */
for (j = 1; degrees[j] != 1; j++);
tree[e].first = j;
tree[e].second = code[i];
degrees[j]--;
degrees[ code[i]]--;
e++;
}
/* Find the last 2 degree-1 nodes */
for (i = 1; degrees[i] != 1; i++);
for (j = i + 1; degrees[j] != 1; j++);
/* Add the last edge */
tree[e].first = i;
tree[e].second = j;
free(degrees);

return tree;
}


Here is an example program that constructs the tree in the image at the top:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
unsigned int code[] = {1, 1, 1, 1, 6, 5};
const size_t len = sizeof(code) / sizeof(unsigned int);
const unsigned int n = len + 1; /* Edges */
edge *tree = prufer_tree(code, len);
unsigned int e;
for (e = 0; e < n; e++) {
printf("(%u, %u)\n", tree[e].first, tree[e].second);
}
free(tree);
return 0;
}


The output:

(2, 1)
(3, 1)
(4, 1)
(7, 1)
(1, 6)
(6, 5)
(5, 8)