depth first search

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.