In this chapter, we will introduce the basic definitions surrounding graphs, and list a spectrum of different algorithmic settings where graphs arise naturally. We will then discuss some basic algorithmic primitives for graphs, beginning with the problem of connectivity and developing some fundamental graph search techniques.
A graph consists of a collection V of nodes (or vertices) and a collection E of edges, each of which “joins” two of the nodes. We thus represent an edge e ∈ E as a two-element subset of V: e = {u, v} for some u, v ∈ V, where we call u and v the ends of e.
A directed graph G’ consists of a set of nodes V and a set of directed edges E’, where each e’ ∈ E’ is an ordered pair (u, v). By contrast, an undirected graph is one in which the roles of u and v in a pair (u, v) for an edge e are interchangeable.
Some well known examples of applications of graphs are given below:
A path in an undirected graph G = (V, E) is defined to be a sequence P of nodes v_1, v_2, … , v_k-1, v_k with the property that each consecutive pair v_i, v_i+1 is joined by an edge in G.
A path is called simple if all its nodes are distinct from one another.
A cycle is a path v_1, v_2, … , v_k-l, v_k in which k > 2, the first k-1 nodes are all distinct, and v_1 = v_k. In other words, the sequence of nodes “cycles back” to where it began.
We say a graph is connected if, for every pair of nodes u and v, there is a path from u to v.
An undirected graph is a tree if it is connected and does not contain a cycle. We say that, for nodes v and w, w is a descendant of v (or v is an ancestor of w) if v lies on the path from the root node to w; and we say that a node is a leaf if it has no descendants.
Important to note: every tree with n nodes that exactly n-1 edges. Any less than n-1 edges and the graph will no longer be a tree, and any more than n-1 edges the graph will contain a cycle.
The following theorem is true:
Let G be an undirected graph with n nodes. Any two of the following statements implies the remaining third: - G is connected. - G does not contain a cycle. - G has n-1 edges.
For me, this section was mostly review from CSCI-112, and from a high school Computer Science class. It was very easy to read and comprehend, but not particularly interesting, since it is basically just facts about trees–something that I already knew. That said, I did find the use of graphs in social networks kind of interesting, because I had never thought about graphs that way before.
In this section, we describe two natural algorithms for the node-to-node connectivity problem at a high level: breadth-first search (BFS) and depth-first search (DFS).
In breadth-first search, we explore outward from starting node s in all possible directions, adding nodes one “layer” at a time. Thus we start with s and include all nodes that are joined by an edge to s–this is the first layer of the search. We then include all additional nodes that are joined by an edge to any node in the first layer–this is the second layer. We continue in this way until no new nodes are encountered.
For each j ≥ 1, layer L_j produced by BFS consists of all nodes at distance exactly j from s. There is a path from s to t if and only if t appears in some layer.
BFS has the natural property of producing trees that are bushier and branched out.
In depth-first search, we start from s and try the first edge leading out of it, to a node v. We then follow the first edge leading out of u, and continue in this way until we reached a “dead end”–a node for which we had already explored all its neighbors. We then backtrack until we get to a node with an unexplored neighbor, and resume from there. This algorithm is called depth-first search since it explores G by going as deeply as possible and only retreating when necessary.
The algorithm for DFS is relatively simple and straight-forward:
DFS(u):
Mark u as "Explored" and add u to R
For each edge (u,v) incident to u
If v is not marked "Explored" then
Recursively invoke DFS(v)
Endif
Endfor
While DFS ultimately visits exactly the same set of nodes as BFS, it typically does so in a very different order: it probes its way down long paths, potentially getting very far from s, before backing up to try nearer unexplored nodes. As such, it produces trees that are deep and narrow, as opposed to the trees produced by BFS which are bushy and branched out.
This section was also part review from CSCI112, where we discussed breadth-first and depth-first graph traversals superficially. The section was, however, much more detailed than what we did in CSCI112. The book did a good job with tree diagrams explaining the algorithms for the traversals step-by-step–it made understanding the underlying concepts very easy (not to mention the fact that we have discussed the algorithms in detail in class). I'd say that this section was easy to comprehend, and relatively interesting as well.
There are two basic ways to represent graphs: by an adjacency matrix and by an adjacency list representation.
A graph G = (V, E) has two natural input parameters, the number of nodes |V|, and the number of edges |E|. We will use n = |V| and m = |E| to denote these, respectively. Running times will be given in terms of both of these two parameters. In this section, we aim to implement the basic graph search algorithms in time O(m+n), which we will refer to as linear time.
For a graph G = (V, E) with n nodes, assuming that the set of nodes is V = {1 ….. n}, we can represent the graph as an adjacency matrix, which is an n×n matrix A where A[u,v] = 1 if there is an edge between u and v, and A[u,v] = 0 otherwise. The adjacency matrix representation allows us to check in O(1) time if a given edge (u, v) is present in the graph. However, the representation takes Θ(n^2) space.
On the other hand, we could also represent the graph using the adjacency list representation. In the adjacency list representation, there is a record for each node v, containing a list of the nodes to which v has edges. To be precise, we have an array Adj, where Adj[v] is a record containing a list of all nodes adjacent to node v. For an undirected graph G = (V, E), each edge e = (v, w) ∈ E occurs on two adjacency lists: node w appears on the list for node v, and node v appears on the list for node w.
While an adjacency matrix requires O(n^2) space (since it uses an n×n matrix), the adjacency list representation requires only O(m+n) space. In the adjacency list representation, checking if a given edge (u, v) is present in the graph can take time proportional to the degree O(n_v): we have to follow the pointers on u’s adjacency list to see if edge v occurs on the list.
The following is an algorithm that implements BFS:
BFS(s):
Set Discovered[s] = true and Discovered[v] = false for all other v
Initialize L[0] to consist of the single element s
Set the layer counter i=0
Set the current BFS tree T=0
While L[i] is not empty
Initialize an empty list L[i+1]
For each node u ∈ L[i]
Consider each edge (u, v) incident to u
If Discovered[v] = false then
Set Discovered[v] = true
Add edge (u, v) to the tree T
Add v to the list L[i+1]
Endif
Endfor
Increment the layer counter i by one
Endwhile
The above implementation of the BFS algorithm runs in time O(m+n) (i.e., linear in the input size), if the graph is given by the adjacency list representation. (Detailed proof on page 91 of the textbook.)
The following algorithm implements BFS:
DFS(s):
Initialize S to be a stack with one element s
While S is not empty
Take a node u from S
If Explored[u] = false then
Set Explored[u] = true
For each edge (u, v) incident to u
Add v to the stack S
Endfor
Endif
Endwhile
The above implementation of the DFS algorithm runs in time O(m+n) (i.e., linear in the input size), if the graph is given by the adjacency list representation. (Detailed proof on page 94 of the textbook.)
This section was a relatively interesting read. I found myself struggling with the notion of O(m+n) initially–even after discussing it in class. Going back and reading the section made much more sense after in-class discussion. I guess I've never had to deal with two variables in terms of the input in order to determine the big-O, which made getting used to the idea a bit more challenging. That said, it does seem intuitive now that I have read this section a couple of times and we have discussed the concept in detail in class.
A bipartite graph is one where the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y. For ease of understanding, we can imagine that the nodes in the set X are colored red, and the nodes in the set Y are colored blue.
If a graph G is bipartite, then it cannot contain an odd cycle. This is because if we have k red nodes, we must also have k blue nodes. Having an odd cycling means that G has 2n+1 nodes. There is no way to divide these 2n+1 nodes into k red nodes and k blue nodes.
We can modify the BFS algorithm slightly to create an algorithm that tests if a graph G is bipartite. We can do this by adding an extra array Color over the nodes. Whenever we get to a step in BFS where we are adding a node v to a list L[i+1], we assign Color[v] = red if i+1 is an even number, and Color[v] = blue if i+1 is an odd number. At the end of this procedure, we simply scan all the edges and determine whether there is any edge for which both ends received the same color. The total running time for the coloring algorithm is O(m+n), much like BFS.
Theorem:
Let G be a connected graph, and let L_1, L_2 .... be the layers produced by BFS starting at node s. Then exactly one of the following two things must hold: (i) There is no edge of G joining two nodes of the same layer. In this case G is a bipartite graph in which the nodes in even-numbered layers can be colored red, and the nodes in odd-numbered layers can be colored blue. (ii) There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite.
The detailed proof of this theorem can be found on page 96 of the textbook.
Despite the its fancy-sounding name, the concept of bipartite graphs was very easy to follow. The algorithm to test for bipartiteness was more or less the BFS algorithm with a few steps added to it. I did think that testing for bipartiteness was an interesting application of the BFS algorithm, and because of that, I found this section a good read.
In a directed graph, the edge (u, v) has a direction: it goes from u to v. In this way, the relationship between u and v is asymmetric, and this has qualitative effects on the structure of the resulting graph.
We can use a version of the adjacency list representation to represent directed graphs. In this representation, instead of each node having a single list of neighbors, each node has two lists associated with it: one list consists of nodes to which it has edges, and a second list consists of nodes from which it has edges.
The BFS and DFS algorithms are more or less the same for directed graphs as they are for undirected graphs.
For the BFS algorithm, we start at a node s, define a first layer of nodes to consist of all those to which s has an edge, define a second layer to consist of all additional nodes to which these first-layer nodes have an edge, and so forth. In this way, we discover nodes layer by layer as they are reached in this outward search from s, and the nodes in layer j are precisely those for which the shortest path from s has exactly j edges. As in the undirected case, this algorithm performs at most constant work for each node and edge, resulting in a running time of O(m+n). Note, however, that since in directed graphs, it is possible for a node s to have a path to a node t even though t has no path to s, what directed BFS is computing is merely the set of all nodes t with the property that s has a path to t; such nodes may or may not have paths back to s.
The DFS algorithm for directed graphs also runs in linear time and computes the same set of nodes. It is again a recursive procedure that tries to explore as deeply as possible, in this case only following edges according to their inherent direction. Thus, when DFS is at a node u, it recursively launches a depth-first search, in order, for each node to which u has an edge.
A directed graph is strongly connected if, for every two nodes u and v, there is a path from u to v and a path from v to u.
Two nodes u and v in a directed graph are mutually reachable if there is a path from u to v and also a path from v to u. As such, a graph is strongly connected if every pair of nodes is mutually reachable. Note that if u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable.
To test if a graph G is strongly connected, we pick any node s and run BFS in G starting from s. We then also run BFS starting from s in G_rev (where G_rev is a graph with all the edges reversed in their directions). Now, if one of these two searches fails to reach every node, then clearly G is not strongly connected. But suppose we find that s has a path to every node, and that every node has a path to s. Then s and v are mutually reachable for every v, and so it follows that every two nodes u and v are mutually reachable: s and u are mutually reachable, and s and v are mutually reachable, so by the above transitive property, we have that u and v are mutually reachable.
For me, this section was more review of what I had known about graphs before. The concepts of directed graphs wasn't novel to me, nor was the concept of strong connectivity. As such, I did not find this section particularly interesting–since I didn't learn much that was new. That said, the section was easy to understand, and did a good job explaining different algorithms.
If a directed graph has no cycles, we call it a directed acyclic graph (DAG).
DAGs can be used to encode precedence relations or dependencies in a natural way. Suppose we have a set of tasks labeled {1, 2 … n} that need to be performed, and there are dependencies among them stipulating, for certain pairs i and j, that i must be performed before j. We can represent such an interdependent set of tasks by introducing a node for each task, and a directed edge (i, j) whenever i must be done before j.
For a directed graph G, we say that a topological ordering of G is an ordering of its nodes as v_l, v_2 … v_n so that for every edge (v_i, v_j), we have i < j. In other words, all edges point “forward” in the ordering. A topological ordering on tasks provides an order in which they can be safely performed.
Theorem:
G has a topological ordering, then G is a DAG.
Proof: Suppose, by way of contradiction, that G has a topological ordering v_1, v_2, …, v_n, and also has a cycle C. Let v_i be the lowest-indexed node on C, and let v_j be the node on C just before v_i–thus (v_j, v_i) is an edge. But by our choice of i, we have j > i, which contradicts the assumption that v_1, v_2, …, v_n was a topological ordering.
To come up with an efficient algorithm to compute the topological ordering in a graph, we must first establish and prove the following theory:
In every DAG G, there is a node v with no incoming edges.
Proof: Let G be a directed graph in which every node has at least one incoming edge. We show how to find a cycle in G; this will prove the claim. We pick any node v, and begin following edges backward from v: sihce v has at least one incoming edge (u, v), we can walk backward to u; then, since u has at least one incoming edge (x, u), we can walk backward to x; and so on. We can continue this process indefinitely, since every node we encounter has an incoming edge. But after n+1 steps, we will have visited some node w twice. If we let C denote the sequence of nodes encountered between successive visits to w, then clearly C forms a cycle.
Theroem:
If G is a DAG, then G has a topological ordering.
(The proof for this theorem can be found on page 102 of the textbook.)
We can use the following algorithm to compute the topological ordering of a graph G:
Find a node v with no incoming edges and order it first O(n)
Delete v from G O(n)
Recursively compute a topological ordering of G-{v} O(n)
and append this order after v O(1)
This algorithm runs in O(n^2).
We can improve this running time to O(m+n) by modifying the algorithm slightly as follows:
We declare a node to be “active” if it has not yet been deleted by the algorithm, and we explicitly maintain two things: (a) for each node w, the number of incoming edges that w has from active nodes; and (b) the set S of all active nodes in G that have no incoming edges from other active nodes. At the start, all nodes are active, so we can initialize (a) and (b) with a single pass through the nodes and edges. Then, each iteration consists of selecting a node v from the set S and deleting it. After deleting v, we go through all nodes w to which v had an edge, and subtract one from the number of active incoming edges that we are maintaining for w. If this causes the number of active incoming edges to w to drop to zero, then we add w to the set S. Proceeding in this way, we keep track of nodes that are eligible for deletion at all times, while spending constant work per edge over the course of the whole algorithm.
I feel like this section was more challenging to understand compared to the rest of the chapter–probably because it was something entirely new to me. The idea of topological ordering seems intuitive and straightforward, and the O(n^2) algorithm felt the most natural way to compute the ordering. While I thought that the optimization to this algorithm to give the O(m+n) running time was genius, I struggled a fair amount understanding the optimized algorithm. However, a few reads later, I did get the idea (took me longer than it should have, to be honest). I'd say this was the most interesting section from 3.2 to 3.6 (the rest was probably 60% review).