- 535 名前：デフォルトの名無しさん [2008/01/24(木) 01:39:57 ]
- [1] 授業単元：アルゴリズム2
[2] 問題文
最小全域木問題
で以下のコメント文の
e[i] を、e[t[0]], ..., e[t[k - 1]]に加えても閉路ができない
をどうやって書くのか分かりません。トレースの問題で躓いてしまいます。
プログラムが分かればトレース出来そうなのでよろしくお願いします。
void mst(int i, int k, int weight) {
if (k == n - 1) {
if (weight < best_weight) {
best_weight = weight;
配列 best_tree に t をコピー;
}
}
else if (i <= m) {
if (e[i] を、e[t[0]], ..., e[t[k - 1]]に加えても閉路ができない）{
t[k] = i;
mst(i + 1, k + 1, weight + w[i]);
}
mst(i + 1, k, weight);
}
}
[4] 期限：1/24 9am test..!
