时间戳

首页 > 解决方案 > 函数返回的值与 return 语句之前的函数体中的值不同

c++ - 函数返回的值与 return 语句之前的函数体中的值不同

问题描述

我正在编写一个函数，该函数返回使用 kruskal 算法创建的最小生成树中两个节点之间的路径

map<string, set<string>> mst = { "A" : ["B"]
                                 "B" : ["A", "C", "D"]
                                 "C" : ["B"]
                                 "D" : ["B", "E"]
                                 "E" : ["D"] }

寻路算法如下：

vector<string> findPath(map<string, set<string>> mst, string src, string dest, vector<string> path) {
    if(src == dest) {
        cout << "Function path size: " << path.size() << endl;
        return path;
    }
    set<string> possible = mst[src];
    for(vector<string>::iterator it = path.begin(); it != path.end(); it++) {
        if(possible.find(*it) != possible.end())
            possible.erase(*it);
    }
    for(set<string>::iterator it = possible.begin(); it != possible.end(); it++) {
        vector<string> a = path;
        if(find(a.begin(), a.end(), src) == a.end())
                a.push_back(src);
        vector<string> p = findPath(mst, *it, dest, a);
        if(p[0] != "randValue") {
            return path;
        }
    }
    vector<string> p = path;
    p[0] = "randValue";
    return p;
}

如果我调用该函数：

vector<string> path;
path = findPath(mst, "A", "C", path);
cout << "Main path size: " << path.size() << endl;

输出是：

Function path size: 2
Main path size: 0

为什么函数不返回填充的路径？

标签： c++recursionstlgraph-algorithm

解决方案

我在我的函数中发现了问题，解决方案只是交换一个变量：

vector<string> findPath(map<string, set<string>> mst, string src, string dest, vector<string> path) {
    if(src == dest) {
        cout << "Function path size: " << path.size() << endl;
        return path;
    }
    set<string> possible = mst[src];
    for(vector<string>::iterator it = path.begin(); it != path.end(); it++) {
        if(possible.find(*it) != possible.end())
            possible.erase(*it);
    }
    for(set<string>::iterator it = possible.begin(); it != possible.end(); it++) {
        vector<string> a = path;
        if(find(a.begin(), a.end(), src) == a.end())
                a.push_back(src);
        vector<string> p = findPath(mst, *it, dest, a);
        if(p[0] != "randValue") {
            /**
             * RETURN p INSTEAD OF path
             */
            return p;
        }
    }
    vector<string> p = path;
    p[0] = "randValue";
    return p;
}

推荐阅读