Graph Traversals
Graph is a form of data structure consisting of two parts:
1. Set of finite vertices called nodes.
2. The edges between those vertices. They can be either directed or undirected. The notation (u,v) denotes the presence of an edge between vertex u and vertex v. If the graph is directed, then the order of the pair matters.
In graph data structure there is the concept of traversing a graph which is commonly known as graph traversal. Graph traversal is nothing but checking/visiting each vertex in a graph.
There are two types of graph traversals:
1. Breadth First Search/Traversal
2. Depth First Search/Traversal
For these traversals we need to know these two terms:
1. Visiting a vertex — Simply meaning going on a particular vertex.
2. Exploration of a vertex — Visiting all the adjacent vertex of a particular vertex is called exploration of the vertex.
So now that we know these two terms, let us understand the working of Breadth-First Search (BFS).
Let’s take this graph as an example to demonstrate BFS. We can select any vertex as the starting vertex. Suppose we selected vertex s as the starting vertex, we add that vertex to a queue.
Once the vertex is visited, we will start exploring it i.e., we will visit all its adjacent vertices and all the adjacent nodes to the queue (We can visit them in any order).
Once we finish exploring all the adjacent vertices of 1, we will select the next vertex which will be decided by the queue. Select the next vertex from the queue which is 2 in this case and start repeating the same procedure until all the nodes in the graph are visited.
This is the basic working of Breadth-First Search/Traversal in an undirected graph.
Pseudo Code of BFS:
Next, we will understand the working of Depth-First Search (DFS)
In DFS, we use stack instead of a queue.
Suppose we take the following graph and use DFS. Just like BFS we can use any vertex as the starting vertex. Let’s take u as the starting vertex.
Once the vertex u is visited, we add it to the stack then we start exploring it. We visit vertex t, now here lies the difference between BFS and DFS because instead of visiting other adjacent vertices we start exploring it.
Now, we start exploring vertex t and visit vertex w but again this time we will not visit other adjacent vertices instead we will explore vertex w. This way we will reach vertex v.
The stack at this point will look something like this
When we start exploring vertex v, we will find that there is no other vertex to visit so we remove vertex v from the stack and go back to vertex r. Again, we see that there is no other vertex to be explored so we also remove it from the stack. Repeating this procedure will make us arrive at vertex t. Here vertex t can be further explored so we visit x.
The stack at this point will be like this
Repeat the same steps and we will visit all the vertices in the graph.
This is the basic working of Depth-First Search/Traversal in an undirected graph.
Code Implementation of DFS:
Time Complexity = O(V+E)
V=Number of vertices
E=Number of edges
Interesting Facts about DFS and BFS
- BFS is just like level order in a binary tree
- DFS is just like pre order traversal of a tree
Applications of BFS
· BFS is used to locate all neighbour nodes in a peer-to-peer network such as BitTorrent.
· BFS indexes are built using search engine crawlers. It finds all links in the original page to get new pages, starting with the source page.
· BFS uses a GPS navigation system to locate nearby locations.
· The BFS algorithm is used in networking when we wish to broadcast some packets.
· The Ford-Fulkerson algorithm uses BFS to find the maximum flow in a network.
Applications of DFS
· When we use DFS on an unweighted graph, we get the shortest path tree with the least spanning tree.
· DFS can be used to find cycles in a graph. There must be one cycle if we only get one back-edge during BFS.
· We can use DFS to find a path between two vertices u and v.
· We can do topological sorting, which is utilised to schedule jobs based on work dependencies. The DFS algorithm can be used to perform topological sorting.
Hope this was helpful!