页面打开中,请稍候...
www.Gzu521.com
| 贵 州 学 习 网 |
|
//从顶点rt出发构造图g的最小生成树t，rt成为树的根结点 /
treeedgenode e; int i, k = 0, min, minpos, v; for ( i = 0; i < n; i++ ) //初始化最小生成树t if ( i != rt ) { t[k>.fromvex = rt; t[k>.tovex = i ; t[k++>.weight = g[rt>; } for ( k = 0; k < n-1; k++ ) { //依次求mst的候选边 min = maxint ; for ( i = k; i < n-1; i++ ) //遍历当前候选边集合 if ( t.weight < min ) //选具有最小权值的候选边 { min = t.weight; minpos = i ; } if ( min == maxint ) //图不连通, 出错处理 { cerr << “graph is disconnected!” << endl; exit(1) ; } e = t[minpos>; t[minpos> = t[k> ; t[k> = e; v = t[k>.tovex; for ( i = k+1; i < n-1; i++ ) //修改候选边集合 if ( g[v>[t.tovex> < t.weight ) t.weight = g[v>[t.tovex>; t.fromvex = v ; 参考答案 一、(1) 错 (2) 错 (3) 对 (4) 错 (5) 对 二、(1) b (2) c 三、3 四、h = élog2(n+1)ù -1 五、a. ① b. ③ c. ② d. ④ e. ③   |
责任编辑：gzu521
当前位置:
