Go to Qiita Advent Calendar Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@RYA234(RYA234)

JavaScriptで蟻本 グラフ　 最小全域木 プリム法

Last updated at Posted at 2024-10-11

概要

アルゴリズムの学習記録を投稿します。
今回は蟻本・グラフ・最小全域木のプリム法についてです。

問題

全域木の最小コストを求めよ。

入力
graph1 = [
        [INF,1,INF,INF,INF,INF,INF],
        [1,INF,3,INF,7,INF,2],
        [INF,3,INF,5,1,INF,INF],
        [INF,INF,5,INF,8,INF,INF],
        [INF,7,1,8,INF,5,INF],
        [INF,INF,INF,INF,5,INF,10],
        [INF,2,INF,INF,INF,10,INF]
        ]

vertexCount =  5

出力
17

※問題文は本には書かれていないので　入力と出力は自分がわかりやすいように書きました。

コード部分

//
/**最小全域木　プリム法　蟻本　p100
 *
 * @param graph{Array} 無向グラフ　隣接行列
 * @param vertexCount{Number} 頂点の数
 * @return {Number} 最小コスト
 */
const  prim = (graph,vertexCount) =>{
    let INF = 1000;
    // 初期化
    let used = new Array(vertexCount).fill(false);
    let mincosts = new Array(vertexCount).fill(INF); //最短経路
    let res = 0;
    mincosts[0] = 0;
    let loopCount = 0;
    console.log(`loopCount|u|v|used|res|条件|結果`);
    console.log(`---------|-|-|----|---|----|---`);
    while(true){
        let v = -1;
        for(let u=0; u<vertexCount; u++){
            // 最小となる頂点を探す
            if(!used[u] && (v == -1 || mincosts[u] < mincosts[v])) {
                loopCount++;
                v = u;
                console.log(`${loopCount}|${u}|${v}|${used}|${res}|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>${!used[u]} and (${v} =1 )| ${mincosts[u]} < ${mincosts[v]}`);
            }
        }

        if(v == -1) break;
        used[v] = true;
        res += mincosts[v];

        for(let u = 0;u < vertexCount; u++){
            loopCount++;
            mincosts[u] = Math.min(mincosts[u], graph[v][u]);
            console.log(`${loopCount}|${u}|${v}|${used}|${res}|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>${mincosts[u]}  = Math.min(${mincosts[v]},${graph[v][u]})`);
        }
    }
    return res;
}

let INF = 1000;
let graph1 = [[INF,1,INF,INF,INF,INF,INF],
        [1,INF,3,INF,7,INF,2],
        [INF,3,INF,5,1,INF,INF],
        [INF,INF,5,INF,8,INF,INF],
        [INF,7,1,8,INF,5,INF],
        [INF,INF,INF,INF,5,INF,10],
        [INF,2,INF,INF,INF,10,INF]
    ]

// 17
prim(graph1,7)

python tutor

コードを実際に動かせるwebサイト
ステップ実行かつステップ事の変数を確認できる特徴があります。

Python Tutorリンク

その他情報

感想

問題文がないからそれがちょっと手間だったんだよなぁ…
入力値を考えるのに時間かかった

依存関係グラフ

依存関係グラフは変数の結びつきを一目でわかりやすくするための図です。
変数の流れを確認しやすくすることでワーキングメモリの負担を減らすことができます。
作成方法はコード上の変数に丸付けて線を繋げています。

image.png

状態遷移図

計算内容を明示する表。
ステップごとの変数の値を各列に表示します。
複雑な計算を行うコードを理解するのに役立つ表です。

蟻本の値

