论坛首页 综合技术论坛

克鲁斯卡尔时间复杂度怎么算出来的

浏览 3329 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-11-05  
克鲁斯卡尔时间复杂度怎么算出来的,特别是log(e),怎么算出来的.如下,这段代码的时间复杂度为什么是loge
int Find(int *parent, int f){
    while(parent[f] > 0){
        f = parent[f];
    }

    return f;
}
   发表时间:2011-11-14   最后修改:2011-11-14
也就是最小生成树吧

一、 克鲁斯卡尔(Kruskal)算法

  typedef struct {
   VertexType vex1;
   VertexType vex2;
   VRType weight;
  }EdgeType;
  typedef ElemType EdgeType;
  typedef struct {         // 有向网的定义
   VertexType vexs[MAX_VERTEX_NUM];  // 顶点信息
   EdgeType edge[MAX_EDGE_NUM];    // 边的信息
   int vexnum,arcnum;        // 图中顶点的数目和边的数目
  }ELGraph;
     
 
  由于克鲁斯卡尔算法是依权值从小到大依次考察每条边,则在本章7.2节中讨论的各种图的表示方法在此都不适用。由此需对图定义一种新的表示方法,以一维数组存放图中所有边,并在构建图的存储结构时将它构造为一个"有序表"。  
   算法 7.8
  void MiniSpanTree_Kruskal(ELGraph G, SqList& MSTree)
 {
  // G.edge 中依权值从小到大存放有向网中各边,按克鲁斯卡尔
  // 算法求得生成树的边存放在顺序表 MSTree 中
  MFSet F;
  InitSet(F, G.vexnum);         // 将森林F初始化为n棵树的集合
  InitList(MSTree, G.vexnum);      // 初始化生成树为空树
  i=0; k=1;
  while( k<G.vexnum ) {
   e = G.edge[i];           // 取第 i 条权值最小的边  
  以顺序表MSTree返回生成树上各条边。  
     r1 = fix_mfset(F, LocateVex(e.vex1));
   r2 = fix_mfset(F, LocateVex(e.vex2)); // 返回两个顶点所在树的树根
   if (r1 != r2) {           // 选定生成树上第k条边
    if (ListInsert(MSTree, k, e)) k++; // 插入生成树
    mix_mfset(F, r1, r2);       // 将两棵树归并为一棵树
   } // if
   i++;                // 继续考察下一条权值最小边
  } // while
  DestroySet(F);
 } // MiniSpanTree_Kruskal

0 请登录后投票
   发表时间:2011-11-14  
如果不考虑建立图的存储结构所需时间,则克鲁斯卡尔算法的时间复杂度为O (e)。
0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics