最小生成樹時間複雜度

Question

我有這個MST實施Prim Algo這是| 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; 
} 

Answer 1

您需要使用鄰接列表（而不是鄰接矩陣）來表示圖。然後你的實現可以給O（E * lg | V |）。

如果您還想優化運行時間，可以使用斐波那契堆來提取最小值。然後你可以實現O（| E | + V * lg | V |）運行時間。使用斐波納契堆可以找到並刪除一個正在運行的分攤O（lg n）中的元素。

更多細節：

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

斐波那契堆也在CLRS本書中討論。