#### Adjacency matrix

What the hell is that, you ask? Well it's one way to organize a graph and the title is quite descriptive. Below, we have our previously filled in graph and below that is our filled in adjacency matrix!

As you can see, the matrix is filled in with X's where they are adjacent, some rows/columsn have multiple X's because those vertices are adjacent to multiple other vertices. You will also notice that our lovely adjacency matrix is symmetric! This is a characteristic of undirected graphs and their corresponding matrices. For the astute (and math lovers), this graph has a lot of empty space, which is termed *sparse*, and storing a sparse matrix can be complicated in some languages. Not cool/awesome/sexy enough for you?

#### Adjacency list

For the sake of spatial complexity, lets jump into adjacency lists. Below is something I copied from MIT's Introduction to Algorithms course taught by Erik Demaine, this specific information is in the lecture notes for lecture 15.

We can see that the example graph is a directed graph with 3 vertices and 4 edges. The corresponding adjacency list is to the right and is stored in a format very similar to an array and storing pointers to adjacent vertices.

Now, let's picture a Javascript array with length 8, storing all of our vertices. Each vertex can be represented as an object with key/value pairs storing the vertex name, weight, and object containing references to adjacent vertices. That was probably confusing so let me write out an example vertex object in Javascript below,

```
var v0 = {
id: v0,
adjacent: {
v1,
v4
}
}
```

Adjacency lists can also just be nested arrays.

#### Time complexity

Big-Oh for graph traversal using BFS is *O(|V| + |E|)*. We can see that this is true because through the entire traversal of the graph, each vertex is only visited once, that is guaranteed by the use of the queue. For each vertex, we can each edge only once as well, thus the combination of the two gives us our time complexity in a nested while loop.

#### Pseudocode

While we pretty much already ran through this in the previous article, I'll sketch out a very basic pseudocoded BFS,

```
For a graph G and origin v
let Q be a queue data structure
Q.enqueue(v)
mark v as found
while Q is not empty
set v to equal Q.dequeue
for all adjacent edges in v, e
if e not marked as found
Q.enqueue(e)
mark e as found
```

Well, that's it for breadth-first search analysis, here are some links for your traversal if you want more!

- Excellent description and python implementation from Brad Miller and David Ranum
- Introduction tutorial from Khan Academy
- Lecture notes for MIT's Introduction to Algorithms course, BFS lecture
- Note there are lecture videos for this one, woo!