Using BFS algorithm to find the shortest path

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);
        }
    }
}

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

Solution 1

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.

Solution 2

BFS is similar to DFS. Instead of going as deep as you can, backtracking and repeating, you look at all nodes at depth 1, then all nodes of depth 2, etc, until you've visited all nodes.

Basic Algorithm:

 -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

Solution 3

For Finding Shortest Path (Written in C++ / C++11)

I think this important to add here, especially because the title is on shortest paths! (the code below that actually allow you to find one) In addition: As mentioned above (in the comments to the second reply) DFS and BFS are pretty much not(!) the same algorithms, the similarity in the code in which replacing the stack with a queue and allowing you to jump from one to another does not make them "essentially the same". BFS is by far the better/right one (between the two) to find the shortest path in an unweighted graph. BFS is building layers from the source and DFS is going as deep as it can.

Actually when running BFS (to find the shortest path) you should initialize your nodes with a "distance" parameter with a very large number and instead using the visited DS, you update it to the parent's distance + 1 (only if it's still with the initialized value).

A simple example would be:

#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];
}

Inspired by Steven & Felix, from: Competitive Programming 3

Comments

[Mooing Duck]

I'm pretty sure DFS and BFS are not "exactly" the same algorithm.

[ardent]

Clarified for accuracy, they are essentially the same algorithm with the only difference being how you add and remove nodes from your data structure. :)

[user2489034]

Changing list into deque, and pop_back() to pop_front() displays empty array as the result.

[ardent]

Have you tried just using the list? You've implemented the stack in terms of a list, and you can do the same thing with a queue.

[G. Bach]

@MooingDuck They can be implemented exactly the same, exchanging a queue for a stack or vice versa (and of course along with them the method names for putting an element into the structure and taking an element out).

[user2489034]

Oh, yeah, you're right, it works now. But still, it has to look for the shortest path, but instead it finds the spanning tree.

[ardent]

@user2489034 The minimum spanning tree IS the shortest path from the root to any other node in the graph. This is due to the graph being unweighted/having equivalent weights between all the nodes.

[G. Bach]

@ardentsonata More precisely, in an unweighted graph, every shortest path tree is an MST, but the other way around doesn't hold in general. Restricted to MSTs found by a BFS, the inclusion holds, though.

[ardent]

@user2489034 You can think of it like this: "Every node has a path to the root, with path length equal to its level (just follow the tree itself), and no path can skip a level so this really is a shortest path." ics.uci.edu/~eppstein/161/960215.html

[ardent]

@G.Bach That is true. My algorithms are a little rusty and I'm just full of inaccurate generalizations today it seems. @_@

[Kohn1001]

As mentioned above (in the comments to this reply) DFS and BFS are pretty much not(!!!) the same algorithms, the similarity in the code in which replacing the stack with a queue and allowing you to jump from one to another does not make them "essentially the same". BFS is by far better/right one (between the two) to find the shortest path in an unweighted graph. BFS is building layers from the source and DFS is going deep as it can