-
Notifications
You must be signed in to change notification settings - Fork 4.3k
/
TreeCenter.java
114 lines (96 loc) · 3.28 KB
/
TreeCenter.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**
* This algorithm finds the center(s) of a tree.
*
* <p>Time complexity: O(V+E)
*
* @author Original author: Jeffrey Xiao, https://github.com/jeffrey-xiao
* @author Modifications by: William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.algorithms.graphtheory.treealgorithms;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class TreeCenter {
public static List<Integer> findTreeCenters(List<List<Integer>> tree) {
final int n = tree.size();
int[] degree = new int[n];
// Find all leaf nodes
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<Integer> edges = tree.get(i);
degree[i] = edges.size();
if (degree[i] <= 1) {
leaves.add(i);
degree[i] = 0;
}
}
int processedLeafs = leaves.size();
// Remove leaf nodes and decrease the degree of each node adding new leaf nodes progressively
// until only the centers remain.
while (processedLeafs < n) {
List<Integer> newLeaves = new ArrayList<>();
for (int node : leaves) {
for (int neighbor : tree.get(node)) {
if (--degree[neighbor] == 1) {
newLeaves.add(neighbor);
}
}
degree[node] = 0;
}
processedLeafs += newLeaves.size();
leaves = newLeaves;
}
return leaves;
}
/** ********** TESTING ********* */
// Create an empty tree as a adjacency list.
public static List<List<Integer>> createEmptyTree(int n) {
List<List<Integer>> tree = new ArrayList<>(n);
for (int i = 0; i < n; i++) tree.add(new LinkedList<>());
return tree;
}
public static void addUndirectedEdge(List<List<Integer>> tree, int from, int to) {
tree.get(from).add(to);
tree.get(to).add(from);
}
public static void main(String[] args) {
List<List<Integer>> graph = createEmptyTree(9);
addUndirectedEdge(graph, 0, 1);
addUndirectedEdge(graph, 2, 1);
addUndirectedEdge(graph, 2, 3);
addUndirectedEdge(graph, 3, 4);
addUndirectedEdge(graph, 5, 3);
addUndirectedEdge(graph, 2, 6);
addUndirectedEdge(graph, 6, 7);
addUndirectedEdge(graph, 6, 8);
// Centers are 2
System.out.println(findTreeCenters(graph));
// Centers are 0
List<List<Integer>> graph2 = createEmptyTree(1);
System.out.println(findTreeCenters(graph2));
// Centers are 0,1
List<List<Integer>> graph3 = createEmptyTree(2);
addUndirectedEdge(graph3, 0, 1);
System.out.println(findTreeCenters(graph3));
// Centers are 1
List<List<Integer>> graph4 = createEmptyTree(3);
addUndirectedEdge(graph4, 0, 1);
addUndirectedEdge(graph4, 1, 2);
System.out.println(findTreeCenters(graph4));
// Centers are 1,2
List<List<Integer>> graph5 = createEmptyTree(4);
addUndirectedEdge(graph5, 0, 1);
addUndirectedEdge(graph5, 1, 2);
addUndirectedEdge(graph5, 2, 3);
System.out.println(findTreeCenters(graph5));
// Centers are 2,3
List<List<Integer>> graph6 = createEmptyTree(7);
addUndirectedEdge(graph6, 0, 1);
addUndirectedEdge(graph6, 1, 2);
addUndirectedEdge(graph6, 2, 3);
addUndirectedEdge(graph6, 3, 4);
addUndirectedEdge(graph6, 4, 5);
addUndirectedEdge(graph6, 4, 6);
System.out.println(findTreeCenters(graph6));
}
}