该算法解决了哈密顿路径问题。G
是一个无向图,v
起始顶点,
G.size()
图的大小,G.get(v).gV
当前顶点的所有邻居顶点。
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);
我可以说这个算法的复杂度是 O(n!) 吗?