0

我有这个用于 Prim Algo 的 MST 实现，它是 |V| 到电源 3。但是 CLRS 说它说复杂度是 O (E * lg |V| ) 假设 |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

您需要使用邻接列表（而不是邻接矩阵）来表示图形。然后你的实现可以给出 O(E * lg |V|)。

如果您想进一步优化运行时间，您可以使用斐波那契堆提取最小值。然后你可以实现 O (|E| + V * lg |V| ) 运行时间。使用斐波那契堆，您可以在摊销 O(lg n) 运行中找到并删除一个元素。

更多细节：

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

斐波那契堆也在 CLRS Book 中讨论过。

于 2013-06-29T10:49:09.587 回答