Graphs and Dynamic Programming

I've been learning graphs and dynamic programming somewhat interleaved. Dynamic programming tends to help solve graph problems because:

Every problem solvable by dynamic programming can be represented in a DAG.

A couple of things I discovered in my experiments:

  • Using a queue for graph traversal (cyclic or acyclic) always does breadth-first search.
  • Using a stack for graph traversal (cyclic or acyclic) always does depth-first search.
  • DFS (traversal using stack) on a binary tree always does a pre-order traversal.

Another fact (not my discovery, that's for sure), is that breadth-first search on an unweighted graph gives the shortest unweighted path between the starting vertex and any other vertex.

I don't have much more to add right now. I've still got a lot to study and I feel I'm falling behind. Time is short.

Right now I'm going over:

  • depth-first search
  • breadth-first search
  • topological sort
  • minimum spanning trees:
    • Prim's algorithm
    • Kruskal's algorithm
  • single-source shortest paths: Dijkstra's algorithm
  • counting connected components
  • listing strongly connected components
  • checking for existence of a cycle
comments powered by Disqus