Algorithms

Breadth First Search is one of the simplest algorithms for searching a graph and the archetype of many important graph algorithms. Dijkstra's single source shortest path algorithm and Prim's minimum spanning tree algorithm use ideas similar to those in Breadth First Search.

Given a graph G=(V,E) and a distinguished source vertex s, BFS systematically explores the edges of G to discover every vertex that is reachable from s. It computes the distance (fewest number of edges) from s to all such reachable vertices. It also produces a Breadth First Tree with root s that contains all such reachable vertices. For any vertex v, reachable from s, the path is the Breadth First tree from s to v corresponds to a shortest path from s to v in G, that is, a path containing the fewest number of edges. The algorithm works on both directed and undirected graphs.

Breadth First Search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier. That is, the algorithm discovers all vertices at distance k from s before discovering any vertices at distance k+1. To keep track of progress BFS colors each vertex white, gray, or black. All vertices start out white and may later become gray and then black. The vertex is discovered the first time it is encountered during the search, at which time it becomes non-white. Gray and black vertices, therefore, have been discovered, but BFS distinguishes between them to ensure that the search proceeds in a BF manner. If (u,v) is a member of E and the vertex u is black, then vertex v is either gray or black; that is, all vertices adjacent to black vertices; they represent the frontier between discovered and undiscovered vertices.

BFS constructs a BF tree, initially containing only its root, which is the source vertex s,. Wherever a white vertex v is discovered in the course of scanning the adjacency list of an already discovered vertex u, the vertex v and the edge (u,v) are added to the three. We say that u is a predecessor or parent of v in the BF tree . Since a vertex is discovered at most once, it has at most one parent. Ancestor or descendant relationship in the BF tree are defined relative to the root s as usual; if u is on a path in the tree from root s to vertex v, then u is an ancestor of v and v is a descendant of U.

The BFS procedure assumes that the input graph G={V,E} is represented using adjacency lists. It maintains several additional data structures with each vertex in the graph. The color of each vertex u, a member of v, is stored in a variable color[u], and the predecessor of u is stored in the variable pi[u]. If u has no predecessor (e.g. if u=s or u has not been discovered) then pi[u]=nil. The distance from the source s to vertex u computed by the algorithm is stored in D[u]. The algorithm also uses a first-in-first-out queue Q to manage the ste of gray vertices.

BFS(G,s)

Depth First Search

The strategy followed by Depth First Search (DFS) is, as the name implies, to search deeper in the graph whenever possible. In DFS, edges are explored out of the most recently discoverd vertex v that has unexplored edges leaving it. When all of these edges have been explored, the search backtracks to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex. If any undiscovered vertices that are reachable from the original source vertex. If any undiscovered vertices remain, then one of them is selected as the new source and the search is repeated from that source. This entire process is repeated until all vertices are discovered.

As in BFS, whenever a vetex v is discovered during a scan of the adjacency list of an already discovered vertex u, DFS records that event by setting v's predecessor field pi[v] to u. Unlike BFS, whose predecessor sub graph forms a tree, the predecessor sub graph produced by a DFSmay be composed of several trees, because the search may be repeated for multiple sources. The predecessor sub graph of DFS is therefore defined slightly differently from that of a BFS search: We let Gpi=(V,Epi) where

Epi={(pi[v],v) : v EE V and pi[v] != nil}

The prodecessor sub graph of DFS forms DF forest composed of several DF trees. The edge in Epi are called tree edges.

As in BFS, vertices are colored the search to indicate their state, each vertex is initially white, is grayed when it is discovered in the search, and is blacked when it is finished, that is, when its adjacency list has been examined completely. This technique guarantees that each vertex ends up in exactly one DF tree so that these trees are disjoint.

Beside creating a DF forest, DFS also time stamps each vertex. Each vertex v had two time stamps. The first time stamp D[v] records when v is first discovered (and grayed). The second time stamp F[v] records when the search finished examining v's adjacency list and blackens v. These time stamps are used in many graph algorithms and are generally useful in reasoning about the behaviour of DFS

The procedure DFS below, records when it discovers vertex u in the variable D[u] and when it finishes vertex u in F[u]. These time stamps are an integer between 1 and 2|V|, since there is one discovery event and one finish event for each of the |V| vertices. For every vertex u, D[u] < F[u]. Vertex u is white before time d[u], gray between time d[u] and f[u], and black thereafter. The following pseudo code is the basic DFS algorithm. The input graph G may be undirected or directed. The variable time is a global varible that we use for time stamping.

DFS(G)

DFS-Visit(u)

Dijkstra's Algorithm

Dijkstra's Algorithm (DA) solves the single source, shortest path problem on a weighted, directed graph G=(V,E) for the case in which all edge weights are non-negative. We assume that w(u,v) >=) for edge (u,v) in E.

DA maintains a set S of vertices whose shortest path weights from the source s have already been determined, that is, for all vertices v in s, we have d[v]=phi(s,v). The algorithm repeatedly selects the u in V-S with the minimum shortest path estimate, inserts U into S, and relaxes all edges leaving U. In the following implimentation, we maintain a priority queue Q that cointains all vertices in V-S, keyed by their d values. The implementation assumes that the graph G is represented by adjacency lists.

DIJKSTRA(G,w,s)

Corman, Thomas H. , Leiserson, Charles E., Rivest, Ronald L., Introduction to Algorithms, (The MIT Press, Cambridge, Massachusett:1990).

Go To: [ Literature ] [ History ] [ Recreation and Games ] [ Algorithms ] [ Art ] [ Home ]