A graph is a non-linear data structure consisting of nodes (vertices) and edges that connect these nodes. It represents a set of objects (nodes) and the relationships between them (edges). Graphs are used to model various real-world scenarios, such as social networks, transportation networks, and communication networks.
Graph traversal algorithms are like explorers systematically navigating a complex network of interconnected nodes. They provide a structured approach to visit every reachable node and edge, ensuring no part of the graph is overlooked. This methodical exploration is fundamental for understanding the graph's structure, identifying patterns, and solving problems that involve relationships between nodes, such as finding the shortest path, detecting cycles, or determining connectivity.
Visually a graph traversal is typically drawn as a decision tree, as shown below:
.
| Traversal Type | Description |
|---|---|
| Depth-First Search (DFS) | Explores as far as possible along each branch before backtracking. |
| Breadth-First Search (BFS) | Explores all neighbors at the present depth prior to moving on to nodes at the next depth level. |
In this algorithm, we follow one path as far as it will go. The algorithm starts in an arbitrary node, called the root node, and explores as far as possible along each branch before backtracking.
The algorithm can also be applied to directed graphs. DFS is implemented with a recursive algorithm and its temporal complexity is O(E+V).
The DFS Algorithm starts at the root (top) node of a tree and goes as far as it can down a given branch (path), then backtracks until it finds an unexplored path, and then explores it. The algorithm does this until the entire graph has been explored.
In the example shown below, the root node would be node “0”; we traverse in depth through node “1”, followed by node “3”. Once we reach the node, we move one level up to node “1” and traverse through all other connected nodes, in this case, node “4”. Once we have covered all connected nodes, we move again one level up, to node “0” and traverse all other connected nodes, in this case, node “2”. As we traverse through deeper nodes, we traverse through nodes “5” and “6”, covering all connected nodes.
The BFS algorithm involves pulling out the first element from the queue, checking for a path, and determining if it is the destination node. If not, all children nodes are added to the queue. This process continues by examining all adjacent nodes before moving to the next level.
The algorithm can also be applied to directed graphs. The time complexity is O(E+V).
The BFS algorithm begins by searching a start node, followed by its adjacent nodes, and then all nodes reachable by paths containing two edges, three edges, and so forth.
In the example below, the root node is node “0”; we traverse width-wise through node “1”, followed by node “2”. After traversing all nodes in the first depth level, we proceed to the second depth level, starting with node “3”, and moving through nodes “4”, “5”, and “6”.
Let us consider a graph to understand the adjacency list and adjacency matrix representation. Let the undirected graph be:
The adjacency matrix representation of a graph is depicted as follows:
The following image represents the adjacency matrix representation:
Definition: In the adjacency list representation, a graph is represented as an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the vertices that form an edge with the vertex.
Visual Representation: The following image represents the adjacency list representation:
A topological sort is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before vertex v in the ordering. In simpler terms, it's a way to order tasks or events where one task must be completed before another can start.
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u-v, vertex u comes before v in the ordering.
Note: Topological Sorting for a graph is not possible if the graph is not a DAG.
Example: Input: Graph:
The first vertex in topological sorting is always a vertex with an in-degree of 0 (a vertex with no incoming edges). A topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. Another topological sorting of the following graph is “4 5 2 3 1 0”.
Warshall's Algorithm: A dynamic programming algorithm used to find the transitive closure of a directed graph.
In simpler terms, it determines whether there exists a path between every pair of vertices in the graph. It efficiently calculates the reachability matrix, which indicates whether a vertex can be reached from another vertex in the graph.
Dijkstra's Algorithm: A greedy algorithm used to find the shortest path between a source node and all other nodes in a weighted graph.
It works by iteratively selecting the unvisited node with the smallest tentative distance from the source node, and then updating the distances of its neighbors. This process continues until all nodes have been visited.
Prim's Algorithm: A greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph.
It starts with an initial vertex and iteratively adds the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST. This process continues until all vertices are included in the MST.
Kruskal's Algorithm: Another greedy algorithm used to find the MST of a connected, weighted, undirected graph.
It sorts all edges in non-decreasing order of their weight and iteratively adds the edge with the minimum weight that doesn't create a cycle in the MST. This process continues until all vertices are connected.
A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected, undirected graph is a spanning tree with a weight less than or equal to the weight of every other spanning tree.
To learn more about Minimum Spanning Tree, refer to this article.
Here we will discuss Kruskal’s algorithm to find the MST of a given weighted graph.
In Kruskal’s algorithm, sort all edges of the given graph in increasing order. Then it keeps on adding new edges and nodes in the MST if the newly added edge does not form a cycle.
It picks the minimum weighted edge at first and the maximum weighted edge at last. Thus we can say that it makes a locally optimal choice in each step in order to find the optimal solution. Hence this is a Greedy Algorithm.
Step 2 uses the Union-Find algorithm to detect cycles.
So we recommend reading the following post as a prerequisite:
Kruskal’s algorithm to find the minimum cost spanning tree uses the greedy approach. The Greedy Choice is to pick the smallest weight edge that does not cause a cycle in the MST constructed so far.
Below is the illustration of the above approach:
Input Graph:
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having (9 – 1) = 8 edges.
| Weight | Source | Destination |
|---|---|---|
| 1 | 7 | 6 |
| 2 | 8 | 2 |
| 2 | 6 | 5 |
| 4 | 0 | 1 |
| 4 | 2 | 5 |
| 6 | 8 | 6 |
| 7 | 2 | 3 |
| 7 | 7 | 8 |
| 8 | 0 | 7 |
| 8 | 1 | 2 |
| 9 | 3 | 4 |
| 10 | 5 | 4 |
| 11 | 1 | 7 |
| 14 | 3 | 5 |
Pick edge 7-6. No cycle is formed, include it.
Add Edge 7-6 in the MST
Note: Since the number of edges included in the MST equals to (V – 1), so the algorithm stops here.
Like Kruskal’s algorithm, Prim’s algorithm is also a Greedy algorithm. This algorithm always starts with a single node and moves through several adjacent nodes, in order to explore all of the connected edges along the way.
The algorithm starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, and the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.
A group of edges that connects two sets of vertices in a graph is called cut in graph theory. So, at every step of Prim’s algorithm, find a cut, pick the minimum weight edge from the cut, and include this vertex in MST Set (the set that contains already included vertices).
The working of Prim’s algorithm can be described by using the following steps:
Note: For determining a cycle, we can divide the vertices into two sets [one set contains the vertices included in MST and the other contains the fringe vertices.]
Consider the following graph as an example for which we need to find the Minimum Spanning Tree (MST).
Step 1: Firstly, we select an arbitrary vertex that acts as the starting vertex of the Minimum Spanning Tree. Here we have selected vertex 0 as the starting vertex.
Step 2: All the edges connecting the incomplete MST and other vertices are the edges {0, 1} and {0, 7}. Between these two the edge with minimum weight is {0, 1}. So include the edge and vertex 1 in the MST.
Step 3: The edges connecting the incomplete MST to other vertices are {0, 7}, {1, 7} and {1, 2}. Among these edges the minimum weight is 8 which is of the edges {0, 7} and {1, 2}. Let us here include the edge {0, 7} and the vertex 7 in the MST. [We could have also included edge {1, 2} and vertex 2 in the MST].
Step 4: The edges that connect the incomplete MST with the fringe vertices are {1, 2}, {7, 6} and {7, 8}. Add the edge {7, 6} and the vertex 6 in the MST as it has the least weight (i.e., 1).
Step 5: The connecting edges now are {7, 8}, {1, 2}, {6, 8} and {6, 5}. Include edge {6, 5} and vertex 5 in the MST as the edge has the minimum weight (i.e., 2) among them.
Step 6: Among the current connecting edges, the edge {5, 2} has the minimum weight. So include that edge and the vertex 2 in the MST.
Step 7: The connecting edges between the incomplete MST and the other edges are {2, 8}, {2, 3}, {5, 3} and {5, 4}. The edge with minimum weight is edge {2, 8} which has weight 2. So include this edge and the vertex 8 in the MST.
Step 8: See here that the edges {7, 8} and {2, 3} both have same weight which are minimum. But 7 is already part of MST. So we will consider the edge {2, 3} and include that edge and vertex 3 in the MST.
Step 9: Only the vertex 4 remains to be included. The minimum weighted edge from the incomplete MST to 4 is {3, 4}.
The final structure of the MST is as follows and the weight of the edges of the MST is (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37.
Note: If we had selected the edge {1, 2} in the third step then the MST would look like the following.
Given a weighted graph and a source vertex in the graph, find the shortest paths from the source to all the other vertices in the given graph.
Note: The given graph does not contain any negative edge.
Input: src = 0, the graph is shown below.
Output: 0 4 12 19 21 11 9 8 14
Explanation: The distance from 0 to 1 = 4. The minimum distance from 0 to 2 = 12. 0->1->2 The minimum distance from 0 to 3 = 19. 0->1->2->3 The minimum distance from 0 to 4 = 21. 0->7->6->5->4 The minimum distance from 0 to 5 = 11. 0->7->6->5 The minimum distance from 0 to 6 = 9. 0->7->6 The minimum distance from 0 to 7 = 8. 0->7 The minimum distance from 0 to 8 = 14. 0->1->2->8
The idea is to generate a SPT (shortest path tree) with a given source as a root. Maintain an Adjacency Matrix with two sets,
At every step of the algorithm, find a vertex that is in the other set (set not yet included) and has a minimum distance from the source.
Note: We use a boolean array sptSet[] to represent the set of vertices included in SPT. If a value sptSet[v] is true, then vertex v is included in SPT, otherwise not. Array dist[] is used to store the shortest distance values of all vertices.
To understand the Dijkstra’s Algorithm lets take a graph and find the shortest path from source to all nodes.
Consider below graph and src = 0
The following subgraph shows vertices and their distance values, only the vertices with finite distance values are shown. The vertices included in SPT are shown in green colour.
We repeat the above steps until sptSet includes all vertices of the given graph. Finally, we get the following Shortest Path Tree (SPT).
Given a directed graph, determine if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable means that there is a path from vertex i to j. The reachability matrix is called the transitive closure of a graph.
For example, consider below graph
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 1
The graph is given in the form of adjacency matrix say ‘graph[V][V]’ where graph[i][j] is 1 if there is an edge from vertex i to vertex j or i is equal to j, otherwise graph[i][j] is 0.
Floyd Warshall Algorithm can be used, we can calculate the distance matrix dist[V][V] using Floyd Warshall, if dist[i][j] is infinite, then j is not reachable from i. Otherwise, j is reachable and the value of dist[i][j] will be less than V.
Instead of directly using Floyd Warshall, we can optimize it in terms of space and time, for this particular problem. Following are the optimizations:
Percentage: 0%
Answered Questions: 0
Correct Answers: 0