Breadth-First-Search & Depth-First-Search

1. Breadth-First-Search
BFS(G){
for (each vertex u in V[G] - {s}) {
color[u] = WHITE;
d[u] = ∞;
Pi[u] = NULL;
}
color[s] = GRAY;
d[s] = 0;
Pi[s] = NULL;
ENQUEUE(Q, s);

While (!Q.empty()){
u = DEQUEUE(Q);
for (each vertex v in adj[u]){
color[v] = GRAY;
Pi[v] = u;
d[v] = d[u] + 1;
ENQUEUE(Q, v);
}
color[u] = BLACK;
}
}

2. Depth-First-Search
DFS(G){
for (each vertex u in V[G]){
color[u] = WHITE;
Pi[u] = NULL;
}
time = 0;
for (each vertex u in V[G]){
if (color[u] == WHITE)
DFS-VISIT(u);
}
}

DFS-VISIT(u){
color[u] = GRAY;
time ++;
d[u] = time;
for (each vertex v in adj[u]){
if (color[v] == WHITE){
Pi[v] = u;
DFS-VISIT(v);
}
}
time++;
f[u] = time;
color[u] = BLACK;
}