depth first search

Find Mother Vertex in a Graph【O(V+E)】

mother vertex in a graph is a vertex from which we can reach all the nodes in the graph through directed path. If there exist mother vertex (or vertices), then one of the mother vertices is the last finished vertex in DFS. (Or a mother vertex has the maximum finish time in DFS traversal).

algorithm

Centroid Decomposition of Tree

Centroid Decomposition is a divide and conquer technique which is used on trees. Given a tree with N nodes, a centroid is a node whose removal splits the given tree into a forest of trees, where each of the resulting tree contains no more than N/2 nodes.

algorithm

Topological Sorting using Depth First Search (DFS)

We will implement Topological sorting using Depth First Search in linear time O(V+E). Topological Sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. It is useful in instruction scheduling and other

graph algorithm

Fleury’s Algorithm: Finding Eulerian tours in a graph

Fleury's algorithm is a simple algorithm for finding Eulerian paths or tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian.

graph algorithm

Find articulation points or cut vertices in a graph

Find articulation point or cut vertices in a graph. A vertex in an undirected connected graph is an articulation point or cut vertex if and only if removing it, and the edges connected to it, splits the graph into multiple components. Hint: Apply Depth First Search on a graph.

graph algorithm

Find cut edges in a graph

Find cut edges in a graph in linear time complexity using Depth First Search. A cut edge e = uv is an edge whose removal disconnects u from v. There are two key observations to solve this problem.

graph algorithm

Depth-first search (DFS) algorithm 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.