Category: Graphs


Graph – Detect Cycle in a Directed Graph

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


Graph – Software Installation Problem

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


Snake and Ladder Problem

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


Topological Sort

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


Graph – Print all paths between source and destination

Objective: Given a graph, source vertex and destination vertex. Write an algorithm to print all possible paths between source and destination. This problem also known as “Print all paths between two nodes” Example: Approach:...


Graph – Depth First Traversal

Objective – Given a graph, do the depth first traversal(DFS). What is depth-first traversal– Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the...

%d bloggers like this: