0

C++と行列を使用してプリムのアルゴリズムを実装しようとしています。

これが私の問題です：

int node[] = {11, 11, 0, 11, 11, 11, 11, 11};
int nodeCon[8];

void generatePrims() {
    int cNode = 3;

    for (int i = 1; i <= 8; i++) {

        if (graph[cNode][i] != 0){

            if (node[i] > graph[cNode][i]) {
                node[i] = graph[cNode][i];
                nodeCon[i] = cNode;
                }
            }
        }
};

cNodeは開始ノードです。

graph[][]接続を保持する2次元行列です。

nodeCon[]MST（どのノードが他のノードに接続されているか）の接続を保持するアレイです

node[]=nodeConのコスト値を保持します。

私の質問は、どのようにしてネクストホップに進むのかということです。最小の接続を見つけ、cNode= minConnectionループがどのように見えるかという値を設定するとしますか？すべてのノードを調べたことをどうやって知ることができますか？

前もって感謝します

4

3 に答える 3

0

私は現在、前の回答にコメントすることができません（私は十分な評判を持っていないため）ので、別の回答を通してコメントします。Piotrソリューションはほぼ正しいですが、Primのアルゴリズムは現在のノード以上のものを考慮に入れていると思います。ここに例があります。プリムのアルゴリズム。これが本質的に意味することは、最新のノードだけでなく、アクセスしたノードからのパスをチェックする必要があるということです。

これは、最後にアクセスしたノードからのパスをチェックするだけではなく、アクセスしたノードを含むベクトルを保存する必要があることを意味します。

于 2013-01-16T23:43:53.663 に答える
0

このようなもの：

int node[]={11,11,0,11,11,11,11,11};
int used[]={0,0,0,0,0,0,0,0,0,0};
int nodeCon[8];

void generatePrims(){
   int cNode = 3;
   int next, min_now;
   for(int i=0; i<8; ++i) {
      used[cNode] = 1;
      min_now = MAX_INT;
      for(int i=1;i<=8;i++){
         if(!used[i]){ 
            if(node[i] > graph[cNode][i]){
               node[i] = graph[cNode][i];
               nodeCon[i]= cNode;
            }
            if(node[i] < min_now) {
               min_now = node[i];
               next = i;
            }  
         } 
      }
      cNode = next;
   }
};

また、注目に値する: 配列 'used' の代わりに、未使用の頂点のリストを使用すると高速になります。

于 2013-01-16T23:17:47.087 に答える
0

次のサイトには、アルゴリズムが実装されており、junit テスト クラスがあります。だから、それはあなたが探しているものでなければなりません。もちろん、単体テストクラスには実際のマトリックスがあります。そして、実装クラスにはコードがあります。

http://www.geekviewpoint.com/java/graph/mst

于 2013-01-17T15:14:47.620 に答える