Graphs are undoubtedly one of the most important data structures we’ll use in real life. From building games to finding applications in social media apps like Instagram and LinkedIn, graphs are terrifically omni-present. Graphs are non-linear data structures, that can be traversed in more than one ways. This ‘more-than-one-ways’ traversal has often confused code newbies to find which one is the correct method, and like democracy, all(here, both) ways are correct.
Breadth first traversal, as the name suggests, is traversing the graph breadthwise — along it’s breadth.
In the above graph (since all trees are graphs) , let us discuss our approach to Breadth-First-Search traversal.
Step1: Start from any node. For our convenience, let us start from 1.
Step 2: Write down all the adjacent nodes of 1 : 1 ,2 ,5 ,4
Step 3: Write down all the adjacent nodes of 2,5,4: 1,2,5,4,6,7,3 (5 and 4 do not have any adjacent nodes).
Step 4: Write down all adjacent nodes of 6,7,3: 1,2,5,4,6,7,3,8 (6 and 7 do not have any adjacent node).
Therefore, in breadth-first traversal, we first explore the breadth of graph and then delve deeper into it’s depth nodes.
Depth-First-Search traversal can be done in the following way:
Step 1: Start from any node. For our convenience, let us start from 1.
Step 2: As soon as you write any node beside 1, forget about 1 and start writing the next adjacent node to the new adjacent node. If you write 2 beside 1, the next step should be 1, 2 , (the next adjacent node to 2).
Step 3: Let us say we write 3 next to 2. Now, forget about 2 and 1 and write the next adjacent node to 3. Your traversal should look like: 1,2,3,8 (since 8 is adjacent to 3).
Step 4: Having no new node to hop on to, come back to 2 and write the other adjacent node: 1,2,3,8,6. If there was some node adjacent to 6, we would write that first. However, as of now, the traversal will be: 1,2,3,8,6,7,4,5 (same process for 1’s remaining adjacent nodes).
Therefore, in depth-first traversal, we first explore the depth of graph and then delve deeper into it’s adjacent nodes.
