#9. Hamilton Cycle / Path

Hamilton Cycle: A cycle with each vertex exactly once.

Hamilton Cycle是一个Backtracking问题!

#9.1 Hamiltonian Cycle for Directed Graph

Java Hamiltonian Cycle

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
public static boolean hasHamiltonCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Set<Integer> visited = new HashSet<>();
final List<Integer> res = new ArrayList<>();
for (final int v : graph.keySet()) {
visited.add(v);
res.add(v);
if (backtracking(v, graph, visited, res)) {
return true;
}
res.remove(0);
visited.remove(v);
}
return false;
}
private static boolean backtracking(final int v, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final List<Integer> res) {
if (res.size() == graph.size()) {
// If the last node in res list is connected to the first node in the res list
final int lastNode = res.get(res.size() - 1);
final int firstNode = res.get(0);
if (graph.get(lastNode).contains(firstNode)) {
return true;
} else {
return false;
}
}
for (final int adj : graph.get(v)) {
if (!visited.contains(adj)) {
visited.add(adj);
res.add(adj);
if (backtracking(adj, graph, visited, res)) {
return true;
}
res.remove(res.size() - 1);
visited.remove(adj);
}
}
return false;
}

#9.2 Hamiltonian Cycle for Undirected Graph

Hamilton Cycle对于Undirected Graph依旧是一个Backtracking的problem

和Directed Graph唯一的区别就是要pass一个parent避免无限循环.

Java Hamiltonian Cycle

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
public static boolean hasHamiltonCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
return new IllegalArgumentException();
}
final Set<Integer> visited = new HashSet<>();
final List<Integer> res = new ArrayList<>();
for (final int v : graph.keySet()) {
visited.add(v);
res.add(v);
if (backtracking(v, graph, visited, res, v)) {
return true;
}
res.remove(0);
visited.remove(v);
}
return false;
}
private static void backtracking(final int v, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final List<Integer> res, final int parent) {
if (res.size() == graph.size()) {
final lastNode = res.get(res.size() - 1);
final firstNode = res.get(0);
if (graph.get(lastNode).contains(firstNode)) {
return true;
} else {
return false;
}
}
for (final int adj : graph.get(v)) {
if (adj != parent && !visited.contains(adj)) {
visited.add(adj);
res.add(adj);
if (backtracking(adj, graph, visited, res, v)) {
return true;
}
res.remove(res.size() - 1);
res.remove(adj);
}
}
return false;
}

Comments

01/03/2020