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:
How to Delay Code Execution in Java
Tính kế thừa (Inheritance) trong java
Java Program to Implement the Program Used in grep/egrep/fgrep
Intersection of Two Lists in Java
Java Program to Implement Find all Back Edges in a Graph
Generating Random Dates in Java
Inheritance and Composition (Is-a vs Has-a relationship) in Java
How to Replace Many if Statements in Java
Assertions in JUnit 4 and JUnit 5
Custom Thread Pools In Java 8 Parallel Streams
Flattening Nested Collections in Java
Spring WebFlux Filters
So sánh HashMap và Hashtable trong Java
Recommended Package Structure of a Spring Boot Project
Java Program to Implement K Way Merge Algorithm
Java Program to Implement PriorityBlockingQueue API
Java Program to Represent Graph Using Incidence Matrix
Partition a List in Java
Java Program to implement Associate Array
Java Program to Solve Tower of Hanoi Problem using Stacks
Spring REST with a Zuul Proxy
Introduction to Liquibase Rollback
What is Thread-Safety and How to Achieve it?
Java Program to Construct an Expression Tree for an Infix Expression
Java Program to Implement Ford–Fulkerson Algorithm
Java Program to Implement Shell Sort
Spring Boot - CORS Support
Giới thiệu JDBC Connection Pool
Java Program to Implement Johnson’s Algorithm
Java Program to Generate a Random UnDirected Graph for a Given Number of Edges
Java Program to Check for balanced parenthesis by using Stacks
Immutable Objects in Java