Skip to main content
`Ctrl`+`K`

# from_prufer_sequence

from_prufer_sequence(sequence)

  Returns the tree corresponding to the given Prüfer sequence.

  A Prüfer sequence is a list of n - 2 numbers between 0 and n - 1, inclusive. The tree corresponding to a given Prüfer sequence can be recovered by repeatedly joining a node in the sequence with a node with the smallest potential degree according to the sequence.

  Parameters:
    sequence list

      A Prüfer sequence, which is a list of n - 2 integers between zero and n - 1, inclusive.

  Returns:
    NetworkX graph

      The tree corresponding to the given Prüfer sequence.

  Raises:
    NetworkXError

      If the Prüfer sequence is not valid.

  See also

  `from_nested_tuple`
  `to_prufer_sequence`

  Notes

  There is a bijection from labeled trees to Prüfer sequences. This function is the inverse of the `from_prufer_sequence()` function.

  Sometimes Prüfer sequences use nodes labeled from 1 to n instead of from 0 to n - 1. This function requires nodes to be labeled in the latter form. You can use `networkx.relabel_nodes()` to relabel the nodes of your tree to the appropriate format.

  This implementation is from [1] and has a running time of \(O(n)\).

  References

  [1]

  Wang, Xiaodong, Lei Wang, and Yingjie Wu. “An optimal algorithm for Prufer codes.” Journal of Software Engineering and Applications 2.02 (2009): 111. <https://doi.org/10.4236/jsea.2009.22016>

  Examples

  There is a bijection between Prüfer sequences and labeled trees, so this function is the inverse of the `to_prufer_sequence()` function:

      >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
      >>> tree = nx.Graph(edges)
      >>> sequence = nx.to_prufer_sequence(tree)
      >>> sequence
      [3, 3, 3, 4]
      >>> tree2 = nx.from_prufer_sequence(sequence)
      >>> list(tree2.edges()) == edges
      True