People always try to find out a way to keep the order of their things. And to achieve this they keep on playing with different data structures until they find the best one. In this blog, we will be talking of one such data structure namely Graph.
It is a non-linear data structure consisting of some nodes (or vertices) and edges (or links) between the nodes. In practical life; graphs are used to model many types of relations or networks of communication.
Graph Representation
To represent a graph we can use either adjacency list of the adjacency matrix. Graphs can be directed or undirected. Undirected graphs have bi-directional edges which mean that if there exists an edge from node A to B then traversing either from A to B and vice versa is possible. Directed Graphs have directional edges which mean if there exists an edge from node A to B then vice versa movement is not allowed.
Nodes in graph can be of two types root or leaf nodes. Root node is the start point in a graph and leaf node is basically a node that has no more child nodes. Leaf nodes do not have any outgoing edges.
Depth First Search (DFS): It is one of the main graph traversal algorithms. The main idea of DFS traversal is to go as deep as possible and backtrack one we reach a vertex that has all its adjacent vertices already visited. Recursive implementation of the technique is very easy. We start at the source vertex and explores all its adjacent neighbours and further recursively call the function for the vertex if not visited. To keep track of nodes as visited or not we also keep a bool visited array initialised to false values. A snippet of the algorithm (in C++ for 1000 nodes) can be found below.
As already mentioned this is a recursive implementation of DFS traversal. In iterative implementation we maintain a stack and push the adjacent child nodes of a node onto the stack and iterate while stack is not empty. Before pushing the child node we also check if the node is visited or not. Time Complexity of the recursive and iterative code is O (V+E), where V is no of vertices and E is the no of edges. Space Complexity is O (V) as we have used visited array.
DFS traversal techniques can be very useful while dealing with graph problems. Let me also mention that DFS will also return the shortest path in a tree (true only in case of trees as there exist only one path). A tree is a special case of a graph where the count of connected components is one and there are no cycles. The following image shows working of DFS. Here consider start node as node 1 and for keeping track of visited or not, consider node coloured in blue visited and node coloured in orange as not visited.
We start at node 1 and explore its neighbours 2 and 3.We can visit any node first. We now move to node 2 and explore its neighbours and once we reach a node with no more unvisited nodes we backtrack.
Application of DFS
- Find a path from the source vertex to other vertices
- Find the connected components in a graph
- Topological Sorting
- Find bridges and articulation points in a graph
- Find LCA of two nodes in a graph
- Find cycles in a directed and undirected graph
Breadth-First Search (BFS): It is a traversing algorithm where you should start traversing from a start node and traverse the graphs layer-wise. In the case of a tree, this is the level order traversal. The above image depicts the working of BFS. As stated earlier, in BFS we first visit all the nodes of the current layer and then traverse nodes in the next layer. BFS implementation is also easier and we use a queue data structure to keep track of nodes in the current label. An important point about this traversal technique is that it traverses the shortest path (the path that contains the smallest number of edges) in an unweighted graph. To find the smallest path in a weighted graph we have Dijkstra’s Algorithm. Also in case, the weight is either 0 or 1 we can use 0/1 BFS. In 0/1 BFS we use a doubly ended queue.
A snippet of the iterative approach in BFS is shown below:
Here we push the source node on the queue and start exploring its non visited child nodes level wise and push the non visited child nodes onto the queue. The time complexity of this technique is also O (V+E), where V is the number of vertices and E is the edges in the graph.
Applications of BFS
- Finding the Shortest path in an unweighted graph
- Find a solution to a game with the least number of moves. In such a scenario each state of the game can be represented by a node and state transitions as edges
- Finding Connected Components in an unweighted graph
- Level Order Traversal in Tree
- Find the shortest paths in graphs with weights 0/1
Let us try applying the concept of BFS and DFS on 2D grids. In case of 2D grids we consider every cell as a node and edges are generally mentioned in the question but for in general sides are considered as edges and two cells are said to be connected if they share aside. In some cases, it is also mentioned that sides + corners are edges.
DFS and BFS ON 2D GRID
Let us consider a 2D grid of some dimension and let us assume we are currently at cell (x, y). Now from the current cell we have 4 directions to move namely up, down, left and right (considering sides as edges only). Now in DFS we start exploring the adjacent vertices and mark these vertices as visited. So more or less in cases of 2D grids as well we apply the same logic as for graphs. Before we look at code for DFS, let us understand an important point as which cells are valid in our grid. Obviously, we need to care about boundary conditions. Hence those cells that are on the boundary and not visited are valid cells. Now let us look at the code snippet for the validity of a cell first and then for DFS.
A good practice of implementing DFS or BFS would be to keep an array for directions and then looping in all directions. Similar is the theory of BFS on Graphs and 2D Grids. Below is the snippet of direction vectors and BFS traversal using this direction vector.
BFS can be used to find the shortest path in a 2D grid and DFS can be used to find connected components in a 2D grid. In case of an edge is corners + sides (which will be mentioned in the question) then make sure to traverse in eight directions.
To explore more about data structures, click here.
By Mridul Kumar
