A minimum spanning tree(MST) is a subset of a graph which connects all the vertices with minimum total edge weight and least number of edges(no cycles). Formally a MST has following properties: Subset of the graph. Contains all vertices of the graph. Every vertex is reachable from all other vertices. Contains no cycles. Minimum total edge weight among all spanning tree. The last point is the defining property of an MST....
The Time Complexity for DFS and BFS is O(V+E). We all know that. But what does V+E is actually mean ? Ever noticed Dijkstra also has this V+E in its time complexity = O((V+E)logV). Ever wondered why ? Understanding DFS and BFS Depth First Search and Breadth First Search are two graph traversal algorithms. While DFS explores the graph recursively, BFS explores the graph level by level. Let’s see the two algorithms:...
Dijkstra is a Greedy algorithm to find the shortest path in a graph from a single source. Let’s take a weighted a graph as below: We’ll take 0 as the source. Shortest path from source 0 to node 4 will go through node 1 and node 3: Similarly we’ve to find the shortest path from the source 0 to every node. How does Dijkstra finds this ? Understanding Dijkstra Dijkstra like any other Greedy algorithm finds the next most optimum path at each step....
A Binary Search Tree or a BST is a tree whose inorder traversal is sorted. For each node in a BST the left subtree has values smaller the node’s value and the right subtree has values greater than the node’s value. Search in a BST Since in a BST the values lesser than the current node lies in the left subtree and greater values lies in the right subtree. We can use this property to search for a value....
Cheatsheet for Time Complexities of DSA and Graphs