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.
Given a dictionary of ancient origin where the words are arranged alphabetically, find the correct order of alphabets in the ancient language.
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.
Given a weighted digraph (Directed Graph), find the least cost path from given source to destination that have exactly m edges.
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.
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.
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.
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.
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.
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.
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.