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.
package com.sanfoundry.combinatorial; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.LinkedHashSet; import java.util.List; import java.util.Random; import java.util.Scanner; import java.util.Set; public class PruferCode { public static List<Integer>[] getRandomTree2(int n, Random rnd) { @SuppressWarnings("unchecked") List<Integer>[] t = new List[n]; for (int i = 0; i < n; i++) t[i] = new ArrayList<>(); int[] p = new int[n]; for (int i = 0, j; i < n; j = rnd.nextInt(i + 1), p[i] = p[j], p[j] = i, i++) ; // random permutation for (int i = 1; i < n; i++) { int parent = p[rnd.nextInt(i)]; t[parent].add(p[i]); t[p[i]].add(parent); } return t; } public static List<Integer>[] pruferCode2Tree(int[] pruferCode) { int n = pruferCode.length + 2; @SuppressWarnings("unchecked") List<Integer>[] tree = new List[n]; for (int i = 0; i < n; i++) tree[i] = new ArrayList<>(); int[] degree = new int[n]; Arrays.fill(degree, 1); for (int v : pruferCode) ++degree[v]; int ptr = 0; while (degree[ptr] != 1) ++ptr; int leaf = ptr; for (int v : pruferCode) { tree[leaf].add(v); tree[v].add(leaf); --degree[leaf]; --degree[v]; if (degree[v] == 1 && v < ptr) { leaf = v; } else { for (++ptr; ptr < n && degree[ptr] != 1; ++ptr) ; leaf = ptr; } } for (int v = 0; v < n - 1; v++) { if (degree[v] == 1) { tree[v].add(n - 1); tree[n - 1].add(v); } } return tree; } public static int[] tree2PruferCode(List<Integer>[] tree) { int n = tree.length; int[] parent = new int[n]; parent[n - 1] = -1; pruferDfs(tree, parent, n - 1); int[] degree = new int[n]; int ptr = -1; for (int i = 0; i < n; ++i) { degree[i] = tree[i].size(); if (degree[i] == 1 && ptr == -1) ptr = i; } int[] res = new int[n - 2]; int leaf = ptr; for (int i = 0; i < n - 2; ++i) { int next = parent[leaf]; res[i] = next; --degree[next]; if (degree[next] == 1 && next < ptr) { leaf = next; } else { ++ptr; while (ptr < n && degree[ptr] != 1) ++ptr; leaf = ptr; } } return res; } static void pruferDfs(List<Integer>[] tree, int[] parent, int v) { for (int i = 0; i < tree[v].size(); ++i) { int to = tree[v].get(i); if (to != parent[v]) { parent[to] = v; pruferDfs(tree, parent, to); } } } // precondition: n >= 2 public static List<Integer>[] getRandomTree(int V, Random rnd) { int[] a = new int[V - 2]; for (int i = 0; i < a.length; i++) { a[i] = rnd.nextInt(V); } return pruferCode2Tree(a); } // precondition: V >= 2, V-1 <= E <= V*(V-1)/2 public static List<Integer>[] getRandomUndirectedConnectedGraph(int V, int E, Random rnd) { List<Integer>[] g = getRandomTree(V, rnd); Set<Long> edgeSet = new LinkedHashSet<>(); for (int i = 0; i < V; i++) { for (int j = i + 1; j < V; j++) { edgeSet.add(((long) i << 32) + j); } } for (int i = 0; i < V; i++) { for (int j : g[i]) { edgeSet.remove(((long) i << 32) + j); } } List<Long> edges = new ArrayList<>(edgeSet); for (int x : getRandomArrangement(edges.size(), E - (V - 1), rnd)) { long e = edges.get(x); int u = (int) (e >>> 32); int v = (int) e; g[u].add(v); g[v].add(u); } for (int i = 0; i < V; i++) Collections.sort(g[i]); return g; } // precondition: V >= 2, V-1 <= E <= V*(V-1)/2 public static List<Integer>[] getRandomUndirectedConnectedGraph2(int V, int E, Random rnd) { List<Integer>[] g = getRandomTree(V, rnd); Set<Long> edgeSet = new LinkedHashSet<>(); for (int i = 0; i < V; i++) { for (int j : g[i]) { edgeSet.add(((long) i << 32) + j); } } for (int i = 0; i < E - (V - 1); i++) { int u; int v; long edge; while (true) { u = rnd.nextInt(V); v = rnd.nextInt(V); edge = ((long) u << 32) + v; if (u < v && !edgeSet.contains(edge)) break; } edgeSet.add(edge); g[u].add(v); g[v].add(u); } for (int i = 0; i < V; i++) Collections.sort(g[i]); return g; } static int[] getRandomArrangement(int n, int m, Random rnd) { int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = i; } for (int i = 0; i < m; i++) { int j = n - 1 - rnd.nextInt(n - i); int t = res[i]; res[i] = res[j]; res[j] = t; } return Arrays.copyOf(res, m); } static void checkGraph(int V, int E, Random rnd) { List<Integer>[] g = getRandomUndirectedConnectedGraph(V, E, rnd); int n = g.length; int[][] a = new int[n][n]; int edges = 0; for (int i = 0; i < n; i++) { for (int j : g[i]) { ++a[i][j]; ++edges; } } if (edges != 2 * E) { throw new RuntimeException(); } for (int i = 0; i < n; i++) { if (a[i][i] != 0) { throw new RuntimeException(); } for (int j = 0; j < n; j++) { if (a[i][j] != a[j][i] || a[i][j] != 0 && a[i][j] != 1) { throw new RuntimeException(); } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter the length of code: "); int n = sc.nextInt(); int[] code = new int[n]; for (int i = 0; i < n; i++) { code[i] = sc.nextInt(); } List<Integer>[] tree = pruferCode2Tree(code); Random rnd = new Random(1); for (int step = 0; step < 1000; step++) { int V = rnd.nextInt(50) + 2; checkGraph(V, V - 1, rnd); checkGraph(V, V * (V - 1) / 2, rnd); checkGraph(V, rnd.nextInt(V * (V - 1) / 2 - (V - 1) + 1) + V - 1, rnd); } System.out.println("Prufer code to tree conversion: " + Arrays.toString(tree)); System.out.println("Tree to prufer code conversion: " + Arrays.toString(tree2PruferCode(tree))); sc.close(); } }
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]
Related posts:
Một số ký tự đặc biệt trong Java
Hướng dẫn Java Design Pattern – Adapter
Java Program to Implement Meldable Heap
Comparing Arrays in Java
Period and Duration in Java
Hướng dẫn Java Design Pattern – Mediator
Rest Web service: Filter và Interceptor với Jersey 2.x (P1)
Java Program to Compute the Volume of a Tetrahedron Using Determinants
Ways to Iterate Over a List in Java
Java Program to Use Above Below Primitive to Test Whether Two Lines Intersect
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
An Introduction to ThreadLocal in Java
Quick Guide to the Java StringTokenizer
Comparing Two HashMaps in Java
Introduction to Eclipse Collections
Calling Stored Procedures from Spring Data JPA Repositories
Spring Security and OpenID Connect
Wrapper Classes in Java
Vector trong Java
Send email with SMTPS (eg. Google GMail)
Java Program to Implement Rolling Hash
Getting Started with Forms in Spring MVC
Hướng dẫn Java Design Pattern – Decorator
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Java Program to Perform Searching in a 2-Dimension K-D Tree
Using JWT with Spring Security OAuth
Java Program to Represent Graph Using Adjacency List
Java Program to Implement Bellman-Ford Algorithm
Biến trong java
Java Program to Implement Adjacency List
Guide to Mustache with Spring Boot