0

该算法解决了哈密顿路径问题。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!) 吗？

4

1 回答 1

0

这是算法枚举图的所有路径。

如果您要枚举图中的所有路径，这应该会在运行时给您一个提示。在一个完整的图中，确实有 n! 路径，所以这是一个下限。我会让你说它是否也是一个上限。

FWIW - 问题可以在 O(2^n) 中解决

于 2012-05-02T18:15:34.500 回答