Mathematica, 34 bytes

<<Combinatorica`
LabeledTreeToCode

Somebody had to do it....

After loading the Combinatorica package, the function LabeledTreeToCode expects a tree input as an undirected graph with explicitly listed edges and vertices; for example, the input in the second test case could be Graph[{{{1, 4}}, {{4, 3}}, {{4, 2}}, {{2, 5}}, {{2, 6}}, {{6, 7}}, {{5, 8}}}, {1, 2, 3, 4, 5, 6, 7, 8}].

Python 3, 136 131 127 bytes

def f(t):
 while len(t)>2:
  m=min(x for x in t if len(t[x])<2);yield t[m][0];del t[m]
  for x in t:m in t[x]and t[x].remove(m)

Takes input as an adjacency matrix. First example:

>>> [*f({1:[2],2:[1,3,4,5],3:[2],4:[2,6],5:[2],6:[4]})]
[2, 2, 2, 4]

Jelly, 31 bytes

FĠLÞḢḢ
0ịµÇHĊṙ@µÇCịṪ,
WÇÐĿḢ€ṖṖḊ

A monadic link which takes a list of pairs of nodes (defining the edges) in any order (and each in any orientation) and returns the Prüfer Code as a list.

Try it online!

FĠLÞḢḢ - Link 1, find leaf location: list of edges (node pairs)
F      - flatten
 Ġ     - group indices by value (sorted smallest to largest by value)
  LÞ   - sort by length (stable sort, so equal lengths remain in prior order)
    ḢḢ - head head (get the first of the first group. If there are leaves this yields
       -   the index of the smallest leaf in the flattened version of the list of edges)

0ịµÇHĊṙ@µÇCịṪ, - Link 2, separate smallest leaf: list with last item a list of edges
0ị             - item at index zero - the list of edges
  µ            - monadic chain separation (call that g)
   Ç           - call last link (1) as a monad (index of smallest leaf if flattened)
    H          - halve
     Ċ         - ceiling (round up)
      ṙ@       - rotate g left by that amount (places the edge to remove at the right)
        µ      - monadic chain separation (call that h)
         Ç     - call last link (1) as a monad (again)
          C    - complement (1-x)
            Ṫ  - tail h (removes and yields the edge)
           ị   - index into, 1-based and modular (gets the other node of the edge)
             , - pair with the modified h
               -    (i.e. [otherNode, restOfTree], ready for the next iteration)

WÇÐĿḢ€ṖṖḊ - Main link: list of edges (node pairs)
W         - wrap in a list (this is so the first iteration works)
  ÐĿ      - loop and collect intermediate results until no more change:
 Ç        -   call last link (2) as a monad
    Ḣ€    - head €ach (get the otherNodes, although the original tree is also collected)
      ṖṖ  - discard the two last results (they are excess to requirements)
        Ḋ - discard the first result (the tree, leaving just the Prüfer Code)

Python, 689 bytes

The following algorithm can be used to generate the Prüfer code (of length n-2) given a tree on n vertices - there is a one-to-one mapping between the Prüfer sequence and a spanning tree of Kn (complete graph with n vertices).

The following python code implements the above algorithm:

def get_degree_sequence(tree):
    ds, nbrs = {}, {}
    for node in tree:
        for nbr in tree[node]:
            ds[node] = ds.get(node, 0) + 1
            ds[nbr] = ds.get(nbr, 0) + 1
            nbrs[node] = nbrs.get(node, []) + [nbr]
            nbrs[nbr] = nbrs.get(nbr, []) + [node]
    return ds, nbrs

def get_prufer_seq(tree):
    ds, nbrs = get_degree_sequence(tree)
    seq = []
    while len(ds) > 2:
        min_leaf = min(list(filter(lambda x: ds[x] == 1, ds)))
        parent = nbrs[min_leaf][0]
        seq.append(parent)
        ds[parent] -= 1
        del ds[min_leaf]
        del nbrs[min_leaf]
        nbrs[parent].remove(min_leaf)
    return seq

Invoke the function with the input tree to get the Prüfer code corresponding to the tree, as shown below:

T = {1:[2, 4, 5], 2:[7], 7:[3], 3:[6]}
print(get_prufer_seq(T))
# [1, 1, 2, 7, 3]

The following animation shows the steps in Prüfer code generation:

05AB1E, 29 bytes

[Dg#ÐD˜{γé¬`U\X.å©Ï`XK`ˆ®_Ï]¯

Try it online!

Explanation

[Dg#                           # loop until only 1 link (2 vertices) remain
    ÐD                         # quadruple the current list of links
      ˜{                       # flatten and sort values
        γé                     # group by value and order by length of runs
          ¬`U                  # store the smallest leaf in X
             \X                # discard the sorted list and push X
               .å©             # check each link in the list if X is in that link
                  Ï`           # keep only that link
                    XK`ˆ       # add the value that isn't X to the global list
                        ®_Ï    # remove the handled link from the list of links
                           ]   # end loop
                            ¯  # output global list

Clojure, 111 bytes

#(loop[r[]G %](if-let[i(first(sort(remove(set(vals G))(keys G))))](recur(conj r(G i))(dissoc G i))(butlast r)))

Requires the input to be a hash-map, having "leaf-like" labels as keys and "root-like" labels as values. For example:

{1 2, 3 2, 5 2, 4 2, 6 4}
{1 4, 3 4, 4 2, 8 5, 5 2, 7 6, 6 2}

On each iteration it finds the smallest key which is not referenced by any other node, adds it to the result r and removes the node from the graph definition G. if-let goes to else case when G is empty, as first returns nil. Also the last element has to be dropped.

Python 2, 91 bytes

d=input()
while len(d)>2:m=min(d,key=lambda k:len(d[k]));n,=d[m];del d[m];d[n]-={m};print n

Try it online!

Based on L3viathan's solution. Takes a dictionary of sets representing adjacency lists.

Sign up or log in

Post as a guest