Posted by: atri | October 7, 2009

## Lect 14: Implementing BFS

(Guest post by Matthew General)

First a recap of BFS:

A BFS run

1. $L_0 = \{s\}$
2. Assume $L_0,\dots,L_j$ have been constructed. $L_{j+1}$ set of vertices not chosen yet but are connected to $L_j$ [by an edge–Atri]
3. Stop when $L_{j+1}$ is an empty set

Some conclusions about a BFS tree:

• Everything in BFS tree has a path to first node
• Undrawn connections in BFS tree are on same layer or adjacent layer

Recap of DFS:

DFS is recursive, start with $u$ and then work on each adjacent node from there

$\mathrm{DFS}(u)$

1. $u$ is explored
2. For every unexplored neighbor $v$ of $u$ $\mathrm{DFS}(v)$

Some conclusions about a DFS tree:

• DFS tree branches after backing up when an end was reached

DFS computes exactly the connected component

Graph representations:

$n$ rows and $n$ columns, $n$ are the number of vertices

• $1$‘s where nodes are connected, $0$‘s if not connected.
 blue green red b 0 1 1 g 1 0 0 r 1 0 0

Undirected graph’s  [adjanceny matrix] will be symetric, while Directed graphs possibly are not.

• Array of pointers corresponding to a link list of neighbors

b $\to$ g, r
g $\to$  b
r $\to$ b

For every vertex you have a list of all the vertecies that are connected

 Adjacency matrix Adjacency list Constant time $(u,v)$ in $E$? $O(n)$ [ $O(n_v)$ ] $O(n)$ all neighbors of $u$? $O(n_u)$ $O(n^2)$ space? $O(m+n)$

We’ll use adjacency list [as they are–Atri] better for iterating over adjacent nodes

Claim:

$\sum_{w \in V} n_w = 2m$, where $n_w$ is the degree of $w$, where degree is the number of adjacent nodes.

Proof idea:
count indirectly the number of edges.

Proof details:
Counting the number of neighbors a node has for every $w \in V$, $w$ gives $$1$ to each of the $n_w$ adjacent edges $u_1$ through $u_{n_w}$. $w$ gives one dollar, $u_1$ gives one dollar implies that every edge has$$2$.

$\sum_{w e\in V} n_w$ = total $that vertices have = total$ that all edges have = $2m$ where $m$ is the number of edges

[Next, we moved on to an implementation of the BFS algorithm.–Atri]

1. Array Discovered ; Discovered[$u$] = T implies that $u$ has been processed
2. Build $L_i$ as a list.

$\mathrm{BFS}(u)$

1. Discovered[$u$] =T, Discovered[$w$]=F every $w \neq u$
2. Set $i=0$
3. $L_0 = \{u\}$
4. While $L_i \neq\emptyset$
• $L_{i+1} = \emptyset$
• For every $u$ element of $L_i$
1. consider every edge $(u,v)$
2. if Discovered[$u$]=F
• Add $v$ to $L_{i+1}$
• Discovered[$u$]=F
• $i=i+1$

Lecture ended at this point.