Online resources say: a spanning tree of a directed graph can be found in O(|V|+|E|) time. Note that I'm not talking about the minimum spanning tree.
I am looking for an algorithm that can find any one spanning tree given a digraph D whose edges don't have any weights associated to them.
I can't find any algorithms online. Please help.
Pick any vertex as root, then proceed using a simple breadth-first search or depth-first Search to add adjacent vertices to your tree until every vertex has been visited once. Enforce visiting every vertex exactly once using a hash table (O(1) insert and lookup) to check previously visited vertices. That way you will achieve O(|V| + |E|) time complexity.