To search in a graph, we first build a tree covering the graph.
Breadth first search
BFS browse by increasing depth to the root.
BFS(Graph G, Node s):
{
f = CreateQueue();
f.stack(s);
mark(s);
while non f.empty()
s = f.pop();
print(s);
for each children t of s in G
if t unmarked DO
f.stack(t);
mark(t);
end if
end for
end while
}
In-depth search : pre-order
In-depth algorithms are recursive. In the prefix path, we always browse the left subtree before processing the right subtree.
- Check if the current node is empty or null.
- Display the data part of the root (or current node).
- Traverse the left subtree by recursively calling the pre-order function.
- Traverse the right subtree by recursively calling the pre-order function.
In-depth search : in-order
The LNR browse as far left as possible, and display the branches from left to right. This algorithm display the diagonals from bottom to top.
- Check if the current node is empty or null.
- Traverse the left subtree by recursively calling the in-order function.
- Display the data part of the root (or current node).
- Traverse the right subtree by recursively calling the in-order function.
In-depth search : out-order
This is a diagonal browsing from top to bottom.
- Check if the current node is empty or null.
- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Display the data part of the root (or current node).
