*(Guest post by Matthew General)*

First a recap of BFS:

A BFS run

- Assume have been constructed. set of vertices not chosen yet but are connected to
*[by an edge–Atri]* - Stop when 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 and then work on each adjacent node from there

- is explored
- For every unexplored neighbor of

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*

rows and columns, are the number of vertices

- ‘s where nodes are connected, ‘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 g, r

g b

r 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 | in ? | [ ] |

all neighbors of ? | ||

space? |

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

**Claim:**

, where is the degree of , 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 , gives $ to each of the adjacent edges through . gives one dollar, gives one dollar implies that every edge has $.

= total $ that vertices have = total $ that all edges have = where is the number of edges

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

- Array Discovered ; Discovered[] = T implies that has been processed
- Build as a list.

- Discovered[] =T, Discovered[]=F every
- Set
- While
- For every element of
- consider every edge
- if Discovered[]=F
- Add to
- Discovered[]=F

- For every element of

Lecture ended at this point.

## Leave a Reply