loopCount u v used res 条件 結果
1 0 0 false,false,false,false,false,false,false 0 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (0 =1 ) 0 < 0
2 0 0 true,false,false,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(0,1000)
3 1 0 true,false,false,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(0,1)
4 2 0 true,false,false,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(0,1000)
5 3 0 true,false,false,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(0,1000)
6 4 0 true,false,false,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(0,1000)
7 5 0 true,false,false,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(0,1000)
8 6 0 true,false,false,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(0,1000)
9 1 1 true,false,false,false,false,false,false 0 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (1 =1 ) 1 < 1
10 0 1 true,true,false,false,false,false,false 1 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(1,1)
11 1 1 true,true,false,false,false,false,false 1 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(1,1000)
12 2 1 true,true,false,false,false,false,false 1 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])3 = Math.min(1,3)
13 3 1 true,true,false,false,false,false,false 1 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(1,1000)
14 4 1 true,true,false,false,false,false,false 1 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])7 = Math.min(1,7)
15 5 1 true,true,false,false,false,false,false 1 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(1,1000)
16 6 1 true,true,false,false,false,false,false 1 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(1,2)
17 2 2 true,true,false,false,false,false,false 1 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (2 =1 ) 3 < 3
18 6 6 true,true,false,false,false,false,false 1 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (6 =1 ) 2 < 2
19 0 6 true,true,false,false,false,false,true 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(2,1000)
20 1 6 true,true,false,false,false,false,true 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(2,2)
21 2 6 true,true,false,false,false,false,true 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])3 = Math.min(2,1000)
22 3 6 true,true,false,false,false,false,true 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(2,1000)
23 4 6 true,true,false,false,false,false,true 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])7 = Math.min(2,1000)
24 5 6 true,true,false,false,false,false,true 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])10 = Math.min(2,10)
25 6 6 true,true,false,false,false,false,true 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(2,1000)
26 2 2 true,true,false,false,false,false,true 3 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (2 =1 ) 3 < 3
27 0 2 true,true,true,false,false,false,true 6 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(3,1000)
28 1 2 true,true,true,false,false,false,true 6 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(3,3)
29 2 2 true,true,true,false,false,false,true 6 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])3 = Math.min(3,1000)
30 3 2 true,true,true,false,false,false,true 6 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(3,5)
31 4 2 true,true,true,false,false,false,true 6 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(3,1)
32 5 2 true,true,true,false,false,false,true 6 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])10 = Math.min(3,1000)
33 6 2 true,true,true,false,false,false,true 6 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(3,1000)
34 3 3 true,true,true,false,false,false,true 6 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (3 =1 ) 5 < 5
35 4 4 true,true,true,false,false,false,true 6 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (4 =1 ) 1 < 1
36 0 4 true,true,true,false,true,false,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(1,1000)
37 1 4 true,true,true,false,true,false,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(1,7)
38 2 4 true,true,true,false,true,false,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(1,1)
39 3 4 true,true,true,false,true,false,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(1,8)
40 4 4 true,true,true,false,true,false,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(1,1000)
41 5 4 true,true,true,false,true,false,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(1,5)
42 6 4 true,true,true,false,true,false,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(1,1000)
43 3 3 true,true,true,false,true,false,true 7 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (3 =1 ) 5 < 5
44 0 3 true,true,true,true,true,false,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(5,1000)
45 1 3 true,true,true,true,true,false,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(5,1000)
46 2 3 true,true,true,true,true,false,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(5,5)
47 3 3 true,true,true,true,true,false,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(5,1000)
48 4 3 true,true,true,true,true,false,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(5,8)
49 5 3 true,true,true,true,true,false,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(5,1000)
50 6 3 true,true,true,true,true,false,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(5,1000)
51 5 5 true,true,true,true,true,false,true 12 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (5 =1 ) 5 < 5
52 0 5 true,true,true,true,true,true,true 17 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(5,1000)
53 1 5 true,true,true,true,true,true,true 17 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(5,1000)
54 2 5 true,true,true,true,true,true,true 17 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(5,1000)
55 3 5 true,true,true,true,true,true,true 17 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(5,1000)
56 4 5 true,true,true,true,true,true,true 17 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(5,5)
57 5 5 true,true,true,true,true,true,true 17 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(5,1000)
58 6 5 true,true,true,true,true,true,true 17 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(5,10)

その他例１ 頂点数４個

入力
graph1 = [
        [INF,2,8,20],
        [2,INF,1,4],
        [8,1,INF,10],
        [20,4,10,INF]
        ]

