Applications of Breadth First Search and Depth First Search

In the previous post(Graph and its implementation, BFS of a graph and DFS of a graph) we understand the logic and the implementation of the Graph traversal. Now we look forward and see the application and needs of the BFS/DFS. Application of the Breadth-First-Search Connected Components of a given Graph …

Read moreApplications of Breadth First Search and Depth First Search

Subarray Sum Equals k

Given an integer array and an integer k. Find total number of contiguous subarrays of given array whose sum of elements is equal to k. Example Input 1: arr[] = {5,0,5,10,3,2,-15,4} k = 5 Output: 7 Input 2: arr[] = {1,1,1,2,4,-2} k = 2 Output: 4 Explanation : consider example-1 …

Read moreSubarray Sum Equals k

Topological Sorting

Given a directed acyclic graph, topologically sort the graph nodes. Topological Sorting Example Topological sorting of above graph is -> {1,2,3,0,5,4} Theory Topological Sorting is done for a Directed Acyclic Graph (DAG). A DAG has no cycles in it. ie, there is no such path starting from any node of …

Read moreTopological Sorting

Graph and its representation

A graph is an abstract data type representing relations or connections between objects(like cities are connected by rough road). In the graph and its representation, basically, the relation is denoted by edges and objects by vertices(nodes). A graph consists of a finite set of vertices and edges. A graph is …

Read moreGraph and its representation