Depth-First Search

Reading: CLR 22.3

Does this look familiar?

1 for each vertex v in V

2 color[v] = white

3 d[v] = INFINITY

4 p[v] = NULL

5 color[s] = gray

6 d[s] = 0

7 Queue.clear()

8 Queue.put(s)

9 while (!Queue.empty())

10 v = Queue.get()

11 for each u adjacent to v

12 if (color[u] == white)

13 color[u] = gray

14 d[u] = d[v] + 1

15 p[u] = v

16 Queue.put(u)

17 color[v] = black

Of course, this is the BFS algorithm. What happends if we replace the Queue with a Stack?

By placing the vertices to examine on a stack instead of in a queue, the behavior of our traversing algorithm is completely changed. Now, the algorithm will traverse a vertice and all of its descendents in the graph before traversing the vertice’s sibling.

There is one interesting detail: If we use the stack, than the vertice we get from the Stack will be the last one we put on. Instead of putting it on the stack and then removing, we can just continue our search with that vertice. How? Recursion!

DFS(G)

1. for each vertex u in V

2. color[u] = white

3. p[u] = null

4. time = 0

5. for each vertex u in V

6. if(color[u] == white)

7. DFS-VISIT(u)

DFS-VISIT(u)

1. color[u] = gray

2. time = time + 1

3. d[u] = time

4. for each v adjacent to u

5. if (color[v] == white)

6. p[v] = u

7. DFS-VISIT(v)

8. color[u] = black

9. time = time + 1

10. f[u] = time

There are several important differences between the Depth-first and Breadth-first algorithm. First, it makes no sense to compute the distance from the root anymore, since DFS does not compute shortest distances. Instead, we compute d[v] for every vertex v which represents a time-stamp of when was v discovered. Also, we compute f[v] which is a time-stamp of when was d finished with in the DFS. f[v] and d[v] have some interesting properties that are used in other algorithms that use DFS.

As before, p[u] is the parent of a vertice in a DFS tree. Actually, using DFS we generally compute a forest, not just a tree. If a vertice is not discovered during the DFS-VISIT, that vertice becomes a root for a new search (line 7 in DFS(G)). We could have done the same in the BFS, but we didn’t because these two algorithms are usually used from other algorithms as presented here.

Also, we can classify the edges in the G as one of the following:

1. Tree edges are edges in the depth-first forest. These are the edges we traverse when we discover a white vertex

2. Back edges those edges (u,v) connecting a vertex u to an ancestor v in a depth-first tree. Self-loops are back edges as well. These are the edges we traverse when we discover a gray vertex.

3. Forward edges are those non-tree edges connecting a vertex to its descendent in the depth-first tree. These are the edges (u,v) we traverse when we discover a black vertex v and d[u]<d[v]

4. Cross edges are all other edges. They can exist in the same depth-first tree, or can go between the trees in the forest. These are the edges (u,v) we traverse when we discover a black vertex v and d[v] < d[u]

An example of DFS.

DFS has some nice properties as well:

Theorem 1(parenthesis theorem). In any depth-first search of a graph, for any two vertices u and v, exactly one of the following three conditions holds:

1. the intervals [d[u], f[u]] and [d[v],f[v]] are entirely disjoint, and neither u nor v is a descendant of the other in the depth-first forest

2. the interval [d[u],f[u]] is contained entirely within the interval [d[v],f[v]] and u is a descendant of v in a depth-first tree

3. Same as 2. with u and v roles reversed.

What does this mean? It means that for every vertex u and v, such that v is the descendent of u in the depth-first tree, d[u]<d[v]<f[v]<f[u].

If we consider d[v] an open parentesis “(v”, and f[v] a closed parentesis “)v”, then the expression formed when all d[v] and f[v] are sorted for all vertices, is a well-formed expression (the parenthesis are balanced). In our example, the expression will be:

(u (v (y (x x) y) v) u) (w (z z) w)

Theorem 2. (white path theorem). In a depth-first forest of a graph, vertex v is a descendant of vertex u if and only if at the time d[u] when the search discovers u, v can be reached from u along a path consisting entirely of white vertices.

Theorem 3. (DFS on undirected graphs). In a depth-first search of an undirected graph, every edge is either a tree edge or a back edge.

Best-first search

Reading: CLR 61., 6.2, 6.3, 6.5

What happends if we don’t use neither stack nor queue in our algorithm? What if we use a data structure that (somehow) gives us a best candidate towards the solution first? This is called best-first search, or A*.

The idea is to have a function (a heuristic) that is easy to compute that will give us a good idea of how “good” the next choice is.

Examples: for grids, you can do Manhattan distance, or diagonal distance, or straight-line distance.

