Fastest way to check the number of nodes reachable from source node

general
, , ,
1

I was doing a problem which involved finding number of reachable nodes from a source node. I implemented this via dfs. I was wondering whether this was the fastest way to check or whether there was any other algorithm I should be looking at.

On an unrelated node: If I implement an algo by using 1.)recursion with memoization or 2.)by iterating , and if the time complexity of both implementation is same which one would execute faster(i.e. if there would be any difference). Does the compiler handle recursion faster than iteration or vice-versa?

2

The fastest way to implement this is DFS or BFS .Both are O(E) where E is the number of edges in the graph. No algorithm can run faster than this.

An iterative solution will most probably run faster than a recursive one as the number of function calls will be lesser and time is consumed because of these function calls .However the time complexity of both will be same

1 Like