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!

Tags

Graphs , Data Structures , Algorithms , Interviews , Javascript , Breadth First Search , BFS

About the author
comments powered by Disqus