使用BFS算法找到最短路径

Question

std::list <int> q;
std::vector<bool> visited(cols + 1);
for(int i = 1; i <= cols; i++) visited[i] = false;
visited[x] = true;
if(!l[x].empty())
{
    for(std::list<int>::iterator i = l[x].begin(); i != l[x].end(); i++)
    {
        q.push_back(x); q.push_back(* i);
    }
    while(!q.empty())
    {
        y = q.back(); q.pop_back();
        x = q.back(); q.pop_back();
        if(!visited[y])
        {
            visited[y] = true;
            if(!l[y].empty())
            for(std::list<int>::iterator i = l[y].begin(); i != l[y].end(); i++)
            {
                if(!visited[*i])
                {q.push_back(y); q.push_back(* i);}
            }
            dfst[x].push_back(y);
            if(flag != 0) dfst[y].push_back(x);
        }
    }
}

这是我的DFS算法，用于在图形中查找生成树。我需要将其转换为BFS算法，以找到两个顶点之间的最短路径。好吧…我该怎么做？BFS算法与上面的算法有点相似吗？还是我需要从头开始编写它？

l-邻接表dfst-在最后保留生成树的数组x-起始顶点y-帮助程序变量

Answer 1

DFS和BFS本质上是相同的算法。诀窍在于您使用的是哪种数据结构，或更确切地说是您首先探索的是哪个节点。

深度优先搜索会利用堆栈，因此会在移回算法之前尽可能降低深度。

要使用广度优先搜索，您将需要使用节点队列，并浏览每个节点，将其邻居（如果尚未访问）添加到队列中，然后处理父节点的其余邻居，然后继续。

这不会对代码进行彻底的更改，而只是从列表中获取节点的方式的更改。

与其弹出后台，不如直接使用它q.pop_front()来获取节点。