使用BFS算法找到最短路径 [英] Using BFS algorithm to find the shortest path

问题描述

  std :: list< int> q; 
 std :: vector< bool> （cols + 1）; 
 for（int i = 1; i <= cols; i ++）visited [i] = false; 
 visited [x] = true; （std :: list< int> :: iterator i = l [x] .begin（）; $！
 if（！l [x] .empty（））
 {
 = 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; （std :: list< int> :: iterator i = 1 [y] .begin（）; i！= l [y]）
 if（！l [y] .empty（））
 .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）; 
 
 
 
 
 
 $ b这是我的DFS算法在图中找到生成树。我需要将它转换为BFS算法，找到两个顶点之间的最短路径。那么......我该怎么做？ BFS算法有点类似于上面的算法吗？或者我需要从头开始编写它？
 
 
 
 l  - 邻接列表
 dfst  - 数组持有生成树
x  - 起始顶点
y  -  helper variable  
 
解决方案
 DFS和BFS实质上是相同的算法。诀窍是你使用哪种数据结构，或者说首先探索哪些节点。 
 
 
深度优先搜索使用堆栈，因此会尽可能地降低然后再回到算法中。
 
 
要利用广度优先搜索，您需要使用一个节点队列，并探索每个节点，添加它们的邻居（如果不是已经访问过）到队列中，然后在继续之前处理父节点的其余邻居。
 
 
 
这不会是你的代码的剧烈变化，只是一个改变你从列表中获取节点的方式。
 
 
 
而不是弹出后面，你可以简单地使用 q.pop_front（）来获得你的节点。
 
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);
        }
    }
}
This is my DFS algorithm for finding the spanning tree in a graph. I need to convert it to the BFS algorithm finding the shortest path between two vertices. Well...how can I do this? Is the BFS algorithm somewhat similar to the one above? Or do I need to write it from the beginning?

l - adjacency list
dfst - array holding spanning tree at the end
x - starting vertex
y - helper variable
解决方案
DFS and BFS are essentially the same algorithms. The trick is which data structure you use, or  rather which nodes you are exploring first.

A depth-first search utilizes a stack and would thus go as far down as possible before moving back in the algorithm.

To utilize a breadth first search, you would need to use a queue of nodes, and explore each node, add their neighbors (if not visited already) to the queue, and then process the rest of the parent node's neighbors before continuing onwards.

It wouldn't be a drastic change of your code, just a change in how you get nodes from your list.

Rather than popping off the back you would simply use q.pop_front() to get your nodes.

                        
这篇关于使用BFS算法找到最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！