In the last lecture we learned about graph representations and depth-first search. We will now look at breadth-first search, which is another fundamental graph algorithm.
Starting from some vertex V, a breadth-first search first visits vertices adjacent to V, i.e. vertices of distance 1 from V. It then visits vertices of distance 2, and so on. In this way it can determine the shortest distance from V to every other vertex in the graph.
We can implement a breadth-first search using a queue, i.e. a FIFO (first in first out) data structure. Also, just as with a depth-first search, we will need a visited set to avoid walking in circles as we search.
We begin by adding the start vertex to the queue and marking it as visited. In a loop, we repeatedly remove vertices from the queue. Each time we remove a vertex, we mark all of its adjacent unvisited vertices as visited and add them to the queue. The algorithm terminates once the queue is empty, at which point we will have visited all reachable vertices.
For example, consider the graph of Europe that we saw in the previous lecture:
Suppose that we begin a breadth-first search at 'austria'. Initially the queue contains only that vertex:
Q = austria
We dequeue 'austria' and enqueue its neighbors (and add them to the visited set):
Q = germany czech hungary slovakia slovenia italy
Next, we dequeue 'germany' and add its neighbors to the queue. However we do not add 'austria' or 'czech', which have already been visited:
Q = czech hungary slovakia slovenia italy belgium netherlands luxembourg denmark poland france
Now we dequeue 'czech'. Its neighbors are 'austria', 'germany', 'poland' and 'slovakia' but they are all visited, so there is nothing to add:
Q = hungary slovakia slovenia italy belgium netherlands luxembourg denmark poland france
Now we dequeue 'hungary'. It has two unvisited neighbors 'romania' and 'croatia', so we enqueue them:
Q = slovakia slovenia italy belgium netherlands luxembourg denmark poland france romania croatia
Next, we dequeue 'slovakia' and 'slovenia'. They have no unvisited neighbors:
Q = italy belgium netherlands luxembourg denmark poland france romania croatia
Just as with a depth-first search, we may imagine that at any time during a breadth-first search, each vertex is either undiscovered (white), on the frontier (gray) or explored (black). The queue represents the frontier, i.e. the gray vertices. So the picture now looks like this:
The gray vertices are in the queue; the black vertices have already been dequeued; the white vertices have not yet entered the queue.
As the algorithm runs, all vertices in the queue are at approximately the same distance from the start vertex. To be more precise, at every moment in time there is some value d such that all vertices in the queue are at distance d or (d + 1) from the start vertex. (At this particular moment in this example, all the vertices in the queue have distance either 1 or 2 from the start vertex 'austria'.)
To implement a breadth-first search in Python, we need a queue implementation. As we learned in a previous lecture, we could implement an efficient queue using a linked list. However, Python's library contains a type deque that we can use instead, which is a bit more convenient. A deque is a double-ended queue: at any time we can append or prepend an item, or remove an item from the front or back of the queue. All of these operations are efficient, i.e. run in O(1) on average. In our implementation, we will call the append() method of the deque class to add an element to the queue, and will call popleft() to remove an item. (Alternatively, we could call appendleft() and pop(), in which case our items would travel through the deque in the opposite direction.)
Here's an implementation of breadth-first search for a graph with integer ids. The visited set is an array of booleans:
from collections import deque
# breadth-first search over graph with integer ids
def bfs(graph, start):
visited = [False] * len(graph)
visited[start] = True
q = deque()
q.append(start)
while len(q) > 0:
v = q.popleft()
print('visiting', v)
for w in graph[v]:
if not visited[w]:
visited[w] = True
q.append(w)Notice that we mark vertices as visited when we add them to the queue, not when we remove them. This ensures that our algorithm will not add the same vertex to the queue more than once.
Like a depth-first search, this breadth-first search function does a constant amount of work for each vertex and edge, so it also runs in time O(V + E).
Let's modify our breadth-first search code so that it can run on our graph of Europe. Since vertex ids are strings, we will store the visited set using a Python set, not an array of booleans. Also, as we search we will compute the distance from the start vertex to every other vertex that we reach. To achieve this, each queue element will be a pair (v, d), where v is a vertex id and d is the distance from the start vertex to v. Finally, when we print out each vertex we will indent it by its distance from the start. Here is the code:
from collections import deque
# breadth-first search over graph with arbitrary ids
def bfs(g, start):
visited = { start }
q = deque()
q.append((start, 0))
while len(q) > 0:
v, dist = q.popleft()
print(' ' * dist + v)
for w in g[v]:
if w not in visited:
q.append((w, dist + 1))
visited.add(w)Let's run it:
>>> bfs(europe, 'ireland')
ireland
uk
france
belgium
luxembourg
germany
italy
spain
netherlands
austria
czech
denmark
poland
greece
malta
slovenia
portugal
slovakia
hungary
sweden
lithuania
bulgaria
croatia
romania
finland
latvia
estonia
>>> We can easily see that the breadth-first search discovers vertices in increasing order of distance from the start vertex.
As it runs, a breadth-first search implicitly generates a breadth-first tree, in which each vertex points to all vertices that are first discovered from it as we search. Here is a breadth-first tree generated by searching our graph of European countries, starting with Austria:
In this picture, the dotted lines are not part of the breadth-first tree. They are edges which were not followed during the search, since they pointed to vertices that were already in the visited set.
The breadth-first tree contains a shortest path from the starting vertex ('austria') to every other vertex in the graph.
Let's now reverse all edges in the breadth-first tree. The result looks like this:
In this picture, each vertex points to its predecessor, namely the vertex from which we discovered it during the breadth-first search. Starting with any vertex v, we can follow arrows to reach the starting vertex. As we do so, we will be walking along a shortest path from v to the starting vertex.
We can modify our breadth-first search code so that as it runs, it remembers the predecessor of each vertex that it discovers. Then once we reach a goal vertex we can retrace a path back to the starting vertex. If we reverse this path, we will have a path from the start to the goal. Here is the updated code:
from collections import deque
# Return a list of vertices along a shortest path from the given start vertex
# to the given goal. If there is no such path, return None.
def bfs_path(graph, start, goal):
visited = { start }
pred = {}
q = deque()
q.append(start)
pred[start] = None # start vertex has no predecessor
while len(q) > 0:
v = q.popleft()
if v == goal:
path = []
while True:
path.append(v)
if pred[v] == None:
break
v = pred[v]
path.reverse()
return path
for w in graph[v]:
if w not in visited:
q.append(w)
visited.add(w)
pred[w] = v # remember w's predecessor
return None # no pathLet's take our breadth-first search code from above, and modify it so that it uses a stack instead of a queue. We can use an ordinary Python list as a stack: we'll call append() to push and pop() to pop. Both of these operations will run in O(1) on average.
from collections import deque
def search(g, start):
visited = { start }
q = []
q.append(start)
while len(q) > 0:
v = q.pop()
print(f'visiting {v}')
for w in g[v]:
if w not in visited:
q.append(w)
visited.add(w)Let's run this code on our Europe graph:
>>> search(graph, 'austria') visiting austria visiting italy visiting malta visiting greece visiting bulgaria visiting romania ...
The code performs a depth-first search! This shows how we can perform a depth-first search non-recursively. This is useful, since Python (and many other languages) allow only a limited depth of recursive calls.
Now, this depth-first search code will not visit the vertices in the same order as the recursive depth-first search that we wrote before. That's because it processes a vertex's neighbors in a slightly different way than the recursive version does. In particular, this version marks all neighboring vertices as visited before it explores paths through any of them. As a somewhat challenging exercise, you could attempt to modify this non-recursive code so that it visits vertices in the exact same order as the recursive version.
Depth-first search and breadth-first search are fundamental algorithms for exploring graphs. Actually these algorithms are more broadly applicable: we can use them to solve many problems in which we search through a state space. These problems have a graph-like structure. In each such problem, there is an initial state and a function that maps each state to a list of its possible successor states. We are searching for some path that leads from the initial state to a goal state.
For example, consider the problem of finding the shortest number of hops that a knight can make to travel from one square to another on a chessboard. Recall that a knight's move has an L shape. The following picture indicates the 8 different squares to which a knight at the given position can move:
In this problem, each state is an (x, y) position on the board. The initial state is the knight's starting square. Each state has up to 8 neighbors, which are the squares that the knight can move to next. The goal state is the position that the knight is trying to reach.
We may solve this problem using a breadth-first search. (A depth-first search would not work, since we are looking for a shortest path.) Each queue element will be a triple (x, y, dist), where dist is the shortest distance between the starting square and the position (x, y). To compute the neighboring states of each state, we will loop over all possible 8 directions in which a knight may move. Here is an implementation:
dirs = [(1, 2), (-1, 2), (1, -2), (-1, -2),
(2, 1), (2, -1), (-2, 1), (-2, -1)]
# Print the smallest number of knight moves to get from (start_x, start_y)
# to (end_x, end_y) on a chessboard.
def knight_path(start_x, start_y, end_x, end_y):
# visited set = 8 x 8 array of booleans
# visited[x][y] is True if we have visited (x, y)
visited = [[False] * 8 for i in range(8)]
q = Queue()
q.enqueue( (start_x, start_y, 0) )
visited[start_x][start_y] = True
while not q.is_empty():
x, y, dist = q.dequeue()
print(f'visiting {(x, y)}')
if (x, y) == (end_x, end_y):
print(f'shortest distance is {dist}')
return
for dx, dy in dirs:
x1, y1 = x + dx, y + dy # next position
if 0 <= x1 < 8 and 0 <= y1 < 8 and not visited[x1][y1]:
q.enqueue( (x1, y1, dist + 1) )
visited[x1][y1] = True
print('unreachable')As an exercise, you could enhance this function so that it prints out a sequence of positions along the shortest path from the start to the end position.
Arithmetic expressions are composed from
numeric constants and from operators that act on those
numbers. In this section we'll use non-negative integer constants
with the binary operators +, -, *
and /, the last of which denotes integer division.
In traditional mathematical notation, these
operators are infix operators: they are written between the
values that they act on (which are called operands). For
example, we write 2 + 2, or 8 - 7. In this
last expression, 8 and 7 are the operands.
Here are some arithmetic expressions written using infix notation:
(4
+ 5) * (2 + 1)
(18
/
2)
-
1
In infix notation we may write parentheses to
distinguish expressions that would otherwise be ambiguous. For
example, 4 + 5 * 9 could mean either (4
+ 5) * 9 or 4 + (5 * 9). Another way to
disambiguate expressions is using operator precedence. For
example, * is generally considered to have higher
precedence than +. However, here we will assume that no
such precedence exists; we must use parentheses to disambiguate.
We may choose an alternative syntax that uses
prefix notation, in which we write each operator before its
operands. For example, we write + 2 4 to mean the
sum of 2 and 4, or / 8 2 to mean 8 divided by 2. Here
are the above expressions rewritten in prefix notation:
* + 4 5 + 2 1 - / 18 2 1
Or we may use postfix notation, in which operators come after
both operands: we might write 4 5 + to mean the sum of 4
and 5. Here are the above expressions in postfix notation:
4 5 + 2 1 + * 18 2 / 1 -
In prefix or postfix notation there is no need either for parentheses
or operator precedence, because expressions are inherently
unambiguous! For example, the prefix expression * + 4 5 9
is equivalent to ((4 + 5) * 9), and the prefix
expression + 4 * 5 9 is equivalent to (4 + (5 *
9)). There is no danger of confusing these in prefix form,
even without parentheses.
In the next lecture we'll discuss how to represent arithmetic expressions in a program and how to convert between infix, prefix, and postfix notations.