Modified Search Problem: Directed Graph

  • Recognize BFS/DFS can be carried on a directed graph.
  • Trace the shortest path algorithm in an unweighted graph by specifying the values in auxiliary data structures.
  • Analyze the running time of the (unweighted) shortest path algorithm, assuming an incidence/adjacency list Graph implementation.

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 AA. 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)\Omicron(N+M).
  • The modified BFS requires more auxiliary space, although it is asymptotically linear (same as plain BFS).