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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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, 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 & technical discussions at Telegram SanfoundryClasses.