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.