What is a Spanning Tree? In an undirected and connected graph G=(V,E), a spanning tree is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. A graph...
Earlier we have seen the implementation of prim’s algorithm using priority queue with decrease key and how decrease key has increased the time complexity. In this article we will improve the implementation(without decrease key)...
Earlier we have seen what is Prim’s algorithm is and how it works. In this article we will see its implementation using adjacency list and Priority Queue. We strongly recommend to read – prim’s...
Earlier we have seen what is Prim’s algorithm is and how it works. In this article we will see its implementation using adjacency list and Min Heap. We strongly recommend to read – prim’s...
Earlier we have seen what is Prim’s algorithm is and how it works. In this article we will see its implementation using adjacency matrix. We strongly recommend to read – prim’s algorithm and how...
What is Prim’s algorithm? Prim’s algorithm is a greedy algorithm. It finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all...
Objective: Given a graph, check if the graph contains a cycle using disjoint set. Note: Disjoint-set data structure, also called a union–find data structure or merge–find set. Example: Earlier in Detect Cycle in Undirected Graph using DFS we...
Earlier we have seen the complete implementation of Disjoint Set. We strongly recommend reading this before continue. Disjoint Set operations – MakeSet(x) Find(x) Union(x,y) Click here to read about these operations in detail. How...
What is Disjoint-set data structure? Represents a mathematics concept Set. A disjoint-set data structure, also called a union–find data structure or merge–find set. A disjoint-set data structure that keeps track of a set of elements partitioned into a number of disjoint or non-overlapping subsets. It...
Objective: Given a graph, source vertex and destination vertex. Write an algorithm to count all possible paths between source and destination. Condition: Graph does not contain any cycle. This problem also known as “paths...
Objective: Given undirected graph write an algorithm to count the number of non reachable vertices from a given vertex Example: Approach: Use DFS Do the DFS (Depth-First Search) from the given vertex A, Recursively...
Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back...
Objective: Given undirected graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Earlier we have seen how to find cycles in directed graphs. In this article we will...
Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back...
Objective: Given a list of software’s which you need to install in a computer. Few software’s has dependency on other software’s in the list, means these software can be installed only when all of...
