Java Program to Create the Prufer Code for a Tree

This is a java program to create Prufer code for a tree. In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n – 2, and can be generated by a simple iterative algorithm.

Here is the source code of the Java Program to Create the Prufer Code for a Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.combinatorial;
  3.  
  4. import java.util.ArrayList;
  5. import java.util.Arrays;
  6. import java.util.Collections;
  7. import java.util.LinkedHashSet;
  8. import java.util.List;
  9. import java.util.Random;
  10. import java.util.Scanner;
  11. import java.util.Set;
  12.  
  13. public class PruferCode
  14. {
  15.     public static List<Integer>[] getRandomTree2(int n, Random rnd)
  16.     {
  17.         @SuppressWarnings("unchecked")
  18.         List<Integer>[] t = new List[n];
  19.         for (int i = 0; i < n; i++)
  20.             t[i] = new ArrayList<>();
  21.         int[] p = new int[n];
  22.         for (int i = 0, j; i < n; j = rnd.nextInt(i + 1), p[i] = p[j], p[j] = i, i++)
  23.             ; // random permutation
  24.         for (int i = 1; i < n; i++)
  25.         {
  26.             int parent = p[rnd.nextInt(i)];
  27.             t[parent].add(p[i]);
  28.             t[p[i]].add(parent);
  29.         }
  30.         return t;
  31.     }
  32.  
  33.     public static List<Integer>[] pruferCode2Tree(int[] pruferCode)
  34.     {
  35.         int n = pruferCode.length + 2;
  36.         @SuppressWarnings("unchecked")
  37.         List<Integer>[] tree = new List[n];
  38.         for (int i = 0; i < n; i++)
  39.             tree[i] = new ArrayList<>();
  40.         int[] degree = new int[n];
  41.         Arrays.fill(degree, 1);
  42.         for (int v : pruferCode)
  43.             ++degree[v];
  44.         int ptr = 0;
  45.         while (degree[ptr] != 1)
  46.             ++ptr;
  47.         int leaf = ptr;
  48.         for (int v : pruferCode)
  49.         {
  50.             tree[leaf].add(v);
  51.             tree[v].add(leaf);
  52.             --degree[leaf];
  53.             --degree[v];
  54.             if (degree[v] == 1 && v < ptr)
  55.             {
  56.                 leaf = v;
  57.             }
  58.             else
  59.             {
  60.                 for (++ptr; ptr < n && degree[ptr] != 1; ++ptr)
  61.                     ;
  62.                 leaf = ptr;
  63.             }
  64.         }
  65.         for (int v = 0; v < n - 1; v++)
  66.         {
  67.             if (degree[v] == 1)
  68.             {
  69.                 tree[v].add(n - 1);
  70.                 tree[n - 1].add(v);
  71.             }
  72.         }
  73.         return tree;
  74.     }
  75.  
  76.     public static int[] tree2PruferCode(List<Integer>[] tree)
  77.     {
  78.         int n = tree.length;
  79.         int[] parent = new int[n];
  80.         parent[n - 1] = -1;
  81.         pruferDfs(tree, parent, n - 1);
  82.         int[] degree = new int[n];
  83.         int ptr = -1;
  84.         for (int i = 0; i < n; ++i)
  85.         {
  86.             degree[i] = tree[i].size();
  87.             if (degree[i] == 1 && ptr == -1)
  88.                 ptr = i;
  89.         }
  90.         int[] res = new int[n - 2];
  91.         int leaf = ptr;
  92.         for (int i = 0; i < n - 2; ++i)
  93.         {
  94.             int next = parent[leaf];
  95.             res[i] = next;
  96.             --degree[next];
  97.             if (degree[next] == 1 && next < ptr)
  98.             {
  99.                 leaf = next;
  100.             }
  101.             else
  102.             {
  103.                 ++ptr;
  104.                 while (ptr < n && degree[ptr] != 1)
  105.                     ++ptr;
  106.                 leaf = ptr;
  107.             }
  108.         }
  109.         return res;
  110.     }
  111.  
  112.     static void pruferDfs(List<Integer>[] tree, int[] parent, int v)
  113.     {
  114.         for (int i = 0; i < tree[v].size(); ++i)
  115.         {
  116.             int to = tree[v].get(i);
  117.             if (to != parent[v])
  118.             {
  119.                 parent[to] = v;
  120.                 pruferDfs(tree, parent, to);
  121.             }
  122.         }
  123.     }
  124.  
  125.     // precondition: n >= 2
  126.     public static List<Integer>[] getRandomTree(int V, Random rnd)
  127.     {
  128.         int[] a = new int[V - 2];
  129.         for (int i = 0; i < a.length; i++)
  130.         {
  131.             a[i] = rnd.nextInt(V);
  132.         }
  133.         return pruferCode2Tree(a);
  134.     }
  135.  
  136.     // precondition: V >= 2, V-1 <= E <= V*(V-1)/2
  137.     public static List<Integer>[] getRandomUndirectedConnectedGraph(int V,
  138.             int E, Random rnd)
  139.     {
  140.         List<Integer>[] g = getRandomTree(V, rnd);
  141.         Set<Long> edgeSet = new LinkedHashSet<>();
  142.         for (int i = 0; i < V; i++)
  143.         {
  144.             for (int j = i + 1; j < V; j++)
  145.             {
  146.                 edgeSet.add(((long) i << 32) + j);
  147.             }
  148.         }
  149.         for (int i = 0; i < V; i++)
  150.         {
  151.             for (int j : g[i])
  152.             {
  153.                 edgeSet.remove(((long) i << 32) + j);
  154.             }
  155.         }
  156.         List<Long> edges = new ArrayList<>(edgeSet);
  157.         for (int x : getRandomArrangement(edges.size(), E - (V - 1), rnd))
  158.         {
  159.             long e = edges.get(x);
  160.             int u = (int) (e >>> 32);
  161.             int v = (int) e;
  162.             g[u].add(v);
  163.             g[v].add(u);
  164.         }
  165.         for (int i = 0; i < V; i++)
  166.             Collections.sort(g[i]);
  167.         return g;
  168.     }
  169.  
  170.     // precondition: V >= 2, V-1 <= E <= V*(V-1)/2
  171.     public static List<Integer>[] getRandomUndirectedConnectedGraph2(int V,
  172.             int E, Random rnd)
  173.     {
  174.         List<Integer>[] g = getRandomTree(V, rnd);
  175.         Set<Long> edgeSet = new LinkedHashSet<>();
  176.         for (int i = 0; i < V; i++)
  177.         {
  178.             for (int j : g[i])
  179.             {
  180.                 edgeSet.add(((long) i << 32) + j);
  181.             }
  182.         }
  183.         for (int i = 0; i < E - (V - 1); i++)
  184.         {
  185.             int u;
  186.             int v;
  187.             long edge;
  188.             while (true)
  189.             {
  190.                 u = rnd.nextInt(V);
  191.                 v = rnd.nextInt(V);
  192.                 edge = ((long) u << 32) + v;
  193.                 if (u < v && !edgeSet.contains(edge))
  194.                     break;
  195.             }
  196.             edgeSet.add(edge);
  197.             g[u].add(v);
  198.             g[v].add(u);
  199.         }
  200.         for (int i = 0; i < V; i++)
  201.             Collections.sort(g[i]);
  202.         return g;
  203.     }
  204.  
  205.     static int[] getRandomArrangement(int n, int m, Random rnd)
  206.     {
  207.         int[] res = new int[n];
  208.         for (int i = 0; i < n; i++)
  209.         {
  210.             res[i] = i;
  211.         }
  212.         for (int i = 0; i < m; i++)
  213.         {
  214.             int j = n - 1 - rnd.nextInt(n - i);
  215.             int t = res[i];
  216.             res[i] = res[j];
  217.             res[j] = t;
  218.         }
  219.         return Arrays.copyOf(res, m);
  220.     }
  221.  
  222.     static void checkGraph(int V, int E, Random rnd)
  223.     {
  224.         List<Integer>[] g = getRandomUndirectedConnectedGraph(V, E, rnd);
  225.         int n = g.length;
  226.         int[][] a = new int[n][n];
  227.         int edges = 0;
  228.         for (int i = 0; i < n; i++)
  229.         {
  230.             for (int j : g[i])
  231.             {
  232.                 ++a[i][j];
  233.                 ++edges;
  234.             }
  235.         }
  236.         if (edges != 2 * E)
  237.         {
  238.             throw new RuntimeException();
  239.         }
  240.         for (int i = 0; i < n; i++)
  241.         {
  242.             if (a[i][i] != 0)
  243.             {
  244.                 throw new RuntimeException();
  245.             }
  246.             for (int j = 0; j < n; j++)
  247.             {
  248.                 if (a[i][j] != a[j][i] || a[i][j] != 0 && a[i][j] != 1)
  249.                 {
  250.                     throw new RuntimeException();
  251.                 }
  252.             }
  253.         }
  254.     }
  255.  
  256.     public static void main(String[] args)
  257.     {
  258.         Scanner sc = new Scanner(System.in);
  259.         System.out.println("Enter the length of code: ");
  260.         int n = sc.nextInt();
  261.         int[] code = new int[n];
  262.         for (int i = 0; i < n; i++)
  263.         {
  264.             code[i] = sc.nextInt();
  265.         }
  266.         List<Integer>[] tree = pruferCode2Tree(code);
  267.         Random rnd = new Random(1);
  268.         for (int step = 0; step < 1000; step++)
  269.         {
  270.             int V = rnd.nextInt(50) + 2;
  271.             checkGraph(V, V - 1, rnd);
  272.             checkGraph(V, V * (V - 1) / 2, rnd);
  273.             checkGraph(V, rnd.nextInt(V * (V - 1) / 2 - (V - 1) + 1) + V - 1,
  274.                     rnd);
  275.         }
  276.         System.out.println("Prufer code to tree conversion: "
  277.                 + Arrays.toString(tree));
  278.         System.out.println("Tree to prufer code conversion: "
  279.                 + Arrays.toString(tree2PruferCode(tree)));
  280.         sc.close();
  281.     }
  282. }

Output:

$ javac PruferCode.java
$ java PruferCode
 
Enter the length of code: 
4
2 3 4 3 
Prufer code to tree conversion: [[2], [3], [0, 4], [1, 4, 5], [2, 3], [3]]
Tree to prufer code conversion: [2, 3, 4, 3]
 
Enter the length of code: 
3
2 4 3 
Prufer code to tree conversion: [[2], [4], [0, 3], [2, 4], [1, 3]]
Tree to prufer code conversion: [2, 4, 3]
 
Enter the length of code: 
5
3 4 5 1 6
Prufer code to tree conversion: [[3], [4, 6], [4], [0, 5], [2, 1], [3, 6], [1, 5]]
Tree to prufer code conversion: [3, 4, 5, 1, 6]

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.