PHP 7 Data Structures and Algorithms

Revisiting BFS and DFS for graphs

We have already seen how we can implement a breadth first search (BFS) and a depth first search (DFS) in a tree structure. We will revisit our BFS and DFS for graphs. The difference between a tree implementation and a graph implementation is that in a graph implementation, we can start from any vertex, whereas we start from the root of the tree in a tree data structure. Another important thing to consider is that our graphs can have cycles, which were absent in the tree, so, we cannot revisit a node or vertex as it will end up in an infinite loop. We will use a concept called graph coloring where we keep the status of different node visits with a color or a value to keep it simple. Let's now write some code ...