c++ - BFS 路径 C++ 实现返回返回一个额外的值

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

1. 像您一样添加头部顶点，但没有路径。
2. 提取队列的头部并将所有相邻顶点添加到队列中，并带有指向其前任的链接。
3. 重复直到队列不为空或到达尾部。
4. 通过指向前人的链接获取从头到尾的路径。

顺便说一句，我建议你不要使用 queue.erase(...)当你想删除队头时的方法(使用queue.pop()代替)。而且，您可以更改 map.at(key)简单的方法map[key] .

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