I. Breadth-first search, starting at node B
Given:
- A graph G = (V, E), where the vertices in V have integer IDs
- An empty queue Q of vertex IDs
- An empty list L of edges
- A function Visit(vertex) that does whatever it is your program needs
The algorithm:
B.visited = true
Visit(B)
Q.enqueue(B)
while (Q is not empty) {
V = Q.dequeue()
for each unvisited neighbor W of V
(in increasing numerical order)
{
W.visited = true
Visit(W)
Q.enqueue(W)
L.add((V, W))
}
}
II. Depth-first search, starting at node B
Given:
- A graph G = (V, E), where the vertices in V have integer IDs
- An empty stack S of vertex IDs
- An empty list L of edges
- A function Visit(vertex) that does whatever it is your program needs
to do when it first encounters a vertex during this traversal.
The algorithm:
B.visited = true
Visit(B)
Push B onto S
while (S is not empty) {
V = S.peek()
if (V has any unvisited neighbors) {
Let W be the unvisited neighbor of V with
the smallest ID
W.visited = true
Visit(W)
S.push(W)
L.add((V, W))
} else {
S.pop()
}
}