Manhattan distance: f(x,y) = |target.x – x| + |target.y – y|

Diagonal distance: f(x,y) = max(|target.x – x|, |target.y – y|)

Straight-line distance f(x,y) = SQRT((target.x – x)² + (target.y – y)²)

To enable choosing a best candidate from a pool of candidates, we need a different data structure, a simple queue is not going to be very efficient.

What we need is a priority queue: works the same as a queue, but when we do a dequeue it gives us the best (i.e. a maximum or minimum according to some function) element.

A very good data structure to create a priority queue is a heap.

Heaps

Heaps are almost-complete binary trees, that have a nice property: the value stored in each node is greater than the value stored in any of its descendents (for max-heaps) or the value stored in each node is smaller than the value stored in any of its descendents (for min-heaps).

We will discuss max-heaps here. Min-heaps are very similar and should be straightforward to implement once max-heaps are understood.

Here’s an example of a max-heap:

Heaps are actually implemented in a more efficient way – they are not represented as graphs or trees. They are stored in a single array. They are stored in such a way that the tree operations on a node (getting a parent, left or right child) can be performed as follows:

parent(i) = floor(i/2)

left(i) = 2*i

right(i) = 2*i + 1

So, the largest element (the root of the tree) is stored in A[1]. Its children are stored in A[2] and A[3]. Children of A[3] are stored in A[6] and A[7] and so forth…

Notice that any subtree of a heap is also a heap. Also notice that the nodes are stored in the array in “layers” – the highest ones first, than the next ones, then the next e.t.c.

To maintain a heap property (every node has a value greater than any of its descendents), we use the procedure MAX-HEPIFY. Given a heap A and a node i that does not satisfy the heap property (but its left and right subtrees are correct heaps), this procedure traverses the tree down, switching nodes that violate the heap property until the property is satisfied. The running time is O(log(n)).

MAX-HEAPIFY(A,i)

1. l = left(i)

2. r = right(i)

3. if (l<= A.size && A[l] > A[i])

4. largest = l

5. else

6. largest = i

7. if (r<=A.size && A[r]>A[largest])

8. largest = r

9. if (largest != i)

10. exchange(A,i,largest)

11. MAX-HEPIFY(A,largest)

To build a max-heap from an arbitrary array, we have to notice that the leaves in a tree are already heaps (they satisfy the heap property by default). So, in the tree defined by the array, the leaves are already heaps, meaning that going up in the tree we can use MAX-HEAPIFY to create heaps consisted of a node and two leaves, then bigger and bigger heaps until the whole tree is a max-heap.

BUILD-MAX-HEAP(A)

1. A.size = A.length

2. for (i = floor(A.length/2); i>0; i--)

3. MAX-HEAPIFY(A,i)

For our priority queue purposes, we need to get the maximum element, and enqueue and dequeue operations.

Maximum is simple:

HEAP-MAXIMUM(A)

1. return A[1]

Dequeuing (removing the maximum element) is more complicated. We need to maintain the almost-complete binary tree property that all the levels in the tree are complete except maybe the last one. That’s why we exchange A[1] with the last element in A and then remove the last element (to maintain the almost-complete binary tree property) and then do MAX-HEAPIFY on the root (to maintain the heap property).

HEAP-EXTRACT-MAX(A)

1. if (A.size < 1)

2. error “heap underflow”

3. max = A[1]

4. A[1] = A[A.size]

5. A.size = A.size – 1

6. MAX-HEAPIFY(A,1)

7. return max

Priority max-queues sometimes need the operation of increasing the value of a node (for example, in operating systems). After increasing the value of a node, we need to “bubble” it up in the tree – switch it with its parent – until the heap property is satisfied.

Exercise: write a HEAP-DECREASE-KEY(A,i,key) for max-heaps

HEAP-INCREASE-KEY(A,i,key)

1. if (key < A[i])

2. error “new key is smaller than current key”

3. A[i] = key

4. while (i > 1 && A[parent(i)] < A[i])

5. exchange(A,i,parent(i))

6. i = parent(i)

Now that we know how to increase the value of a node, inserting a node into a priority queue is simple: we just put it at the end of A, set its value to –INFINITY and then increase its value to the correct value. Can you see why we do this? Why can’t we just set its value to key and be done with it?

MAX-HEAP-INSERT(A,key)

1. heap-size[A] = heap-size[A] + 1

2. A[heap-size[A]] = -INFINITY

3. HEAP-INCREASE-KEY(A,heap-size[A],key)

Exercise: write the corresponding procedures for min-heaps: MIN-HEAPIFY, BUILD-MIN-HEAP, HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY and MIN-HEAP-INSERT.