0

|V| である Prim Algo のこの MST 実装があります。べき乗 3。しかし、CLRS は、|V| を仮定すると、複雑さは O (E * lg |V| ) であると言っています。〜|E| その O(|V| * lg |V|) 。私の実装は修正されるかもしれませんが、どうすれば |V| を下回ることができるのかわかりません。* |V| マトリックス実装で

class matrix_graph
{
private:
    int** v;
    int vertexes;
public:
    matrix_graph(int**, int);
    ~matrix_graph(void);
    bool is_connected(int i,int j);
    int egde_weight(int i,int j){return v[i][j];}
};






int mst()
{
    int v[9][9] = {  
        {0,4,0,0,0,0,0,0,8},
        {0,0,8,0,0,0,0,0,11},
        {0,8,0,7,0,4,0,2,0},
        {0,0,7,0,9,14,0,0,0},
        {0,0,0,9,0,10,0,0,0},
        {0,0,4,14,10,0,2,0,0},
        {0,0,0,0,0,2,0,6,1},
        {0,0,2,0,0,0,6,0,7},
        {8,11,0,0,0,0,1,7,0}
    };

    int* ptr_v[9];
    for(int i=0;i<9;i++){
        ptr_v[i] = & v[i][0];
    }
    matrix_graph* m = new matrix_graph(ptr_v , 9 );

    std::set<int> tree;
    tree.insert(0);

        std::set<int> non_tree;
        non_tree.insert(1);
    non_tree.insert(2);
    non_tree.insert(3);
    non_tree.insert(4);
    non_tree.insert(5);
    non_tree.insert(6);
    non_tree.insert(7);
    non_tree.insert(8);

    int i = 0;
    int min = _I32_MAX;
    int add_to_tree;
    int sum = 0;

    while(!non_tree.empty()){
        for(std::set<int>::iterator iter = tree.begin() ; iter != tree.end() ; iter++ ){
            for(std::set<int>::iterator iter_n = non_tree.begin() ; iter_n != non_tree.end() ; iter_n++){
                int edge = m->egde_weight(*iter , *iter_n);
                if( edge > 0 && edge < min)
                {
                    min = edge;
                    add_to_tree = *iter_n;
                }
            }
        }
        tree.insert(add_to_tree);
        non_tree.erase(add_to_tree);
        sum += min;
        min = _I32_MAX;
    }
    return sum;
}
4

1 に答える 1

4

Adjacency list (Adjacency Matrix ではありません) を使用してグラフを表す必要があります。次に、実装で O(E * lg |V| ) を指定できます。

実行時間をさらに最適化したい場合は、フィボナッチ ヒープを使用して最小値を抽出できます。次に、O (|E| + V * lg |V| ) の実行時間を達成できます。フィボナッチ ヒープを使用すると、実行中の償却済み O(lg n) 内の要素を見つけて削除できます。

詳細:

http://en.wikipedia.org/wiki/Fibonacci_heap

フィボナッチ ヒープについては、CLRS ブックでも説明されています。

于 2013-06-29T10:49:09.587 に答える