breadth-first-search - 广度优先搜索简单改进

Question

在大多数资源中，BFS 的实现是这样的（这是极客实现极客的极客）：

void findpaths(vector<vector<int> >&g, int src,  
                             int dst, int v) 
{ 
// create a queue which stores 
// the paths 
queue<vector<int> > q; 

// path vector to store the current path 
vector<int> path; 
path.push_back(src); 
q.push(path); 
while (!q.empty()) { 
    path = q.front(); 
    q.pop(); 
    int last = path[path.size() - 1]; 

    // if last vertex is the desired destination 
    // then print the path 
    if (last == dst)  
        printpath(path);         

    // traverse to all the nodes connected to  
    // current vertex and push new path to queue 
    for (int i = 0; i < g[last].size(); i++) { 
        if (isNotVisited(g[last][i], path)) { 
            vector<int> newpath(path); 
            newpath.push_back(g[last][i]); 
            q.push(newpath); 
        } 
    } 
} 

上面的实现建议我们首先将邻居添加到队列中，然后我们将检查它是否是我们的目的地。

但是我们可以在将邻居添加到队列时简单地检查邻居是否是目的地（而不是在轮到该节点时检查它）虽然这是一个非常小的改进，但比上一个要好。那么为什么大家都用之前的方法来实现BFS呢？

标签： breadth-first-search