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....