DFS/BFS implementation of Cormen's pseudo code

Question

This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this.

#include "iostream"
#include "vector"
#include "list"

enum color{
    WHITE,
    GREY,
    BLACK
};

struct edge{
    int destination_vertex;
    edge(int ver){
        destination_vertex = ver;
    }
};

struct vertex{
    int id;
    color visited;
    std::list<edge>  list;
    vertex(int _id){
        id = _id;
    }
};


class graph
{
private:
    std::vector<vertex> vertexes;
    void dfs_visits(vertex& source);
    int next;
public:
    graph(void){
        next = 0;
    }
    ~graph(void){}
    void dfs();
    void bfs();
};



void graph::dfs(void)
{
    for(std::vector<vertex>::iterator iter =vertexes.begin();iter < vertexes.end();iter++ ){
        iter->visited = WHITE;  
    }   

    for(std::vector<vertex>::iterator iter =vertexes.begin();iter < vertexes.end();iter++ ){
        if(iter->visited == WHITE){
            dfs_visits(*iter);
        }
    }
}


void graph::dfs_visits(vertex& source){
    source.visited = GREY;
    for(std::list<edge>::iterator iter = source.list.begin();iter != source.list.end();iter++){
        if(vertexes[iter->destination_vertex].visited == WHITE){
            dfs_visits(vertexes[iter->destination_vertex]);
        }
    }
    source.visited = BLACK;
    std::cout<< source.id <<std::endl;
}

void graph::bfs(){

    for(std::vector<vertex>::iterator iter=vertexes.begin();iter != vertexes.end();iter++){
        iter->visited = WHITE;
    }

    std::queue<vertex*> bsf_q;

    bsf_q.push(&vertexes[0]);

    while(!bsf_q.empty()){
        vertex * v = bsf_q.front();
        bsf_q.pop();

        for(std::list<edge>::iterator iter = v->list.begin() ;iter != v->list.end();iter++ ){
            if(vertexes[iter->destination_vertex].visited == WHITE){
                vertexes[iter->destination_vertex].visited = GREY;
                bsf_q.push(& vertexes[iter->destination_vertex]);
            }
        }

        v->visited = BLACK;
        std::cout << v->id <<std::endl;
    }
}

Answer 1

Preliminaries

It's conventional to include system headers with brackets instead of quotes and prefer std::vector over std::list unless proven wrong by a benchmark (note that the use of the word "list" in CLRS is not used in the same sense as std::list).

#include <vector>
#include <limits>

Data structures

Separate your algorithms and data structures and use a common naming convention where types have capitalized initial letters

enum { 
    INFINITY = std::numeric_limits<int>::max() 
};

enum Color {
    WHITE,
    GREY,
    BLACK
};

struct Vertex {
    int id;

    // BFS properties
    Color color;
    int discovery;
    Vertex* parent;

    // DFS properties
    int finish;
};

// adjacenty list representation (Figure 22.1 (b) of CLRS 3rd ed.)
struct Graph {
    std::vector<Vertex> vertices;
    std::vector< std::vector<Vertex*> > adjacent;
};    

Several things can be said about my choice of data structures. For the purpose of illustrating BFS and DFS I wouldn't make them full-fledged classes with data hiding. You also need to set up some scaffolding code to initialize a Graph object, and make sure that the Vertex* inside adjacent are actually only pointing to Vertex objects inside vertices of the same Graph object (so that in fact adjacent only holds non-owning pointers). Real-world code would encapsulate the enforcement of such invariants inside the constructor and modifying member functions. For brevity this is not being show.

I also would remove the Edge class because it is implicitly represented as an Vertex* in the adjacency list graph representation. Finally, because the id in Vertex is an int, you get away with using a std::vector as a container. For std::string vertex labels, one would need to use a std::map<std::string, std::vector<Vertex*>> for the adjacent data inside Graph.

Note that the properties of BFS and DFS are put inside Vertex. This is to accomodate the style of notation of CLRS. They write on p592 that you can put that information in separate data structures as well (e.g. a std::map<Vertex*, SearchProperties>). Boost.Graph (the closest thing in C++ to a standardized graph implementation) uses such property maps to achieve the same effect more elegantly.

Breadth-first search

Document your algorithms pre- and post-conditions, as well as the runtime complexity as a function of the input size (look it up in CLRS!). I would give the function breadth_first_search the same signature as in CLRS, except that they are not very careful about whether they pass by value, reference or pointer.

#include <queue>

// pre-condition: graph of vertices with unitialized BFS properties
void breadth_first_search(Graph& g, Vertex* s)
{       
    for (auto& v: g.vertices)
        if (v.id == s->id) continue;
        v.color = WHITE;
        v.discovery = INFINITY;
        v.parent = nullptr;
    }
    s->color = GRAY;
    s->discovery = 0;
    s->parent = nullptr;    
    std::queue<Vertex*> q;
    q.push(s);    
    while (!q.empty()) {
        auto u = q.front();
        q.pop();    
        for (auto v: G.adjacent[u->id])) {
            if (v->color == WHITE) {
                v->color = GRAY;
                v->discovery = u->discovery + 1;
                v->parent = u;
                q.push(v);
            }
        }
        u->color = BLACK;
    }
}
// post-condition: graph with initialized vertex color and discovery times

Notice that I would strongly recommend to use the C++11 features auto type deduction and ranged for-loop. These enormously improve the readability of your code: the code above is in almost exactly the same notation as the listing of BFS(G,s) on p595 of CLRS (except that I use color, discovery and parent instead of the terser c, d and pi.

Except for debugging purposes, I would eliminate the std::cout calls from the BFS algorithm. Because the algorithm also keeps track of the parent information, you can completely retrace the algorithms steps after it finishes, should you want to, and print whatever information necessary.

Depth-first search

For the depth-first search, I again would follow the CLRS conventions as much as possible:

void depth_first_search(Graph& g)
{
    for (auto& u: g.vertices) {
        u.color = WHITE;
        u.parent = nullptr;
    }

    for (auto& u: g.vertices) {
        if (u.color == WHITE)
            depth_first_search_visit(g, &u, 1)
    }
}

void depth_first_search_visit(Graph& g, Vertex* u, int time)
{
    u->color = GRAY;
    u->discovery = time;
    for (auto v: g.adjacent[u->id]) {
        if (v->color == WHITE) {
            v->parent = u;
            depth_first_search_visit(G, u, time + 1)
        }
    }
    u->color = BLACK;
    u->finish = time + 1;    
}

Note that I would pass the time variable by value along the recursive calls to depth_first_search_visit, which makes it slightly clearer to reason about the algorithm (and also avoids a few explicit increments here and there). Again note that the code above is in almost exactly the same notation as the listing of DFS(G) on p604 of CLRS.

Extra: note that BFS is written as a single function with an init phase + infinite loop over a std::queue, and DFS as an init function + a recursive fuction. It is a nice exercise to rewrite DFS as a single function with an init phase + infinite loop over a std::stack (instead of the implicit stack used by the recursion).

Further reading

If you want to know how the pros are doing it: familiarize yourself with Boost.Graph.