• Given a graph, one way to visit every vertex in that graph is via a breadth-first search.• Select a starting point.• Visit all vertices that are “one jump” away from it.• Visit all vertices that are “two jumps” away from it.• A simple problem that can be solved using this general technique is that of finding the shortest path between two vertices in an undirected and unweighted graph.• If the graph is not connected, what happens?Starting at vertex s∈V generate an array of distances from s called dist[] such that for all v∈V, dist[v]=length of shortest path from s to v.dist[s]=0We will also create a predecessor array of the last vertex we were at before getting to the end of the path from s to v for all v∈V, pred[v]=“one step back” pred[s]=noneWith just these two arrays, we will be able to reconstruct any shortest part request from s to some vertex. This is because any sub-path of the optimal path must also be an optimal path between its own endpoints. If it weren’t, then we could have replaced it and gotten a shorter overall path.Start at s.For each neighbor v of sdist[v]=1pred[v]=s.Move outwards from each neighbor you’ve seen and set the next “ripple” out as “+1” of the current distance, and set pred[] appropriately.Need a way to make sure we don’t end up in cycles!We will assign a color to each vertex based on the following rules:- white = not seen yet at all- gray = seen but not processed yet- black = processedWe will create a queue of gray vertices, and will never add any vertex to the queue more than once.When we are done processing a vertex (ie: we have touched all its neighbors) we go back to the queue to get the next vertex to process.BFS (Graph G, vertex s) {int size = G.getVertexCount;int dist[] = new int[size];vertex pred[] = new int[size];Queue Q= new Queue<vertex>;Colors state[] = new Colors[size];for each v in G.V {state[v]=white; dist[v]=infinity; pred[v]=none;}state[s]=gray; dist[s]=0; pred[s]=none;Q.add(s);while (!Q.empty()){u=Q.remove();for each unvisited v in G.Adj(u) {state[v]=gray;dist[v]=dist[u]+1;pred[v]=u;Q.add(v);}state[u]=black;}}• Each vertex gets enqueued at most one time, so each is processed at most one time.• Let’s write this up using a summation to represent the processing of all of the vertices…• It allows us to organize the entire graph as “ripples” away from a central point.• This could be useful if we could restate other questions within this framework.• Our predecessor array could be used to create a tree rooted at source s of vertices that can be reached from s. • This is often called a breadth-first tree. • If we could phrase a problem as a traversal of this tree…NOTE: This only works if there are no cycles, since if there are cycles there isn’t the notion of a sorted order.Imagine a graph as beads where the edges are strings of equal length connecting ordered pairs of beads.You want to arrange the beads so that all edges point left-to-right.How can you use a DFS with “timing” info to accomplish
View Full Document
Unlocking...