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

Weighted Graph Implementation – JAVA

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

Graph – Depth First Search in Disconnected Graph

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

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 – Depth First Search using Recursion

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

Graph Implementation – Adjacency Matrix | Set 3

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

Graph Implementation – Adjacency List – Better| Set 2

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

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

Breadth-First Search/Traversal in a Graph.

Breadth-First Search ( or Tra­ver­sal)  in a Graph is quite similar to Binary Tree. Click here to read about BFS in Binary Tree. Example: What is Breadth First Search: Breadth-first search (BFS) is an...

Graph Representation – Adjacency Matrix and Adjacency List

What is Graph: G = (V,E) Graph is a collection of nodes or vertices (V) and edges(E) between them. We can traverse these nodes using the edges. These edges might be weighted or non-weighted....