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