-1

我正在尝试实现 Prims 算法来查找给定图的最小生成树。代码现在可以编译，但可执行文件（而不是打印 MST）会打印“segmentation fault:11”。此外，我收到警告：

Warning: control reaches end of non-void function

有人能帮我理解它有什么问题吗？提前致谢。

double Graph::getWeight(int v, int w)
{
    if(edge(v,w))
    {
        Node* t = adj[v];
        while(t != NULL)
        {
            t = t->next;
            if((t ->v) == w)
            return t->weight;
        }
    }
}
4

3 回答 3

7

警告指的是您的getWeight函数说它将返回 adouble但实际上仅double在某些条件下返回 a 。如果任一if语句为假（即 ifedge(v,1)为假或 ift->v == w始终为假），则该函数不返回任何内容。

如果条件不成立，也许您想返回一些默认值。

这是否是您的分段错误的原因是另一回​​事。

于 2012-12-14T21:52:30.420 回答
0

如果我理解正确，您的函数会尝试检索顶点v和之间给定边的权重w。如果该边不存在，或者它们之间的权重不存在于图形数据中，则该函数不会返回任何内容。

即使您知道您的数据结构将形成良好的格式，您也应该确保操作它的代码可以对不良数据做出反应。

#include <exception>
#include <string>

/* ... */

double Graph::getWeight(int v, int w)
{
    if(edge(v,w))
    {
        Node* t = adj[v];
        while(t != NULL)
        {
            t = t->next;
            if((t ->v) == w)
                return t->weight;
        }
    }
    std::string msg = "malformed graph: no edge between ";
    msg += v;
    msg += " and ";
    msg += w;
    throw std::runtime_error(msg);
}

如果图表格式不正确，上述内容至少会在运行时警告您。你甚至可以让它抛出两个不同的异常，具体取决于发生了什么问题（edge(v,w)为假或循环找不到正确的权重）。

如果您知道您的图表格式不正确，您可以尝试修复它，看看它是否也修复了您遇到的段错误。

于 2012-12-14T22:04:52.863 回答
-1

这部分只是一个更好的编码实践：

double Graph::getWeight(int v, int w)
{
    double result = 0.0;
    if(edge(v,w))
    {
        Node* t = adj[v];
        while(t != NULL)
        {
            t = t->next;
            if((t ->v) == w)
            result=t->weight;
        }
    }
    return result;
}
于 2012-12-14T22:00:18.210 回答