CS61B: Lecture 22

Graphs and Traversals

• Tree Traversals is a means of iterating over the items within a tree.
• There are different orders that we may visit the nodes in.
• Main orderings
  • Level Order: Visit top-to-bottom, left-to-right, think about BFS.
  • Depth First Traversals
    • 3 Types: Preorder, Inorder, Postorder.
    • We traverse the deep nodes before the shallow nodes.

Preorder DF tree traversals

preOrder (BSTNode x) {
    if (x = null) return ;
    print(x.key);
    preOrder(x.left);
    preOrder(x.right)
}

• Get the current parent node, then get the preOrder traversal of the left subtree, followed by the preOrder Traversal of the right subtree.
  • Visually, we go down the left most branch first, and slowly climb back up to go to the right.

Inorder DF tree Traversal

inOrder (BSTNode x) {
    if (x = null) return ;
    inOrder(x.left);
    print(x.key);
    inOrder(x.right)
}

• Intuitively, this gets us the keys of the tree in their smallest to greater order.

Postorder DF tree Traversal

postOrder (BSTNode x) {
    if (x = null) return ;
    postOrder(x.left);
    postOrder(x.right);
    print(x.key);
}

• Intuitively, this accesses from the bottom to the top, left to right.
  • This is useful for building up from the leaves to the root of a tree.
  • We may efficiently calculate filesystem sizes like this.

    Graphs

• A Graph contains a set of nodes and edges but may contain cycles.
• Simple graphs are graphs where no edges connect a vertex to itself, and no two edges connect the same vertices.

s-t connectivity problem.

• Given a source vertex s and a target vertex t, is there a path between s and t?
• We want to create a connected(s, t)`
• Every time we call connected(s, t)
  • We mark s
  • Does s == t? retirn true
  • Otherwise, if connected(v, t) for any unmarked neighbor v of s, return true.
  • Return false;

DepthFirstPaths Demo

• Apply DFS starting from some source vertex.
• We use an array marked and edgeTo
  • marked represents if we visited that node yet.
  • edgeTo represents the node that we used to travel to the current node using DFS.
• In general, DFS is not unique.

DFS orders

• DFS Preoder: Action is before DFS calls to neighbors. Order of the recursive calls.
• DFS Postorder: Action is after DFS calls to neighbors. Order of the dfs returns.