0

クラスカルのアルゴリズムをテストするために、単純な無向グラフを生成する必要があります。次のように作成された、すべての接続の構造があります。

    struct connection
    {
       node1;
       node2;
       edge_value;
    }

ここで、Kruskal をテストするために、これらの接続を適切な量生成する必要があります。Kruskal のアルゴリズムは、この世代ほど難しくはありませんでした。グラフに直面するのはこれが初めてだったからかもしれません。

4

1 に答える 1

3

kruskal アルゴリズムを実行したいので、データ構造は問題ありません。

すでに kruskal の実装があると仮定します (このデータ構造では、ベクトルを設定し、そのベクトルを適切な関数で並べ替え、最後にそのベクトルをウォークスルーするだけで、計算コストは​​ n になります)。ログ (n) )。

アルゴリズムをテストする必要がある場合は、uva の Web サイトを調べることをお勧めします。頭のてっぺんから、この問題を参照できます: http://uva.onlinejudge.org/external/113/11354.html kruskal の実装が機能するかどうかをテストする 3 つの事例..

于 2012-04-10T21:15:46.057 に答える