CS 3510 Midterm: CS 3510 GT t2Practice
Document Summary
Test 2 in class, friday, sep 30, 2016: main topics. Checking s t reachability in graphs. Shortest path and how to nd them. Minimum spanning tree, cut property, and algorithms for nding them. Dijkstra"s algorithm and how to get to o(m log n): not included: Speeding up reachability to o(m) using breadth- rst-search. How to extract negative cycle from nal state of the bellman-ford algorithm (you should know that it can be done though). Speeding up kruskal"s / prim"s mst algorithms o(m log n): graphs. Vertices, edges, arcs, g = (v, e, w) or g = (v, e, l). Walk: sequence of vertices v0 . vk s. t. vi vi+1 e. If there is a s t walk, there is a s t path: connectivity: Reachability: check if there is path from s t. Connectivity in o(nm) time by repeatedly propagate reached" ags. Undirected graph: connected components, vertices are partitioned into connected compo- nents: s t shortest path:
