**
**

**Breadth-first search: the basic algorithm**
Given a graph with N vertices and a selected vertex A:

**for(i = 1; there are unvisited vertices ; i++)**

Visit all unvisited vertices at distance **i**

(**i** is the length of the shortest path between A and currently processed vertices)
As we saw, the algorithm for single source shortest path uses breadth-first search

For a graph with N vertices the shortest path between two vertices can be

at most N-1.
The search is implemented by storing the neighbors in a queue.

**BFS algorithm**

1. Store source vertex S in a queue and mark as processed

2. While queue is not empty

Read vertex v from the queue

For all neighbors **w**:

If **w** is not processed

Mark as processed

Append in the queue

Record the parent of **w** to be **v**

(parent is necessary only if we need the shortest path tree)
We can use a distance table to mark vertices as processed by storing
the distance to the source vertex.

**Adjacency lists**

A: B, C, E

B: A, C, E

C: A, B, D

D: C, E

E: A, E

Let's select A as the starting node.

Distance table:

1. After reading A from the queue and processing its neighbors:

2. Read B. Its neighbors are A, C and E. All are processed.

3. Read C. Its neighbors are A, B and D. A and B are processed. D is not.
After processing D we have;

4. Read E. Its neighbors are processed

5. Read D. Its neighbors are processed

The queue is empty and the algorithm ends.

The table defines the shortest path tree, rooted at A.

**
**

**Complexity of the BFS algorithm**
Consider the algorithm’s basic loop:

While queue is not empty:

1. Read vertex **v** from the queue

2. For all neighbors **w**:

If **w** is not processed

Mark **w** as processed

Append **w** in the queue
In step 1 we read a node from the queue.
The question to be answered is: how many nodes are stored in the queue?
The answer is: each node is stored only once – if it is not processed.
Thus the reading step will be performed O(V) times,
where V is the number of the nodes in the graph.

In step 2 we examine all neighbors, i.e. we examine all edges of the
currently read node.
Since the graph is not oriented, we will examine 2*E edges,
where E is the number of the edges in the graph.

Hence the complexity of BFS is O(V + 2*E)

If we use adjacency matrix instead of adjacency lists, the complexity will
be O(V^{2})

**Attention:** a typical error in determining the complexity
is to multiply the number of the nodes by the number of the edges.
Why we should not multiply the number of the edges by the number of the nodes?

**
**

**Relation between DFS and BFS**
BFS and DFS are very closely related to each other.
The difference is that BFS uses a queue while DFS uses a stack. Queues can
be described as lists where we write at the end and read from the beginning.
Stacks can be described as lists where we write at the end and read from
the end. Thus we can describe BFS and DFS in the following way:

bfs(G)
list L = empty
tree T = empty
choose a starting vertex x
visit(x)
while(L nonempty)
remove edge (v,w) from beginning of L
if w not visited
add (v,w) to T
visit(w)
dfs(G)
list L = empty
tree T = empty
choose a starting vertex x
visit(x)
while(L nonempty)
remove edge (v,w) from end of L
if w not visited
add (v,w) to T
visit(w)
visit(vertex v)
mark v as visited
for each edge (v,w)
add edge (v,w) to end of L