Given a graph one way to visit every vertex in that graph is via a breadthfirst 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 0 We 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 none With 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 s dist v 1 pred 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 processed We 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 this
View Full Document
Unlocking...