## Transitive Closure of a Graph

Given a digraph G, the transitive closure is a digraph G’ such that (i, j) is an edge in G’ if there is a directed path from i to j in G. The resultant digraph G’ representation in form of adjacency matrix is called the connectivity matrix.

Read More Transitive Closure of a Graph

## Topological Sorting in a DAG

Given a directed acyclic graph (DAG), print it in Topological order. If the DAG has more than one topological ordering, print any of them.

Read More Topological Sorting in a DAG

## Bipartite Graph

Given a graph, check if given graph is bipartite graph or not. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.

## Arrival and Departure Time of Vertices in DFS

Given a graph, find arrival & departure time of its vertices in DFS. Arrival Time is the time at which the vertex was explored for the first time in the DFS and Departure Time is the time at which we have explored all the neighbors of the vertex and we are ready to backtrack.

Read More Arrival and Departure Time of Vertices in DFS

## Depth First Search (DFS) | Iterative & Recursive Implementation

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 case of a graph) and explores as far as possible along each branch before backtracking.

Read More Depth First Search (DFS) | Iterative & Recursive Implementation

## Breadth First Search (BFS) | Iterative & Recursive Implementation

Breadth first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.

## Graph Implementation in C++ without using STL

Given an undirected or a directed graph, implement the graph without using any data structure provided by any programming language library (e.g. STL in C++ or Collections in Java, etc). Implement for both weighted and unweighted graphs.

Read More Graph Implementation in C++ without using STL

## Graph Implementation using STL

Given an undirected or a directed graph, implement the graph using any data structure provided by any programming language library (e.g. STL in C++ or Collections in Java, etc). Implement for both weighted and unweighted graphs.

Read More Graph Implementation using STL

## Terminology and Representations of Graphs

This post covers basic definition in terminologies associated with graphs and covers Adjacency list and adjacency matrix graph representations of the graph.   What is a Graph? A graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes and a collection of pairs of vertices from V called edges of …

Read More Terminology and Representations of Graphs