1. DFS + Pre/Post
Alphabetic order when applicable
A. Pre and Post
Pre
A - 1 B - 2 D - 3 F - 4 E - 7 C - 10
Post
F - 5 D - 6 E - 8 B - 9 C - 11 A - 12
Remember
Clock increments for both pre and post too Single node in recursion stack goes to post call iff all its vertices connected vertices have been visited
B. Identify edges
Tree edge - normal traversal Forward edge - ancestor → non-child descendant Back edge - descendant - ancestor Cross edge - edge to an alrdy fully explored node (postvisited)
Tree
A, B B, D D, F B, E A, C
Forward Edge
None
Back Edge
F, B
Cross edge
E, F A, C
C: Contains Cycle?
Yes - back edge
2. SCC
A. Find all SCC’s
1 2, 3, 4, 5, 6
B. Draw metagraph
1 → M
C. Why metagraphs are always DAG’s
Since SCC’s with more than one node always contain at least one cycle, by treating every cycle like a node, the resulting graph links acyclic nodes.
Better explanation
Assume to the contrary that the metagraph has a cycle Then SCC A has an edge going to SCC B and vice versa. This means every node in A can reach B and vice versa. This means that they should be a single SCC, not two separate ones. We have reached a contradiction.
D. Topological Ordering
M, 1
3. Topological Sort
A. Verify DAG
All nodes are singletons.
How to actually verify by def of a DAG
Confirm no cycles via DFS (no back edges or finding a ancestor node)
B. Valid topological ordering with DFS + Post-Order
A, C, E, B, D, F
Explanation
Do post-order decreasing for topological
C. Uniqueness?
No A B C D E F
D. Min Time Steps for Parallel
Explanation
Length of longest chain to complete nodes in parallel
Algorithm for counting a length of a path
Height/depth of a DAG
4. Djikstra’s
Relaxed edges - ones that cause the known distance map for a vertex to be updated
5. BFS vs DFS
A. Prove every path from s to v is less than distance d
Assume we ran BFS from vertex s and vertex v is at distance d from s. BFS finds shortest path. Assume to the contrary that there was a path less than d. But d was the shortest path. We have reached a contradiction.
B
Yes, consider a degenerate graph
C
BFS always finds a shortest path because it proceeds in steps away from a source vertex, evaluating all paths at once and therefore guaranteed to find shortest. DFS is not guaranteed because it goes depth first and can traverse a longer path first.
Remember
BFS - shortest path
6. MST Kruskal
A.
B, D A, C E, F C, D B, E
B. Total weight
C
Edges are all distinct; no point at which an edge with min weight is not considered due to cycle where choosing a diff min weight at a diff time would hav echanged
D
Replace BD with AB
7. Prim’s and Cut Property
a.
1, 3 1, 4 2, 4 2, 5
b
If there is a minimum edge where e has vertices u, v and , then is contained in some MST
c
Goal: is contained in some MST
Let A be the current graph (1, 3) and be a cut Assume min edge e where and is the remaining edge of minimum weight Possible choices are 3, 4 2, 4 2, 5 Let