Explain various graph traversal techniques.

258views

written 8.5 years ago by

teamques10 ★ 68k

Breadth-First Search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.
BFS exhaustively searches the entire graph or sequence without considering the goal until it finds it.
All child nodes obtained by expanding a node are added to a FIFO (i.e., First In, First Out) queue. In typical implementations, nodes that have not yet been examined for their neighbors are placed in either a queue or a linked list..
An informal algorithm would be, “If the element sought is found in this node, quit the search and return a result. Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered, until there are no undisconverd nodes left.”.

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.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
DFS will process the vertices first deep and then wide. After processing a vertex it recursively processes all its descendants. A stack is maintained.

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.
Here is an example:-

BFS will visit the nodes in the following order: A, B, C, E, D, F, G.
DFS will visit the nodes in the following order: A, B, D, F, E, C, G.

ADD COMMENT EDIT