Modified Search Problem: Directed Graph

The BFS/DFS algorithm can be carried on a directed graph. The only adjustment would be to consider each vertex's "outgoing neighbors" 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 algorithm's complexity is the same as the simple BFS algorithm; it runs in $O(N+M)$.
  • The modified BFS requires more auxiliary space, although it is asymptotically linear (same as plain BFS).