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 に答える