0
9.0kviews
Explain various graph traversal techniques.
1 Answer
written 8.4 years ago by |
The algorithm of BFS is given below:-
Start.
Enqueue the root node. Dequeue a node and examine it.
If it is the element to be found, return a value. Else enqueue the direct child nodes that have not been visited.
If the queue is empty, return a negative value to indicate element wasn’t found. Else go to the previous step.
Stop.
The worst-case time complexity of BFS is O( | E | + | V | ), since every vertex and every edge will be explored in the worst case.
The algorithm of DFS is given below:-
Start.
Push the root node.
Pop a node and examine it. If it is the element to be found, return a value. Else push a direct child node that has not been visited.
If the stack is empty, return a negative value to indicate element wasn’t found. Else go to the previous step.
Stop.
The worst-case time complexity of DFS is O( | E | + | V | ), since each node is visited only once and in the case of a tree (no cycles) all the edges are crossed once.