Graph Algorithms

The following materials are notes on graph algorithms. They assume knowledge of basic graph theory.

Introduction
Implementations
Common Problem Patterns
Depth First Search (DFS)

Introduction

Graph algorithms pervade modern life: Maps, web links, circuits, schedules, matching, computer networks, road systems, program structures, company hierarchies, are just a few examples. In fact, trees and linked lists are just graphs. Any connected data structure is the realization of a mathematical graph. The most common graphs in computer science, however, simple graphs.

graph. A graph ${G}$ is a structure ${((V_G, E_G),\df{graph}).}$ The tuple ${(V_G,E_G)}$ is a pair of two sets. The set ${V_G}$ is a set of distinct objects called vertices or nodes, and the set ${E_G \subseteq V_G \times V_G}$ is a set of distinct pairs called edges such that, if ${v \in V_G,}$ then ${(v,v) \notin E_G.}$ For all edges ${(a,b) \in E_G,}$ we may denote an edge with a variable ${e = (a,b)}$ and describe it as, "The edge connecting ${a}$ and ${b.}$ "

Later, we will include more operations (e.g., operations on vertices). Importantly, a practical API would also include some method of removing parallel edges. We will define these operations more elaborately as we proceed. In analyzing graph algorithms, we assume that ${\card{V}/\card{E}}$ — the proportion of vertices to edges for some graph ${G=(V,E)}$ — is bounded above by a some constant ${C \in \reals.}$ For this first section, we'll only be working with sets of edges. An edge is defined as follows.

Implementations

The graph definitions provided previously are abstractions of implementation details. Accordingly, it's at our discretion how the implementation should be handled. For some algorithms, we might want an edge implementation, in which case we will use the following definition.

structure ${\df{edge}}$ contains
1. ${\var}$ ${\tx{head}}$
2. ${\var}$ ${\tx{tail}}$
3. ${\df{new edge}(d_1, d_2):\ar{\var \mapsto \df{edge}}}$
  1. ${\let{out}{\df{malloc}(\df{sizeof}~\df{edge})}}$
  2. ${\let{out[\tx{head}]}{\df{malloc}(\df{sizeof}~d_1)}}$
  3. ${\let{out[\tx{tail}]}{\df{malloc}(\df{sizeof}~d_1)}}$
  4. return ${out}$
end

Adjacency Matrices

One approach is to use an adjacency matrix, a nested Boolean array.

	${b}$	${c}$	${d}$	${e}$
${a}$	1	0	1	1
${b}$	0	1	0	0
${c}$	0	0	1	0
${d}$	0	0	0	1
${e}$	0	0	0	0
${f}$	1	0	0	0

Here, the leftmost column represents the edge sources, and the topmost row represents destinations. The edge ${(d,a),}$ for example, connects vertex ${d}$ (the source) and vertex ${a}$ (the destination), so we mark the corresponding cell as ${1.}$

As is usually the case with nested arrays, there are costs and benefits to this approach. As nested arrays, adjacency matrices are Simple to implement and maintain (and are conducive to linear algebra applications). They're also particularly efficient, compared to other approaches, for dense graphs. Moreover, for weighted graphs, the time complexity of edge weight lookup is ${\bigO{1}.}$ On the other hand, instantiating the structure takes ${(\card V)^2}$ time, and if ${\card V}$ is small enough, memory allocation calls will likely predominate. They also require ${\bigTheta{V^2}}$ space, and iteration takes ${\bigTheta{V^2}}$ time.

Adacency Lists

An alternative approach is to use an adacency list: Use a connected data structure (typically, a hash table), where each key is a node (the source-nodes of an edge), and each value is an array of nodes (the end-nodes of the edges).

{\eqs{ a~&\mapsto~\ix{b,c} \\ \hdashline b~&\mapsto~\ix{c} \\ \hdashline c~&\mapsto~\ix{d} \\ \hdashline d~&\mapsto~\ix{a} \\ }}

For algorithms involving adjacency lists, we will use the structure below.

structure ${\df{graph}}$ contains

variables
1. ${\df{hash-table}:(\var~,\var~\df{array})}$ ${V}$
2. ${\nat}$ ${\tx{order}}$
constructor
1. ${\df{new}\texttt{( )}: \nil \mapsto \df{graph}}$
  1. ${\let{out}{\df{malloc}(\df{sizeof}~\df{graph})}}$
  2. return ${out}$
binary operations
1. init
  1. ${\df{variable}~d,a,b}$
  2. ${\df{graph}~G}$
2. ${G \df{ add-vertex } d}$ add a vertex
  1. ${V\ix{d}=\df{new array}}$
3. ${G \df{ add-edge } (a,b)}$ add an edge
  1. ${V\ix{a} \push b}$
  2. ${V\ix{b} \push a}$
