Hamiton图系列文章 (5) ：Hamilton图判定充要条件实现的算法复杂度分析

1. 首先看一下引用主程序。

#include "patharrayoptimized.h"
using namespace std;
 
int main(int argc, char *argv[])
{
    /*
    (0)--(1)--(2)
    |   / \   |
    |  /   \  |
    | /     \ |
    (3)-------(4)
    */
    vectorbool>> graph = {
            {0, 1, 0, 1, 0},
               {0, 1, 1, 1},
                  {0, 0, 1},
                     {0, 1},
                        {0}
                                };
 
    cout << "G1" << endl;
    PathArrayOptimized G1(graph);
    G1.help();
 
    PathArrayOptimized G = G1;
 
    for (int i=0; i<4; i++) {
        G = G * G1;
        cout << "G" << i+2 << endl;
        G.help();
    }
 
 
    if(G.isZero()){
        cout << "G does not have Hamilton circle\n";
    } else {
        cout << "G is Hamilton Graph with hamilton circle\n";
    }
 
    return 1;
}

设图G（V，E）的规模为N，也就是|V| = N，要求出G1^N,外循环需要N次，其实，G1^N可以分解如下：

G1^N  =  G1^(N/2) * G1^(N/2);

G1^(N/2) = G1^(N/4) * G1^(N/4);

....

也就是说外循环，可以做到log（N）次就可以求得G1^N。

2.其次看一下道路矩阵乘法

道路矩阵乘法实现中有循环控制变量7个(前面3个是平凡控制变量，跟正常的矩阵相乘含义一样)：

i，

        j，

                k,

                        x,

                                y,

                                        m,

                                                n

重点说一下x,y

x,y是道路矩阵中表示从节点i到节点k， 从节点k到节点j中所有的初级道路的个数。

以5节点完全图K5为例。

G1^4中这里的x与y都等于（n-2）!  = （5-2）！ = 6

3. 结论:

   这个实现算法，最坏情况下还是n! 级别，也就是说是指数级别的复杂度。