04/11/1419:06:29 129 CS 61B: Lecture 29 Monday, April 7, 2014GRAPHS (continued)======Breadth-first search (BFS) is a little more complicated than depth-firstsearch, because it’s not naturally recursive. We use a queue so that verticesare visited in order according to their distance from the starting vertex. public void bfs(Vertex u) { for (each vertex v in V) { // O(|V|) time v.visited = false; } u.visit(null); // Do some unspecified thing to u u.visited = true; // Mark the vertex u visited q = new Queue(); // New queue... q.enqueue(u); // ...initially containing u while (q is not empty) { // With adjacency list, O(|E|) time v = q.dequeue(); for (each vertex w such that (v, w) is an edge in E) { if (!w.visited) { w.visit(v); // Do some unspecified thing to w w.visited = true; // Mark the vertex w visited q.enqueue(w); } } } public class Vertex { } protected Vertex parent; protected int depth; Notice that when we visit a vertex, protected boolean visited; we pass the edge’s origin vertex as a parameter. This allows us to public void visit(Vertex origin) {do a computation such as finding this.parent = origin; the distance of the vertex from if (origin == null) { the starting vertex, or finding this.depth = 0; the shortest path between them. } else { The visit() method at right this.depth = origin.depth + 1;accomplishes both these tasks. } } } When an edge (v, w) is traversed to visit a Vertex w, the depth of w is set tothe depth of v plus one, and v is set to become the _parent_ of w.The sequence of figures below shows BFS running on the city adjacency graph(Albany, Kensington, Emeryville, Berkeley, Oakland, Piedmont) from lastlecture, starting from Albany. A "V" is currently visited; a digit shows thedepth of a vertex that is marked visited; a "*" is a vertex which we try tovisit but discover has already been visited. Underneath each figure of thegraph, I depict the queue and the current value of the variable "v" in bfs().V-K 0-V 0-1 *-1 0-1 *-1 0-* 0-1 0-1 0-1 0-1 0-1 0-1 0-1 0-1 0-1 \| \| \| \| \| \| \| \| \| \| \| \| \| \| \| \|E-B E-B E-V E-1 E-* E-1 E-1 V-1 2-1 2-* 2-1 *-1 2-* 2-1 2-1 2-1|/ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ |/ O-P O-P O-P O-P O-P O-P O-P O-P V-P 2-P *-P 2-P 2-P 2-V *-3 2-3 === === === === === === === === === === === === === === === ===A K KB B B E EO O O P === === === === === === === === === === === === === === === === v=A v=A v=K v=K v=B v=B v=B v=B v=E v=E v=O v=O v=O v=PAfter we finish, we can find the shortest path from any vertex to the 0<--1starting vertex by following the parent pointers (right). These ^ pointers form a tree rooted at the starting vertex. Note that they \ point in the direction _opposite_ the search direction that got us there. \ 2-->1Why does this work? The starting vertex is enqueued first, then all the ^ vertices at a distance of 1 from the start, then all the vertices at a / distance of 2, and so on. Why? When the starting vertex is dequeued, / all the vertices at a distance of 1 are enqueued, but no other vertex 2<--3is. When the depth-1 vertices are dequeued and processed, all thevertices at a distance of 2 are enqueued, because every vertex at a distance of2 must be reachable by a single edge from some vertex at a distance of 1. Noother vertex is enqueued, because every vertex at a distance less than 2 hasbeen marked, and every vertex at a distance greater than 2 is not reachable bya single edge from some vertex at a distance of 1.Recommendation: pull out a piece of paper, draw a graph and a program stack,and simulate BFS, with you acting as the computer and executing bfs() line byline. You will understand it much better after taking the time to do this.BFS, like DFS, runs in O(|V| + |E|) time if you use an adjacency list;O(|V|^2) time if you use an adjacency matrix.Weighted Graphs---------------A weighted graph is a graph in which each edge is labeled with a numericalweight. A weight might express the distance between two nodes, the cost ofmoving from one to the other, the resistance between two points in anelectrical circuit, or many other things.In an adjacency matrix, each weight is stored in the matrix. Whereas anunweighted graph uses an array of booleans, a weighted graph uses an array ofints, doubles, or some other numerical type. Edges missing from the graph canbe represented by a special number like Integer.MIN_VALUE, at the cost ofdeclaring that number invalid as an edge weight. (If you want to permit everyint to be a valid edge weight, you might use an additional array of booleansas well.)In an adjacency list, recall that each edge is represented by a listnode. Eachlistnode must be enlarged to include a weight, in addition to the reference tothe destination vertex. (If you’re using an array implementation of lists,you’ll need two separate arrays: one for weights, and one for destinations.)There are two particularly common problems involving weighted graphs. One isthe _shortest_path_problem_. Suppose a graph represents a highway map, andeach road is labeled with the amount of time it takes to drive from oneinterchange to the next. What’s the fastest way to drive from Berkeley to LosAngeles? A shortest path algorithm will tell us. You’ll learn several ofthese algorithms if you
View Full Document
Unlocking...