DFS and BFS in a graph in C++

Question

Here goes the depth first search:

#include <vector>
#include <iostream>

using namespace std;

typedef vector<vector<int> > graph; // adjacency list, vertexs are integers


void dfs(graph g, int s0) // s0 is the first vertex in the search
{
    int n = g.size();

    if(s0 < 0 || s0 >= n) // invalid initial vertex
        return;

    vector<bool> already_seen(n, false);
    vector<int> to_be_handled {};

    to_be_handled.push_back(s0);

    while(to_be_handled.size() > 0)
    {
        int s = to_be_handled.back();
        to_be_handled.pop_back();

        if(!already_seen[s])
        {
            already_seen[s] = true;

            cout << s << " "; // handle s

            for(int v: g[s]) // add neighbors
                to_be_handled.push_back(v); // (*)
        }
    }
}

And for the breadth first search, just replace the line (*) with this line:

to_be_handled.insert(to_be_handled.begin(), v);

I guess using a queue would be more effective for the BFS but I initially just wanted to implement a DFS so don't mind the second one.

Answer 1

using namespace std is considered bad practice.

---

to_be_handled.insert(to_be_handled.begin(), v); will badly hurt the performance. As mentioned in comments, BFS benefits from using std::queue, which is specifically designed for this purpose.

Simulating stack with std::vector is also dubious, again from the performance point of view. std::vector guarantees contiguous storage, and the you'd have to face reallocation penalty as it grows. Again, std::stack is specifically designed to avoid such a penalty.

---

The utility of the function is severely limited by the handler being hardcoded. You may pass the handler as an argument, or better yet restructure the code to make them iterators of Graph, and let the client handle vertices, e.g.:

    Graph g;
    for (auto it: g.bfs_iterator(start)) {
        handle(it);
    }

Answer 2

Here my little remarks, on top of what vnp said:

1. Use the right functions

   while(to_be_handled.size() > 0)
   

   Is bad, especially if you consider switching to a stack that is by default based on a deque. Instead use the right function

   while(!to_be_handled.empty())
   

   This is not only more descriptive, but also more efficient, as it does not have to walk all the list to generate size().

2. Use std::stack or std::queue for DFS or BFS. If you think, that memory locality is important to you, remember that stack is a container adaptor, so you can write:

   std::stack<int, std::vector<int>>
   

   And have a stack based on a std::vector

3. The second most frequent topic next to namespace std. Use descriptive names! What is g,v,n? In this limited example this might be easy, but does it hurt to write

   for (int neighbor : thisGraph(currentNode))
   

   Ask yourself in 6 month from now will this be easier to understand than

   for (int v: g(v))
   

4. You can omit the empty brackets for the declaration of to_be_handled