**P3**from Week 08 quiz questions (take home, to be done before Class 13)**P4**from Week 08 quiz questions (take home, to be done before Class 18)

search(graph G, vertex s) ------------------------- initialize "store" S add s to S mark s as visited [set parent[s] = null] while S is not empty do u = remove next vertex from S for each child v of u do if v not marked visited mark v as visited [set parent[v] = u] add v to S

search(graph G, vertex s) ------------------------- initialize stack S S.push(s) mark s as visited [set parent[s] = null] while S is not empty do u = S.pop() for each child v of u do if v not marked visited mark v as visited [set parent[v] = u] S.push(v)

search(graph G, vertex s) ------------------------- initialize queue Q Q.enqueue(s) mark s as visited [set parent[s] = null] while Q is not empty do u = Q.dequeue() for each child v of u do if v not marked visited mark v as visited [set parent[v] = u] Q.enqueue(v)

search(graph G, vertex s) ------------------------- initialize priority queue Q based on vertices "dist" Q.enqueue(s) ← first setting dist[s] = 0 mark s as visited [set parent[s] = null] while Q is not empty do u = Q.dequeue() ← i.e. dequeue vertex with minimum "dist" on queue for each child v of u do if v not marked visited mark v as visited [set parent[v] = u] ← set dist[v] = dist[u] + weightOfEdge(u,v) Q.enqueue(v) else dnew = dist[u] + weightOfEdge(u,v) if dnew < dist[v] set dist[v] = min(dist[v],) [set parent[v] = u] NOTE: Q may need to be updated, depending on how you set things up

As an exercise in class, we broke into groups and took the same graph and tried the Queue, Stack and Dijkstra/Priority-queue versions of search as above. What I asked you to do was to draw the graph with the edges from the "parent" relation highlighted. The highlighted edges formed (of course) a tree. This tree is called "the search tree" for the graph. So even though we have an arbitrary graph, the search algorithm implicitly follows a subgraph of edges that form a tree. This tree is interesting!

- with a stack - if you look at the order that nodes are popped off the stack, the search algorithm ends up performing a depth-first traversal of the search tree. That's why we refer to this as depth-first search.
- with a queue - if you look at the order that nodes are dequeued, the search algorithm ends up performing a breadth-first traversal of the search tree. That's why we refer to this as breadth-first search.
- with the priority queue with the Dijkstra weight - the search tree ends up consisting of the shortest paths from $s$ to all the reachable vertices.