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

Answer 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.

Answer 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

Answer 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

Answer 4

No,you don't have to change much in your code. just replace replace stack in case of DFS with Queue and it will become BFS.

Difference in implementation of BFS and DFS is that "BFS is implemented using Queue and DFS is using Stack" (Reason is obvious that DFS does depth like in maze.)

SEE changes for yourself:

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

    }
}

As you can see implementation of both just differ "in use of STACK and QUEUE".

Hope this helps !