2 
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 - 辅助变量

4

4 回答 4

4

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

深度优先搜索利用堆栈，因此在返回算法之前会尽可能地向下搜索。

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

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

而不是从后面弹出，您只需使用它q.pop_front()来获取您的节点。

于 2013-06-18T21:13:02.273 回答
3

BFS 类似于 DFS。不是尽可能深入，回溯和重复，而是查看深度为 1 的所有节点，然后查看深度为 2 的所有节点，依此类推，直到访问完所有节点。

基本算法：

 -Choose a starting node and add to LookQueue
 -look at all nodes directly touching and add them to LookQueue
 -when you've looked at them all
    -look at all nodes in LookQueue (removing them as you do)
    and look at all nodes touching them (adding them as you do)
       -repeat until all nodes are visited
于 2013-06-18T21:13:34.987 回答
2

寻找最短路径 （用 C++ / C++11 编写）

我认为在此处添加这一点很重要，尤其是因为标题位于最短路径上！（下面的代码实际上可以让您找到一个）另外：如上所述（在第二个回复的评论中）DFS 和 BFS 几乎不是（！）相同的算法，在代码中替换与队列堆叠并允许您从一个跳到另一个并不会使它们“基本相同”。BFS 是迄今为止在未加权图中找到最短路径的更好/正确的方法（两者之间）。BFS 正在从源头构建层，而 DFS 正在尽可能深入。

实际上，在运行 BFS（以查找最短路径）时，您应该使用具有很大数字的“距离”参数初始化节点，而不是使用访问过的 DS，将其更新为父节点的距离 + 1（仅当它仍然与初始化值）。

一个简单的例子是：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;
const int imax = std::numeric_limits<int>::max();
using vi = vector<int>;

/* printPath - implementation at the end */    
void
printPath(int s, int t, const vi &path);

/*input:
* n is number of the nodes in the Graph
* adjList holds a neighbors vector for each Node
* s is the source node
*/

void dfs(int n, vector<vi> adjList, int s)
{
    //imax declared above as the max value for int (in C++)
    vector<int> distance(n, imax);
    vi path;
    queue<int> q; q.push(s); distance[s] = 0;

    while (!q.empty()) {
        auto curr = q.front(); q.pop();

        for (int i = 0; i < (int)adjList[curr].size(); ++i) {
            if (distance[i] == imax) {
                distance[i] = distance[curr] + 1;
                //save the parent to have the path at the end of the algo.
                path[i] = curr;
            }
        }//for
    }//while
     /* t can be anything you want */
    int t = 5;
    printPath(s, t, path); cout << endl;
}

/* print the shortest path from s to t */ 
void
printPath(int s, int t, const vi &path)
{
    if (t == s) {
        return;
    }
    printPath(s, path[t], path);
    cout << path[t];
}

灵感来自 Steven & Felix，来自： Competitive Programming 3

于 2017-02-03T18:41:39.247 回答
0

不，您不必对代码进行太多更改。只需将 DFS 的替换堆栈替换为队列，它将成为 BFS。

BFS 和 DFS 实现的区别在于“BFS 使用 Queue 实现，DFS 使用 Stack”（原因很明显，DFS 做深度就像迷宫一样。）

亲自查看更改：

文件系统：

void dfs(int start)
{
    int j,temp; 
    stack<int> s; //STACK
    s.push(start);
    vector<int>:: iterator it;
    while(s.empty()==0)
    {
        temp=s.top(); // Top element from Stack
        s.pop();
        status[temp]=1; // marked as visited , 0 means unvisited
        cout<<temp<<endl; // visited element
        for(it=list[temp].begin();it!=list[temp].end();it++)
        {
            j=*it;
            if(status[j]==0)
            {
                s.push(j);
                status[j]=2;    // means that it is in stack        
            }
        }

    }
}

BFS：

void bfs(int start)
{
    int j,temp; 
    queue<int> q; // QUEUE
    q.push(start);
    vector<int>:: iterator it;
    while(q.empty()==0)
    {
        temp=q.front(); // Front element from Queue
        q.pop();
        status[temp]=1; // marked as visited , 0 means unvisited
        cout<<temp<<endl; // visited element
        for(it=list[temp].begin();it!=list[temp].end();it++)
        {
            j=*it;
            if(status[j]==0)
            {
                q.push(j);
                status[j]=2;    // means that it is in queue        
            }
        }

    }
}

正如您所看到的，两者的实现只是“使用堆栈和队列”不同。

希望这可以帮助 ！

于 2013-06-18T21:59:06.483 回答