## Depth first search (DFS) vs Breadth first search (BFS)

In this post, we will see the difference between Depth first search (DFS) and Breadth first search (BFS) algorithm which are used to traverse/search tree or graph data structure.

## Find the correct order of alphabets in a given dictionary of ancient origin

Given a dictionary of ancient origin where the words are arranged alphabetically, find the correct order of alphabets in the ancient language.

## Find the path between given vertices in a directed graph

Given a directed graph and two vertices (say source and destination vertex), determine if the destination vertex is reachable from the source vertex or not. If the path exists from the source vertex to the destination vertex, print it.

## Least cost path in given digraph from given source to destination having exactly m edges

Given a weighted digraph (Directed Graph), find the least cost path from given source to destination that have exactly m edges.

## Find maximum cost path in graph from given source to destination

Given a weighted graph, find the maximum cost path from given source to destination that is greater than a given integer x. The path should not contain any cycles.

## Determine negative-weight cycle in a graph

Given a directed weighted graph, report a negative-weight cycle in the graph if any. A negative-weight cycle is a cycle in graph whose edges sum to a negative value.

## Kahn’s Topological Sort Algorithm

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

## Find Cost of Shortest Path in DAG using one pass of Bellman-Ford

Given a directed acyclic graph (DAG) and a source vertex, find the cost of shortest path from source vertex to all other vertices present in the graph. If vertex can’t be reached from given source vertex, print its distance as infinity.

## Least Cost Path in Weighted Digraph using BFS

Consider a directed graph where weight of its edges can be one of x, 2x or 3x (x is a given integer), compute the least cost path from source to destination efficiently.

## Determine if a graph is Bipartite Graph using DFS

Given a graph, determine if given graph is bipartite graph using DFS. 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.

## Check if Graph is Strongly Connected or not using one DFS Traversal

Given a directed graph, check if it is strongly connected or not. A directed graphs is said to be strongly connected if every vertex is reachable from every other vertex.

## Print all k-colorable configurations of the graph (Vertex coloring of graph)

Given a graph, find if it is k-colorable or not and print all possible configuration of assignment of colors to its vertices.