Given an undirected graph, check if is is a tree or not. In other words, check if given undirected graph is a Acyclic Connected Graph or not.
Given a digraph (Directed Graph), find the total number of routes to reach the destination from given source that have exactly m edges.
Given an connected undirected graph, find if it contains any cycle or not.
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.
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.
Describe types of edges involved in DFS of a tree and directed & undirected graph and establish relation between them.
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.
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.
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 without using any container provided by any programming language library (e.g. STL in C++ or Collections in Java, etc). Implement for both weighted and unweighted graphs using Adjacency List representation.