c++ - prims 算法中父数组始终为零

Question

我有以下函数来查找父数组，以便使用 Prim 算法获得图的最小生成树。

#include<stdlib.h> 
#include <limits.h>
#include <iostream>

int printMST(int parent[], int n, int** graph)
{
for (int i = 1; i < n; i++)
std::cout<<parent[i]<<" - "<<i<<" "<<graph[i][parent[i]]<<"\n";
}
int* prim(int** graph,int no_of_vertices);
int main(){
int no_of_vertices;
std::cin>>no_of_vertices;
int** graph = new int*[no_of_vertices];
for(int i = 0; i < no_of_vertices; ++i)
 graph[i] = new int[no_of_vertices];
for(int i = 0; i <no_of_vertices; ++i)
for(int j = 0; j < no_of_vertices; ++j)
  std::cin>>graph[i][j];

 int* parent;
parent= prim(graph,no_of_vertices);
// Print the solution
printMST(parent, no_of_vertices, graph);
 return 0;
}

int nodeWithMinKey(int key[],bool mst[], int no_of_vertices)
{
int min=1000,min_index;

for(int i=0;i<no_of_vertices;i++)
{
if(mst[i]=false && key[i]<min)
    {
    min=key[i];
    min_index=i;
    }

}

return min_index;
}
int* prim(int** graph, int no_of_vertices){
    int* parent = (int*)malloc(sizeof(int)*no_of_vertices);

    int key[100];
    bool mst[100];
    int i;

    for(i = 0; i<no_of_vertices; i++)
    {
        key[i] = 1000;
        mst[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    for(i = 0; i<no_of_vertices-1; i++)
    {
        int u = nodeWithMinKey(key, mst, no_of_vertices);

        mst[u] = true;

        for(int v = 0; v<no_of_vertices; v++)
        {
            if(graph[u][v] && mst[v] == false && graph[u][v] <  key[v])
            {
                parent[v] = u;
                key[v] = graph[u][v];
            }

        }
    }
    return parent;
}

但是父数组的所有值都是“0”(零)，不知道哪里出了问题。

Answer 1

这一行

if(mst[i]=false && key[i]<min)

有一个赋值=而不是比较==。这将始终导致 if 测试始终失败，因此您的 min_index 将永远不会被设置。