Check whether a directed graph is Eulerian
An Eulerian trail (or Eulerian path) is a path in a graph that visits every edge exactly once. Given a directed graph, check whether it has an Eulerian path or not.
Category: Graph
Find itinerary from the given list of departure and arrival airports
Given a list of departure and arrival airports, find the itinerary in order. It may be assumed that departure is scheduled from every airport except the final destination, and each airport is visited only once.
Check if a set of words can be rearranged to form a circle
Given a set of words, check if the individual words can be rearranged to form a circle. Two words, X and Y, can be put together in a circle if the last character of X is the same as the first character of Y or vice-versa.
Find root vertex of a graph
A root vertex of a directed graph is a vertex u with a directed path from u to v for every pair of vertices (u, v) in the graph. In other words, all other vertices in the graph can be reached from the root vertex.
Eulerian cycle in directed graphs
Given a directed graph, check if it is possible to construct a cycle that visits each edge exactly once, i.e., check whether the graph has an Eulerian cycle or not.
Check whether an undirected graph is Eulerian
Given an undirected graph, check whether it has an Eulerian path or not. In other words, check if it is possible to construct a path that visits each edge exactly once.
Find the longest path in a Directed Acyclic Graph (DAG)
Given a directed acyclic graph (DAG) and a source vertex, find the cost of the longest path from the source vertex to all other vertices present in the graph. If the vertex can’t be reached from the given source vertex, print its distance as infinity.
Construct a directed graph from an undirected graph that satisfies given constraints
Given a connected undirected graph and a vertex in the graph, construct a directed graph such that any path in the directed graph leads to that particular vertex.
Find all Possible Topological Orderings of a DAG
Given a Directed Acyclic Graph (DAG), print all its topological orderings. A Topological ordering of a directed graph G is a linear ordering of the nodes as v1, v2,…,vn such that all edges point forward: for every edge (vi, vj), we have i < j.
Depth-First Search (DFS) vs Breadth-First Search (BFS)
This post will cover the difference between the Depth–first search (DFS) and Breadth–first search (BFS) algorithm used to traverse/search tree or graph data structure.
Find 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 a path exists from the source vertex to the destination vertex, print it.