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 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...
Objective – Given a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position. You can assume the dice you throw results in always...
We have already discussed about Graph basics. We recommend reading this before you continue to read this article. What is Weighted Graph? A Graph is called weighted graph when it has weighted edges which...
Objective: Given a Graph in which one or more vertices are disconnected, do the depth first traversal. Earlier we have seen DFS where all the vertices in graph were connected. In this article we...
Topological Sort: A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed...
Objective: Given a graph, do the depth first traversal using recursion. Earlier we have seen DFS using stack. In this article we will see how to do DFS using recursion. (Recursion also uses stack...
Earlier we had discussed in Graph Representation – Adjacency Matrix and Adjacency List about Graph and its different representations and we read Graph Implementation – Adjacency List .In this article we will implement graph...
Earlier we had discussed in Graph Representation – Adjacency Matrix and Adjacency List about Graph and its different representations. In this article we will see the better (use inbuilt class of LinkedList) way to...