4. ${G \df{ remove-edge } (a,b)}$ remove an edge
  1. if ${a \in V}$ then
    1. ${\let{A}{V\ix{a}}}$
    2. ${\let{L}{\len~V\ix{a}}}$
    3. ${\let{i}{0}}$
    4. while ${i \lt L}$
      1. if ${A \ix{i} = a}$ then ${A \df{ delete } a}$
      2. ${+(i,1)}$
      3. ${\goto{20}}$
  2. if ${b \in V}$ then
    1. ${\let{B}{V\ix{b}}}$
    2. ${\let{L}{\len~V\ix{b}}}$
    3. ${\let{i}{0}}$
    4. while ${i \lt L}$
      1. if ${B \ix{i} = a}$ then ${B \df{ delete } a}$
      2. ${+(i,1)}$
      3. ${\goto{29}}$
5. ${G \df{ remove-vertex } v}$ remove vertex
  1. if ${v \in V}$ then
    1. ${\forall(key,value) \in V}$
      1. if ${v \in value}$ then ${value \df{ delete } v}$
    2. ${V \rid v}$

In general: Adjacency lists are particularly space efficient for for space graphs. On the other hand, they become much less space efficient for denser graphs because of their connected nature. In contrast to the adjacency matrix, iterating over is much faster, but because edges are represented as key-array pairs, we have an edge weight lookup of ${\bigO{E}.}$ Adjacency lists are also slightly more complicated to implement and maintain, and aren't nearly as conducive to linear algebra applications as adjacency matrices.

Edge Lists

Yet another representation is the edge list. This is little more than a list (or array) of edges:

[(a,b), (a,c), (b,c), (c,d), (d,a)].

As we can likely tell, this approach is rarely used in practice. There isn't any notion of ordering, and edge lookup comes at ${\bigO{n}.}$ That said, they're often used as auxiliary data structures for certain algorithms, and we'll seem repeatedly.

Common Problem Patterns

Whenever we work with graphs, we want to always ask the following set of questions:

Is the graph directed or undirected?
Are the edges weighted?
Is the graph sparse or dense?
Should we use an adjacency matrix, adjacency list, edge list, or some other structure?

Additionally, it's helpful to spot some common problem patterns that are squarely in the domain of graph theory.

shortest path problem. Given a graph ${G}$ with vertices ${a}$ and ${b,}$ find the shortest path from ${a}$ to ${b.}$

The shortest path problem is addressed by numerous algorithms. For unweighted graphs, we have breadth-first search and depth-first search. For weighted graphs, we have Dijkstra's Algorithm, A*, the list goes on. All of these algorithms have different tradeoffs. Some problems, however, ask us to just find a path.

connectivity problem. Given a graph ${G}$ with vertices ${a}$ and ${b,}$ is there a path between ${a}$ and ${b?}$

This problem appears benign on its face, until we're asked to find a path between two nodes among millions of interconnections.

negative cycle problem. Given a weighted graph ${G,}$ is there a negative cycle?

A negative cycle occurs when an edge has a negative value. This can lead to wrong computations involving edge weights. This is particularly problematic, given the fact that the results of those computations are often used as intermediary results for other graph algorithms (e.g., a shortest path solution). In other applications, negative cycles are desirable. For example, FOREX trading applications have a particular interest in these cycles, as negative edge weights can be interpreted as measures of risk reduction. To common algorithms for this problem are the Bellman-Ford Algorithm and the Floyd-Warshall Algorithm.

strong-connectivity problem. Let ${D}$ be a directed graph with ${C_0, C_1, \ldots, C_{k-1}}$ self-contained cycles with ${i,k \in \nat.}$ For all self-contained cycles ${C_i,}$ is there directed path from a vertex ${v \in C_i}$ to every other vertex ${w \in C_i?}$

The strong-connectivity problem usually arises as an intermediary problem in implementing some of the algorithms mentioned thus far. Popular solutions include Tarjan's Algorithm and Kosaraju's Algorithm.

traveling salesman problem. Given a weighted graph ${^{w}G = (V,E),}$ what is the shortest Hamiltonian cycle of ${^wG?}$

In plain English: We're given a list of addresses. The addresses are separated by varying distances — some are closer to others, others farther. Our task: Visit every address exactly once, then return to the address we started on. What's the shortest route to accomplishing this task correctly? This problem is NP-hard. Some common algorithms include the Held-Karp Algorithm, Branch-and-bound, and many approximation algorithms.

edge-cutting problem. Let ${i, n, k \in \nat,}$ where ${n \lt k,}$ and a graph ${G = (V,E)}$ with ${n}$ connected components. Suppose ${E = \set{e_1, e_2, \ldots, e_n}}$ and that ${E \smallsetminus \set{e_i}}$ implies ${n \gt k.}$ What is the value of ${i?}$

vertex-cutting problem. Let ${i, n, k \in \nat,}$ where ${n \lt k,}$ and a graph ${G = (V,E)}$ with ${n}$ connected components. Suppose ${V = \set{v_1, v_2, \ldots, v_n}}$ and that ${V \smallsetminus \set{v_i}}$ implies ${n \gt k.}$ What is the value of ${i?}$

