SUNY Geneseo Department of Computer Science

Breadth First Search

Tuesday, January 29

CSci 242, Spring 2013
Prof. Doug Baldwin

Questions?

Problem 3 from graphs problem set (two people in any group of n > 2 have the same number of friends in the group)?

[Discussion developed a graph version of the theorem and considered several ways to solve it. Not shown here because people who assign or write textbook problems would prefer not to have solutions widely available on the Web.]

Try it by hand

Heavily connected graph on 7 vertices

Quoridor

See http://www.fupa.com/play/BoardGame-free-games/quoridor.html
A computer player can find a path towards its goal (aka “endzone”) by using breadth first search
Graph uses vertices to represent squares on the board and (undirected) edges to represent the ability to move from one square directly to another
Source vertex for breadth first search is the one the pawn is currently on
Modify breadth first search so that it stops as soon as it finds any square in the endzone
That square is necessarily the one with the shortest path—this follows from Corollary 22.4 (that vertices are enqueued in increasing order of distance) and the fact that a queue is a FIFO structure

Depth first search

Read Section 22.3