*unvisited*— if they haven't been discovered yet,*visited but not processed*— if they've been discovered but we haven't gone through their child list yet, and*visited and processed*— if we're done doing anything with them.

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] = dnew [set parent[v] = u] NOTE: Q may need to be updated, depending on how you set things upOf course the real magic is how to provide the priority queue functionality needed by Dijkstra's algorithm efficiently! Notice that we don't just need to get the minimum weighted node. We alo need to update weights of neighbors of the node we just dequeued. Supporting that efficiently is the key to making Dijkstra's algorithm efficient.

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.