BFS 路径 C++ 实现 returning return 一个额外的值

Question

我正在尝试使用广度优先搜索实现一个函数来查找给定开始和结束节点的路径。我是 c++ 的新手，我已经在 python 中实现了相同的功能并且它有效。

下图应该给出路径{{1, 3, 6}, {1, 2, 5, 6}}:

map<int, vector<int> > aGraph = {
    {1, {2, 3}},
    {2, {1, 4, 5}},
    {3, {1, 6}},
    {4, {2}},
    {5, {2, 6}},
    {6, {3, 5}}
};

我创建了一个名为 BFSPaths 的函数来解决这个问题，但是我的答案总是多了一个数字 {{1, 2, 3, 6}, {1, 2, 4, 5, 6}}。我一直无法弄清楚为什么将 2 和 4 添加到答案中。这就是函数的样子：

vector<vector<int>> BFSPaths(map<int, vector<int>> &graph, int head, int tail)
{
    vector<vector<int>> out;
    vector<int> init {head};
    vector<tuple<int, vector<int>>> queue = { make_tuple(head, init) };

    while (queue.size() > 0)
    {
        int vertex = get<0>(queue.at(0));
        vector<int> path = get<1>(queue.at(0));
        queue.erase(queue.begin());

        vector<int> difference;
        sort(graph.at(vertex).begin(), graph.at(vertex).end());
        sort(path.begin(), path.end());

        set_difference(
                graph.at(vertex).begin(), graph.at(vertex).end(),
                path.begin(), path.end(),
                back_inserter( difference )
        );

        for (int v : difference)
        {
            if (v == tail)
            {
                path.push_back(v);
                out.push_back(path);
            }
            else
            {
                path.push_back(v);
                tuple<int, vector<int>> temp (v, path);
                queue.push_back(temp);
            }
        }
    }
    return out;
}

这就是我调用函数的方式（打印到 shell）：

void testBFSPaths(map<int, vector<int>> &graph, int head, int tail)
{
    vector<vector<int>> paths = BFSPaths(graph, head, tail);

    for (int i=0; i<paths.size(); i++)
    {
        print(paths.at(i));
    }
}

int main ()
{
    // graph definition goes here ....

    testBFSPaths(aGraph, 1, 6);
}

如果有人能在正确的方向上推动我，我将不胜感激。

Answer 1

据我了解，您在此处计算可达顶点与到当前顶点的路径之间的集合差异：

set_difference(
    graph.at(vertex).begin(), graph.at(vertex).end(),
    path.begin(), path.end(),
    back_inserter( difference )
);

但是对于BFS来说没有任何意义。正如您进一步看到的，您正在将此差异的顶点添加到您的答案中，无论它们是否位于从头到尾的路径上。在这种情况下，您应该考虑另一种方法并稍微更改您的算法。我推荐的步骤：

像您一样添加头部顶点，但没有路径。
提取队列的头部并将所有相邻顶点添加到队列中，并为其前导添加 link。
重复直到队列不为空或到达尾部。
跟随前人link得到从头到尾的路径

顺便说一句，我建议您在要删除队头时不要使用 queue.erase(...) 方法（请改用 queue.pop()）。而且，您可以将 map.at(key) 方法更改为简单的 map[key].

最后一件事——我不太清楚如果必须经常对它们进行排序，为什么要将相邻顶点存储在 vector<int> 中。使用 set<int> 之类的东西，这样您就不必担心了。

Answer 2

问题是路径正在更新path.insert(path.end(), v)。我需要使用临时路径，以便在迭代期间访问的节点不会不必要地更改原始路径。

我也用了集合（区别不大，只是去掉了排序步骤）。

固定后的函数如下所示：

vector<set<int>> BFSPaths(map<int, set<int>> &graph, int head, int tail)
{
    vector<set<int>> out;
    set<int> init {head};
    queue<tuple<int, set<int>>> aQueue;
    aQueue.push( make_tuple(head, init) );

    while (aQueue.size() > 0)
    {
        int vertex = get<0>(aQueue.front());
        set<int> path = get<1>(aQueue.front());
        aQueue.pop();

        vector<int> difference;
        set_difference(
            graph[vertex].begin(), graph[vertex].end(),
            path.begin(), path.end(),
            back_inserter( difference )
        );


        for (int v : difference)
        {
            set<int> tempPath;
            tempPath.insert(path.begin(), path.end());
            tempPath.insert(tempPath.end(), v);

            if (v == tail)
            {
                out.push_back(tempPath);
            }
            else
            {
                tuple<int, set<int>> temp (v, tempPath);
                aQueue.push(temp);
            }
        }
    }

    return out;
}

tempPath 现在是传递到队列或添加到 out 向量的内容。

BFS 路径 C++ 实现 returning return 一个额外的值

BFS paths C++ implementation returning return an extra value

c++

c++11

breadth-first-search