When we remove an edge from some graph ${G,}$ we potentially end up with two or more connected components of ${G.}$ The edge-cutting problem asks which edge, when removed, causes the number of connected components to increase beyond some tolerance maximum ${k \in \nat.}$ Edges that causes this increase are called bridges.

The vertex-cutting problem is similar to the edge-cutting problem, but the focus here is on cutting edges. The question then, is, which vertex, if cut, would cause an increase to the tolerance maximum ${k?}$ Vertices that cause these increases are called articulation points. Both the edge- and vertex-cutting problems are particularly important because they reveal bottlenecks and vulnerabilities in a given graph.

minimum spanning tree problem. Let ${W = (V,E)}$ be a weighted graph with a total edge weight ${T.}$ Let ${S = \set{w_1, w_2, \ldots, w_n,}}$ be a set of graphs such that for all ${i,n \in \nat:i \le n,}$ each ${w_i}$ is a graph with the vertex set ${v_i = V}$ and an edge set ${e_i \subseteq E}$ and a total edge weight ${t_i.}$ Construct the graph ${w_i \in S}$ such that ${t_i = \min\set{t_1, t_2, \ldots, t_n}.}$

In plain English: We're given a weighted graph ${W.}$ We want to create a version of ${W}$ that includes all its vertices, but with the smallest possible total weight (the sum of all the edge weights in ${W}$ ). Common algorithms for this problem include Kruskal's Algorithm, Prim's Algorithm, and Boruvka's Algorithm.

Depth First Search (DFS)

Depth First Search (DFS) is an algorithm for traversing a graph's nodes and edges. The algorithm has a time complexity of order ${\bigO{V+E}.}$ The algorithm itself is often used as an auxiliary, so it's often used on its own. Instead, it's often augmented to another algorithm — searching, counting, deleting, etc. The name "depth first" comes from the algorithm plunging into a graph without regard to which edge it traverses next. It's primary driver is a check: Has this node been visited? If the node has been visited, the algorithm backtracks.

For tracking, we'll fill in the node we're currently on green. After a node is visited, we'll fill the visited node grey. First, we pick any node to start. This is where the name depth first comes from: We plunge into a graph without regard of where we might go next. Here, we'll start with the node ${\set{0}.}$
We mark ${\set{0}}$ visited, and plunge. There's only one option, ${\set{9},}$ so we visit this node next.
Mark ${\set{9}}$ visited and plunge. We only have one option again, so visit ${\set{8}.}$
Now we have two options, ${\set{1}}$ and ${\set{8}.}$ Again — plunge. It doesn't matter which node we visit. We just dive into the deep end. We'll take ${\set{7}}$ purely for illustrative purposes.
At ${\set{7},}$ we have many options, but again, we pick arbitrarily. We'll choose ${\set{10}.}$
We only have one option, ${\set{11},}$ so we go there.
This is where things get interesting. We only have one option, ${\set{7}.}$ But remember, we don't want to "revisit" nodes. So, we backtrack to ${\set{7}.}$ To denote backtracking, we'll fill the nodes beige and the edges red. Backtracking to 7, we still have edges to choose.
Back at 7, we still have edges to choose. We pick ${\set{3}.}$
We pick another node arbitrarily. We'll go ${\set{2}.}$
We hit a deadend, so we backtrack to ${\set{3}}$ and pick another node. We only have one option, ${\set{5},}$ so we visit that node.
Now visit ${\set{6}.}$
We can't visit ${\set{7}}$ since we've already visited that node, so we backtrack to ${\set{8}.}$ Once we're there, the only node we can visit is ${\set{1}.}$ Visting that node, we've traversed the entire graph.

Below are two possible implementations of DFS, one recursive, the other iterative.

rdfs

Input: a graph ${\G,}$ a vertex ${\v,}$ and a function ${\f}$ operating on ${\v.}$
Output: the graph ${G}$

${\let{visited}{\set{~}}}$
function ${\lambda(v)}$
1. if ${v = \nil}$ return ${\nil}$
2. ${\let{visited \ix{v}}{1}}$
3. ${\f(v)}$
4. foreach ${neighbor \in G\ix{V}\ix{v}}$
  1. if ${visited \ix{neighbor}}$ then
    1. return ${\lambda(neighbor)}$
return ${\lambda(\v)}$

idfs

Input: a graph ${\G,}$ a vertex ${\v,}$ and a function ${\f}$ operating on ${\v.}$
Output: the graph ${G}$

init
1. ${\let{stack}{\df{new stack}}}$
2. ${\let{visited}{\set{~}}}$
3. ${\let{visited\ix{\v}}{1}}$
4. ${\let{v_c}{\nil}}$ current vertex
while ${stack \neq \nil}$
1. ${\let{v_c}{\df{pop}~stack}}$
2. ${\f(v_c)}$
3. foreach ${neighbor \in G\ix{V}\ix{v_c}}$
  1. if ${visited \ix{neighbor}=0}$ then
    1. ${\let{visited\ix{neighbor}}{1}}$
    2. ${stack ~\df{push}~ neighbor}$
return ${\lambda(\v)}$