**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)

- d[u] <-- infinity

pi[u] <-- nil

d[s] <-- 0

pi[s] <-- nil

Q <-- {s}

- d[v] <-- d[u] + 1

pi[v] <-- u

EnQueue(Q,v)

color[u] <-- black

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 **DFS**may 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)

- pi[u] <-- nil

DFS-Visit(u)

- color[u] <-- Gray

d[u] <-- time <-- time+1

- DFS-Vistit(v)

f[u] <-- time <-- time +1

**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)

- INITIALIZE-SINGLE-SOURCE(G,s)

S <-- empty set

Q <-- V[G]

- S <-- S union {u}

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 ]