Modified Search Problem: Directed Graph

The BFS/DFS algorithm can be carried on a directed graph. The only adjustment would be to consider the "outgoing neighbors" of each vertex during "exploration".

Consider the following directed graph:

Exercise Carry the BFS algorithm on the graph above starting at vertex $A$. Keep track of previous and distance values for each vertex. Reflect on the complexity of the algorithm.

Solution
  • The complexity of algorithm is same as the plain BFS algorithm; it runs in $O(N+M)$.
  • The modified BFS requires more auxiliary space, although it is asymptotically linear (same as plain BFS).