0

我正在尝试使用 C++ 和矩阵来实现 Prim 的算法。

这是我的问题：

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[][]是保持连接的二维矩阵。

nodeCon[]是将保存 MST 连接的数组（哪个节点与其他节点连接）

node[]=保存 nodeCon 的成本值。

我的问题是我将如何继续下一跳？假设我找到了最小连接，我将设置cNode= minConnection循环的外观？我怎么知道我检查了所有节点？

提前致谢

4

3 回答 3

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;
   }
};

另外值得注意的是：如果您将使用未使用的顶点列表而不是数组“已使用”，它会更快。

于 2013-01-16T23:17:47.087 回答
0

我目前无法评论上一个答案（因为我没有足够的声誉）所以我会通过另一个答案来做。Piotr 解决方案几乎是正确的，但我相信 Prim 的算法考虑的不仅仅是当前节点。一个例子可以在这里看到Prim 的算法。这实质上意味着您需要检查您访问过的节点的路径，而不仅仅是最近的节点。

这意味着您将需要存储一个向量，其中包含您访问过的节点并通过它们“针对每个”，而不是仅检查您访问过的最后一个节点的路径。

于 2013-01-16T23:43:53.663 回答
0

以下站点已实现算法和 junit 测试类。所以它应该是你正在寻找的。当然，单元测试类有一个实际的矩阵。并且实现类有代码。

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

于 2013-01-17T15:14:47.620 回答