ICS 161: Design and Analysis of Algorithms
Lecture notes for February 1, 1996


Graph algorithms

What is a graph?

It's an abstract notion, used to represent the idea of some kind of connection between pairs of objects. A graph consists of:

For this definition it doesn't matter what the vertices or edges represent -- that will be different depending on what application the graph comes from. It also doesn't matter how I draw the graph, the only part that matters is which pairs of vertices are connected with each other.

There are two different types of graph that we'll commonly see.

Whenever we talk about graphs, we'll use n to denote the number of vertices, and m to denote the number of edges. This notation is confusing, but I'll stick with it because it's very standard. We'll also use V(G) to denote the set of vertices of a graph G, and E(G) to denote the set of edges.

Some more examples of graphs

As we have seen, all of these many problems can be reformulated as graph problems. This hides the unnecessary complications of the problem, making the important structure more obvious and making it easier to find a solution. Translation to a graph problem also has the advantaged that several different real world problems could end up looking like the same graph problem, so finding a good algorithm for that one problem could have many applications.

Representation of Graphs

In order to perform graph algorithms in a computer, we have to decide how to store the graph. When I talk about graphs to you, I'll draw a diagram with circles and lines on the blackboard, but computers aren't very good at interpreting that sort of input. Instead we need a representation closer to the abstract definition of a graph. There are several possibilities, with different uses. I didn't go over all of them in the lecture (I left out the incidence list and incidence matrix.)

Connectivity

As a warmup to graph algorithms, we'll start with a simple problem: is a graph connected? Is there always an airline route from A to B? Is everyone in the family tree related to everyone else? Can your scheduling task be split into two parts that can be done by different departments of your company?

As a rough outline, we start with some vertex x, and build a list of the vertices you can get to from x. Each time we find a new vertex to be added to this list, we check its neighbors to see if they should be added as well. Finally, we check whether the list covers the whole graph. In pseudocode:

    test-connected(G)
    {
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
        find and remove some vertex y in K
        for each edge (y,z)
            if (z is not in L)
            add z to both L and K

    if L has fewer than n items
        return disconnected
    else return connected
    }
To analyze the algorithm, first notice that the outer loop happens n times (once per vertex). The time for the inner loop (finding all unreached neighbors) is more complicated, and depends on the graph representation. One key step (testing whether z is in L) seems like it might be slow, but can be done quickly by keeping a bit on each vertex that says whether it's in L or not. At the end of the algorithm, the list L tells you one connected component of the graph (how much of the graph can be reached from x). With some more care, we can find all components of G rather than just one component.

If graph is connected, we can modify the algorithm to find a tree in G covering all vertices (a spanning tree): For each z, let parent(z) be the vertex y corresponding to the time at which we added z to L. This gives a graph in which each vertex except x is connected to some previous vertex, and any such graph must be a tree.

When analyzing the algorithm, we didn't pay attention to what order we put vertices into K and removed them again, but different orders produce different trees. If we put vertices at end of K, take them off front (so K acts like a queue) we get "breadth first search". Then the parent of z is always as close to x as possible so this gives shortest paths from x to everything else, and the tree is short and bushy. If instead we add and remove vertices at the same end of K (so K acts like a stack) we get "depth first search". This tends to produce long stringy spanning trees with some useful properties that we'll see later.


ICS 161 -- Dept. Information & Computer Science -- UC Irvine
Last update: