GRAPH TRAVERSAL TECHNIQUES
Introduction
To solve problems on graphs, we need a mechanism for traversing the graphs. Graph traversal algorithms are also called graph search algorithms.
Like tree traversal algorithms (Inorder, Preorder, Postorder and Level-Order traversals), graph traversal algorithms can be thought of as starting at some source vertex in a graph and "searching/traversing" the graph by going through the edges and marking the vertices.
Note:
- We will be using 2D arrays(adjacency matrix) for implementing graph.
- We shall implement an undirected graph.
- Make a point that the order of traversing actually can be anything like ascending or descending or random, but will stick to traverse each node in ascending order.
- The output for DFS & BFS will differ because it depends on what vertex you start with and in what order you traverse them.
Now, we will discuss two algorithms for traversing the graphs.
Breadth First Search(BFS)
The BFS algorithm for graphs works similar to BFS algorithm for trees. Like BFS traversal of trees, internally this algorithm also uses queue. First create a new array called isVisited[] which tracks whether a node is visited or not.
Initially we can start from any vertex but for convenience will start with 0. Print this node, set it as visited and explore this currently visited node i.e 0. (Exploring means if there is node adjacent to 0 then add them in the queue in ascending order).
Now move to the next element in the queue by dequeuing the front element and explore them as they come in order(queue). Stop when all the nodes are visited.
Applications: Finding all connected components in a graph, finding all nodes within one connected component, finding the shortest path between two nodes, testing a graph for bi-partiteness.
Depth First Search(DFS)
The DFS algorithm for graphs works similar to pre order(type of DFS) algorithm for trees. Like pre order traversal, internally this algorithm also uses stack. First create a new array called isVisited[] which tracks whether a node is visited or not.
Initially we can start from any vertex but for convenience will start with 0. Print this node, set it as visited and visit next adjacent node.
Follow the above procedure until you reach a deadend. Deadend means, you are just traversing in one way(not exploring), diving deeper by deeper as you traverse each node and going to the depth of the graph. So you come across a node whose adjacent nodes are already visited.
After you reach this deadend, start backtracking. For this operation will have to use stack but as we are using recursion, we shall not worry about using stacks.
While backtracking, if you find any node's adjacent node is unvisited, then traverse to that node and go further deep.
Applications: Topological sorting, finding articulation points (cut vertices) of the graph, finding strongly connected components, solving puzzles such as mazes.
Insertion
-
Adding vertices:
Adding a vertex will be performed by incrementing the total
no. of vertices(V). The initial value of V will be -1 and when
you add one vertex, this V gets incremented and the
incremented value is treated as the value of new node.
Suppose you add one vertex when V=-1. Now V gets incremented to 0. So the new vertex is 0. - Adding edges: Take two vertices as two inputs and set the value of this inputs as 1 in the adjacency matrix.
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for GRAPH TRAVERSAL TECHNIQUESThat's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!