vertexCount =  4

出力
7

image.png

loopCount u v used res 条件 結果
1 0 0 false,false,false,false 0 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (0 =1 ) 0 < 0
2 0 0 true,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(0,1000)
3 1 0 true,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(0,2)
4 2 0 true,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])8 = Math.min(0,8)
5 3 0 true,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])20 = Math.min(0,20)
6 1 1 true,false,false,false 0 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (1 =1 ) 2 < 2
7 0 1 true,true,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(2,2)
8 1 1 true,true,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(2,1000)
9 2 1 true,true,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(2,1)
10 3 1 true,true,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])4 = Math.min(2,4)
11 2 2 true,true,false,false 2 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (2 =1 ) 1 < 1
12 0 2 true,true,true,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(1,8)
13 1 2 true,true,true,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(1,1)
14 2 2 true,true,true,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(1,1000)
15 3 2 true,true,true,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])4 = Math.min(1,10)
16 3 3 true,true,true,false 3 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (3 =1 ) 4 < 4
17 0 3 true,true,true,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(4,20)
18 1 3 true,true,true,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(4,4)
19 2 3 true,true,true,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(4,10)
20 3 3 true,true,true,true 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])4 = Math.min(4,1000)

その他例2　頂点数５個

入力
graph1 = [
            [INF,2,8,20,INF],
            [2,INF,1,4,INF],
            [8,1,INF,10,30],
            [20,4,10,INF,5],
            [INF,INF,30,5,INF]
        ]

vertexCount =  5

出力
12

image.png

loopCount u v used res 条件 結果
1 0 0 false,false,false,false,false 0 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (0 =1 ) 0 < 0
2 0 0 true,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(0,1000)
3 1 0 true,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(0,2)
4 2 0 true,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])8 = Math.min(0,8)
5 3 0 true,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])20 = Math.min(0,20)
6 4 0 true,false,false,false,false 0 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(0,1000)
7 1 1 true,false,false,false,false 0 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (1 =1 ) 2 < 2
8 0 1 true,true,false,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(2,2)
9 1 1 true,true,false,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])2 = Math.min(2,1000)
10 2 1 true,true,false,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(2,1)
11 3 1 true,true,false,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])4 = Math.min(2,4)
12 4 1 true,true,false,false,false 2 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1000 = Math.min(2,1000)
13 2 2 true,true,false,false,false 2 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (2 =1 ) 1 < 1
14 0 2 true,true,true,false,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(1,8)
15 1 2 true,true,true,false,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(1,1)
16 2 2 true,true,true,false,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(1,1000)
17 3 2 true,true,true,false,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])4 = Math.min(1,10)
18 4 2 true,true,true,false,false 3 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])30 = Math.min(1,30)
19 3 3 true,true,true,false,false 3 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (3 =1 ) 4 < 4
20 0 3 true,true,true,true,false 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(4,20)
21 1 3 true,true,true,true,false 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(4,4)
22 2 3 true,true,true,true,false 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(4,10)
23 3 3 true,true,true,true,false 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])4 = Math.min(4,1000)
24 4 3 true,true,true,true,false 7 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(4,5)
25 4 4 true,true,true,true,false 7 最小となる頂点を探す !used[u] && (v == -1 or mincosts[u] < mincosts[v]) true and (4 =1 ) 5 < 5
26 0 4 true,true,true,true,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])0 = Math.min(5,1000)
27 1 4 true,true,true,true,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(5,1000)
28 2 4 true,true,true,true,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])1 = Math.min(5,30)
29 3 4 true,true,true,true,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])4 = Math.min(5,5)
30 4 4 true,true,true,true,true 12 最小コストを求める mincosts[u] = Math.min(mincosts[u], graph[v][u])5 = Math.min(5,1000)

参考資料

プログラミングコンテストチャレンジブック [第2版]　マイナビ　p100-101

プログラマー脳　秀和システム
p73 python tutor
p71 状態遷移表　
p69 依存関係グラフ

githubコミット部分

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?