CODEWITHSUNDEEP
algorithmdirected-graph
TL7
TL7

Reputation: 1

Algorithm to find a root of directed graph

I can easily tell which node is the root of a directed graph by looking at it but if I want to use an algorithm to find one do I start with DFS?

Upvotes: 0

Views: 2276

Answers (1)

Catie Lambert
Catie Lambert

Reputation: 21

A directed graph doesn't have a root unless it's a tree. If you want to find the vertices of a directed graph that don't have incoming edges, you can run DFS and keep track of how vertices are discovered. If a vertex is only discovered because it was selected from the list of vertices and is never rediscovered by an edge, then it has no incoming edges.

Another way to think of this is using DFS to examine all the edges of the graph. Any vertex that never shows up at the receiving end of an edge will be a "root".

Upvotes: 2

Related Questions