Total paths in a digraph from a given source to a destination having exactly `m` edges
Given a digraph (directed graph), find the total number of routes to reach the destination from a given source with exactly m
edges.
Ace your Coding Interview
Get hired by top tech companies with our comprehensive interview preparation.
Get StartedGiven a digraph (directed graph), find the total number of routes to reach the destination from a given source with exactly m
edges.
Given a connected undirected graph, find if it contains any cycle or not. For example, the following graph contains a cycle 2–5–10–6–2
.
The transitive closure for a digraph G
is a digraph G’
with an edge (i, j)
corresponding to each directed path from i
to j
in G
. The resultant digraph G’
representation in the form of the adjacency matrix is called the connectivity matrix.
Given a Directed Acyclic Graph (DAG), print it in topological order using topological sort algorithm. If the DAG has more than one topological ordering, output any of them.
Find the minimum number of throws required to win a given Snake and Ladder game. For example, the following game requires at least 7 dice throws to win.
Given a graph, check if it is bipartite 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
.
This post describes the types of edges involved in Depth–first search (DFS) of a tree and directed & undirected graphs and establish the relation between them.
The 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.
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 for a graph) and explore as far as possible along each branch before backtracking.
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.
Given an undirected or a directed graph, implement the graph data structure in C++ without using STL. Implement for both weighted and unweighted graphs using the adjacency list representation.
In this post, we will see graph implementation in Java using Collections for weighted and unweighted, graph and digraph.