Representation

Last time, we learned about adjacency lists, and adjacency matrices. Obviously, there must be pros and cons to each of these. Let's call the number of vertices \(n\), and the number of edges \(m\).

Graph Search

In graph search, we want to know, given a graph G, and two nodes v1 and v2, what is a path from v1 to v2? We can answer this question in different ways depending on our graph, and what we want from our answer. If we have an unweighted graph, and we want the shortest path, then we use Breadth-First Search (BFS). You already know BFS! Here's the explanation copy-pasted over from the IC211 project WordGraph:

Our algorithm is:

  1. Add our first node to the list, and mark it "visited."
  2. Remove the first node in the Queue (we'll call it Node A), and, for each node connected to A that has not already been marked "visited:"
    1. Note that its "parent" is Node A.
    2. Check to see if it is our target node. If so, we can traverse the "parent" pointers back to our starting node to reveal the path.
    3. Mark it as "visited."
    4. Add it to the Queue.
  3. Repeat step 2, unless the Queue is empty, in which case no path exists.

Helpful pictures of this happening can be found at the old WordGraph page.

Essentially, this works by adding all vertices that are one step away from v1 to the queue, then all the vertices two steps away, then three.

So, what does BFS guarantee us? Well, first, the only thing that causes this to stop, is we either find v2, or we run out of connected, unvisited vertices. So, if a path exists (if v2 is connected to v1), then we are guaranteed to find it. Additionally, because all vertices that can be reached in \(k\) steps are added before any vertices that can only be reached in \(k+1\) steps are added, the path we find will be the shortest such path that exists. Cool!

Let's try something crazy. Let's replace the Queue with a Stack. What will happen? Well, we're still guaranteed to find a path if it exists. However, we no longer visit all vertices \(k\) steps away before we visit some that are \(k+1\) steps away. So, the path we find will no longer be the shortest possible. Because you go deep in the graph rather than going wide on the graph, this is called Depth-First Search (DFS).

Credit Randall Munroe, XKCD.com

It's worth noting that this doesn't change if we're looking at a directed graph; BFS and DFS are exactly the same.

Graph Search on a Weighted Graph (Dijkstra's Algorithm)

BFS and DFS are well and good if each edge is created equal, that is, we have no preference between going down any edge over any other edge. In a weighted graph, this may not be true.

Consider the following graph. Here, the vertices may be intersections, and the edges may be roads, with expected time to travel as the weights.

Let's consider the problem of finding the fastest route from vertex A to vertex H. Let's augment our vertices so they contain three additional pieces of information: their parent, the fastest time to that vertex discovered so far, and whether they are unvisited, visited, or finished. We'll call "unvisited, visited, or finished" its status. So, our graph now looks like this (we'll shape it as a rectangle to indicate it has been visited, and red to indicate it has been finished):

Essentially, we're going to replace the Queue from BFS with a Priority Queue, which will return to us the vertex with the smallest value in the "time" field. Let's also modify our Priority Queue, so in addition to insert and getMin, it also has a "changePriority function. Adding this to a PQ implemented with a heap isn't difficult; if each vertex stores where in the heap it is, then changing the priority and bubbling as appropriate is easy and \(O(\log(n))\).

A status of "unvisited" will mean it has not yet been added to the PQ, a status of "visited" will mean it is currently in the PQ, and a status of "finished" will mean it has been returned by the PQ. The algorithm looks like this:

Dijkstras(G,v1,v2) //Given a graph G and a start vertex v1, return a path to v2
  PriorityQueue pq = new PriorityQueue();
  v1.time = 0; //No time to go from v1 to v1
  v1.status = visited; //add it to the PQ
  pq.insert(0, v1);
  while pq.size() > 0 { //While there's still something in the PQ,
    Vertex v = pq.getMin(); //Get the vertex in the PQ with the smallest 
                            //"time from v1" field
    v.status = finished;
    if v==v2 //found it!
      return buildPath(v2);
      //buildPath starts at v2, and walks the parent pointers back, returning
      //the path
    List incidentEdges = G.incidentEdges(v); //get all edges eminating from v
    foreach e in incidentEdges { //for each edge connected to v,
      Vertex oppV = the vertex connected to v by e; //get the one it connects to v
      if (oppV.status == unvisited)
        oppV.parent = v;
        oppV.time = v.time + e.weight; //This is the fastest time to oppV
                                       //discovered so far
        oppV.status = visited;
        pq.insert(oppV.time, oppV);
      //else, if it is currently in the PQ, but this is now a faster way,
      else if (oppV.status == visited && oppV.time > v.time+e.weight)
        oppV.parent = v; //change its parent
        oppV.time = v.time+e.weight; //update its time to the faster route
        pq.changePriority(oppV.time, oppV); //update pq to reflect changed priority
      else
        //do nothing with oppV
    }
  }
  //Here, we finished without finding v2
  throw new Exception("no path exists");

Let's walk it through. First, we set A's time to 0, and add it to the PQ. We then start the loop, removing A from the PQ, and marking it finished:

We then get all vertices incident to A, calling them oppV, in turn. We update their time to A's time plus the weight of the edge connecting them, and add them to the PQ.

We then pop the PQ, getting back vertex B. The vertices incident to B are A, C, D, and G. For each of them, the following happens:

That gives us the following:

We then pop the PQ, getting back vertex C. The vertices incident to C are A, B, D, and E. For each of them, the following happens:

That gives us the following:

We then pop the PQ, getting back vertex D. The vertices incident to D are B, C, and E. For each of them, the following happens:

That gives us the following:

We then pop the PQ, getting back vertex E. The vertices incident to E are C, D, and F. For each of them, the following happens:

That gives us the following:

We then pop the PQ, getting back vertex F. The vertices incident to F are E and G. For each of them, the following happens:

That gives us the following:

We then pop the PQ, getting back vertex G. The vertices incident to G are B, F, I, and H. For each of them, the following happens:

That gives us the following:

We then pop the PQ, getting back vertex I. The vertices incident to I are G and H. For each of them, the following happens:

That gives us the following:

We then pop the PQ, getting back vertex H. This was our target. So, we walk back the parent pointers, and discover our path was A,B,D,E,F,G,I,H, and it will take 21 units of time.

Dijkstra's Runtime

How long does Dijkstra's take? Well, it depends upon what data structure we use to implement our Priority Queue. We probably like heaps best, so we'll start by looking at that. Let's say we have \(n\) vertices, and \(m\) edges. We have the following steps to sum up for each time through the for loop:

So, each pass through the for loop is \(O(\log(n))\). The for loop runs once for each edge, so that loop, in total, is \(O(m\log(n))\).

In addition, we have the stuff inside the while loop, but outside the for loop; this is \(n\) getMins, so \(O(n\log(n))\).

So, in total, \(O(n\log(n) + m\log(n))\). In a connected graph, \(m\geq n-1\) (see why?), so we can just call this \(O(m\log(n))\).

OK. What else could we use to implement a PQ. Well, what if we used an unsorted linked list? That's always been stupid, but a good exercise. Let's see if that remains true (it doesn't).

In an unsorted linked list, since we're not maintaining the ordering, doing the delete-then-insert can take the form of just changing the parent and time values, which is \(O(1)\). There are \(m\) of those, making the stuff in the for loop happen in \(O(m)\) time. Now, things inside the while loop but outside the for loop, is a getMin() happening n times: \(O(n^2)\), because each getMin() is now \(O(n)\).

So, the total runtime for this with PQ implemented with an unsorted linked list is \(O(n^2+m)\).

So, we need to decide which is faster, \(O(n^2 + m)\), or \(O(m\log(n))\). In a dense graph, \(m \approx n^2\), making the comparison between \(O(n^2)\) or \(O(n^2\log(n))\). The unsorted list is actually faster! In a sparse graph, \(m \approx n\), making the comparison between \(O(n^2)\) or \(O(n\log(n))\). In this case, the heap is faster.