intro types of graph terminology 图论问题 s-t Path. Is there a path between vertices s and t? Shortest s-t Path. What is the shortest path between vertices s and t? Cycle. Does the graph contain any cycles? Euler Tour. Is there a cycle that uses every edge exactly once? Hamilton Tour. Is there a cycle that uses every vertex exactly once? Connectivity. Is the graph connected, i.e. is there a path between all vertex pairs?

interface 1 2 3 4 5 6 7 8 9 10 11 12 /** (Min) Priority Queue: Allowing tracking and removal of the * smallest item in a priority queue. */ public interface MinPQ<Item> { /** Adds the item to the priority queue. */ public void add(Item x); /** Returns the smallest item in the priority queue. */ public Item getSmallest(); /** Removes the smallest item from the priority queue. */ public Item removeSmallest(); /** Returns the size of the priority queue.

Traversals Level Order Traverse top-to-bottom, left-to-right (like reading in English): We say that the nodes are ‘visited’ in the given order. Depth First Traversals Preorder, Inorder, Postorder Basic (rough) idea: Traverse “deep nodes” (e.g. A) before shallow ones (e.g. F). preorder 1 2 3 4 5 6 preOrder(BSTNode x) { if (x == null) return; print(x.key) preOrder(x.left) preOrder(x.right) } D B A C F E G inorder 1 2 3 4 5 6 inOrder(BSTNode x) { if (x == null) return; inOrder(x.