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:

Adjacency matrix

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.

Adjacency List

  • 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

We asked some questions about Adjacency matrices and Adjacency Lists:

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: