Graphs

We can represent a graph by an adjacency matrix; if there are \(n = |V|\) vertices \(v_1,...,v_n\), this is an \(nxn\) array whose \((i, j)\) th entry is:

For undirected graphs, the matrix is symmetric since an edge \(\{u, v\}\) can be taken in either direction.

Here's the adjacency matrix for the graph above:

The biggest convenience of this format is that the presence of a particular edge can be checked in constant time, with just one memory access. On the other hand the matrix takes up \(O(|V|^2)\) space, which is wasteful if the graph does not have very many edges.

An alternative representation to the adjacency matrix, with size proportional to the number of edges, is the adjacency list. It consists of \(|V|\) linked lists, one per vertex. The linked list for vertex \(u\) holds the names of vertices to which \(u\) has an outgoing edge - that is, vertices \(v\) for which \((u, v) \in E\). Therefore, each edge appears in exactly one of the linked lists if the graph is directed or two of the lists if the graph is undirected. Either way, the total size of the data structure is \(O(|E|)\). Checking for a particular edge \((u, v)\) is no longer constant time, because it requires sifting through \(u\)'s adjacency list. But it is easy to iterate through all neighbors of a vertex (by running down the corresponding linked list), and, as we shall soon see, this turns out to be a very useful operation in graph algorithms. Again, for undirected graphs, this representation has a symmetry of sorts: \(v\) is in \(u\)'s adjacency list if and only if \(u\) is in \(v\)'s adjacency list.

Which of the two representations is better? Well, it depends on the relationship between \(|V|\), the number of nodes in the graph, and \(|E|\), the number of edges. \(|E|\) can be as small as \(|V|\) (if it gets much smaller, then the graph degenerates - for example, has isolated vertices), or as large as \(|V|^2\) (when all possible edges are present). When \(|E|\) is close to the upper limit of this range, we call the graph dense. At the other extreme, if \(|E|\) is close to \(|V|\), the graph is sparse. Exactly where \(|E|\) lies in this range is usually a crucial factor in selecting the right graph algorithm.

The basic breadth-first search algorithm is given below. The algorithm explores wide before going deep; we look at each child before looking at any of the children's children. BFS takes \(O(n + m)\) time.

def bfs(graph, root):
    parent = {}
    discovered = {root}
    queue = [root]
    while queue:
        current = queue.pop(0)
        for neighbor in get_adjacent(current, graph):
            if neighbor not in discovered:
                parent[neighbor] = current
                discovered.add(neighbor)
                queue.append(neighbor)

Note that to search an entire graph one would need to apply this function to each vertex in the graph.

In this implementation of breadth-first search, we assign a direction to each edge, from the discoverer current to the discovered neighbor. We maintain a parent map which defines a tree on the vertices of the graph. This tree contains the shortest path from the root to every other node in the tree. A breadth-first search tree can be seen in the right of the image below.

The graph edges that do not appear in the breadth-first search tree also have special properties. For undirected graphs, non-tree edges can point only to vertices on the same level as the parent vertex, or to vertices on the level directly below the parent. These properties follow easily from the fact that each path in the tree must be the shortest path in the graph.

The difference between BFS and DFS results is in the order in which they explore vertices. This order depends completely upon the container data structure used to store the unprocessed vertices: BFS uses a queue, DFS uses a stack. DFS implementations often use recursion instead of an explicit stack. Depth-first search explores deep before going wide; the algorithm looks at the entirety of a child before moving to the next child.

def dfs(root, graph):
    discovered = set()
    parent = {}

    def search(node):
        discovered.add(node)
        for neighbor in get_adjacent(node, graph):
            if neighbor not in discovered:
                parent[neighbor] = root
                dfs(neighbor, graph)

    search(root)

Note that some implementations of depth-first search also maintain the traversal time for each vertex. A time clock ticks each time we enter or exit any vertex. entry_time and exit_time dictionaries go from node -> time. The time intervals can tell us a vertex's ancestor and how many descendants it has.

Depth-first search partitions the edges of an undirected graph into exactly two classes: tree edges and back edges. The tree edges discover new vertices, and are those encoding in the parent relation (seen in the image above). Back edges are those whose other endpoint is an ancestor of the vertex being expanded, so they point back into the tree.