计算机科学论坛--关于最小支撑森林，请问这道真题算法中给定函数某些地方的确切含义

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

2004 DS 真题二. 算法判别和改进题

题目主要部分如下：

请分析下面算法能否求出图的“最小支撑森林”MSF。
1. 如果可以，请说明理由。
2. 如果不可以，请回答以下问题：
(1) 说明它为什么不能求出MSF。
(2) 按照下列要求写出修改后的算法：
a> 说明修改方案的基本思想。要求在原算法框架下进行简单修改，不允许进行太大的改动。
b> 写出完整的修改后的算法（只需要写函数Prim()部分，不需要写其它辅助内容），在算法中用下划线标出修改的内容。
c> 注意写止必要的注释，尤其是新修改的部分。
d> 假设图的顶点数为n、边数为e，请分析算法的时间代价，以及辅助的堆中元素最多可能有多少。

void Prim (Graph * G, int * D, int s) {
int V[G->n()];
int i, w;
for (i = 0; i < G->n(); i++) {               //处理顶点
  int v = minVertex(G, D);
  G->setMark(v, VISITED);
  if (v != s) AddEdgetoMST( V[v], v);
  if (D[v] == INFINITY) return;
  for (w = G->first(v); w < G->n(); w = G->next(v, w))
  if (D[w] > G->weight(v, w)) {
   D[w] = G->weight(v, w);    //修改距离数组D
   V[w] = v;                               //修改前驱记录
  }
}
}

问题：
1. D是距离数组，可它到底表示什么距离，在外层for循环中它表示离v最近邻接点的距离吗？
2. D的初始值情况如何，都是INFINITY吗？
3. “int v = minVertex(G, D);”中，minVertex函数到底是个什么含义？

这些函数在教材中中没出现的，题目里也没说得太清楚，悟也悟不太懂，请高人指点一下，谢谢了！

[此贴子已经被作者于2007-11-6 18:25:19编辑过]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

为什么没有人帮忙呀，本人很着急！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

问题：
1. D是距离数组，可它到底表示什么距离，在外层for循环中它表示离v最近邻接点的距离吗？
2. D的初始值情况如何，都是INFINITY吗？
3. “int v = minVertex(G, D);”中，minVertex函数到底是个什么含义？
----------------------------------------------------------------------------------------------------------------

这个题的算法是MST的prim算法：

1. D[i]表示结点 i 距离已经处理过的MST中的那些结点的最小距离；
2. 初始时D[s]=0, 因为始点s到自己的距离为0。其他的结点与s有边的就是边的权值，没边的都是INFINITY。
3. 找出所有与已经处理过的MST中结点相邻，且未访问的, D距离最小的结点。

int minVertex(Grap *G, int*D)
{
     int i, v;
     for (i = 0; i < G->n();  i++)
           if (G->setMark( i ) ==  UNVISITED)
           { v = i ;  break ; }
     for (i = 0; i < G->n();  i++)
          if (G->setMark( i ) ==  UNVISITED && D[I] < D[v] )
             v = i ;
     retrurn  v ;
}

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

谢谢你的回复，对我帮助太大了！回答描述很精确！


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	93.750ms