×
Home Discussions Write at Opengenus IQ
×
  • #7daysOfCode
  • C Interview questions
  • Linux ๐Ÿ’ฝ
  • ๐Ÿ”Š Data Structures
  • Graph Algorithms
  • Dynamic Programming ๐Ÿ’‘
  • Greedy Algo ๐Ÿ“”
  • Algo Book ๐Ÿง 
  • String Algo ๐Ÿงฌ
  • Join our Internship ๐ŸŽ“
  • Home

depth first search

A collection of 7 posts

Algorithms

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).

Parth Maniyar Parth Maniyar
Algorithms

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.

Sadanand Vishwas Sadanand Vishwas
Algorithms

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

Saranya Jena Saranya Jena
Graph Algorithms

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.

Alexa Ryder Alexa Ryder
Graph Algorithms

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.

Alexa Ryder Alexa Ryder
Graph Algorithms

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.

Alexa Ryder Alexa Ryder
Graph Algorithms

Depth First Search

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.

Alexa Ryder Alexa Ryder
×

Visit our discussion forum to ask any question and join our community

View Forum
OpenGenus IQ © 2021 All rights reserved โ„ข [email: team@opengenus.org]
Top Posts LinkedIn Twitter