This algorithm solves Hamiltonian path problem. G
is a unoriented graph, v
starting vertex,
G.size()
size of the graph, G.get(v).gV
all the neighbor verices of the current vertex.
static private void dfs(HashMap<Integer, Virsune> G, int v) {
path.push(v);
// add v to the current path
onPath[v] = true;
if (path.size() == G.size()) {
System.out.println(path);
Integer[] tmp = new Integer[G.size()];
System.arraycopy(path.toArray(), 0, tmp, 0, path.size());
hamPaths.add(tmp);
}
for (int w : G.get(v).gV) {
if (!onPath[w]) {
dfs(G, w);
}
}
path.pop();
onPath[v] = false;
}
// main method
dfs(G,0);
Can I just say that complexity of this algorithm is O(n!) ?
This is algorithm is enumerating all the paths of the graph.
If you're enumerating all the paths in a graph, this should give you a hint at the runtime. In a complete graph, there are indeed n! paths, so this is a lower bound. I'll leave it to you to say if it's an upper bound as well.
FWIW - the problem is solvable in O(2^n)