6.006 Introduction to Algorithms, Recitation 9

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Recitation 9 Recitation 9 Graphs A graph G = (V, E) is a mathematical object comprising a set of vertices V (also called nodes) and a set of edges E, where each edge in E is a two-element subset of vertices from V . A vertex and edge are incident or adjacent if the edge contains the vertex. Let u and v be vertices. An edge is directed if its subset pair is ordered, e.g., (u, v), and undirected if its subset pair is unordered, e.g., {u, v} or alternatively both (u, v) and (v, u). A directed edge e = (u, v) extends from vertex u (e’s tail) to vertex v (e’s head), with e an incoming edge of v and an outgoing edge of u. In an undirected graph, every edge is incoming and outgoing. The in-degree and out-degree of a vertex v denotes the number of incoming and outgoing edges connected to v respectively. Unless otherwise specified, when we talk about degree, we generally mean out-degree. As their name suggest, graphs are often depicted graphically, with vertices drawn as points, and edges drawn as lines connecting the points. If an edge is directed, its corresponding line typically includes an indication of the direction of the edge, for example via an arrowhead near the edge’s head. Below are examples of a directed graph G1 and an undirected graph G2 . V1 = {0, 1, 2, 3, 4} V2 = {0, 1, 2, 3, 4} G1 = (V1 , E1 ) G2 = (V2 , E2 ) E1 = {(0, 1), (1, 2), (2, 0), (3, 4)} E2 = {{0, 1}, {0, 3}, {0, 4}, {2, 3}} 0 0 4 1 3 2 4 1 3 2 A path1 in a graph is a sequence of vertices (v0 , . . . , vk ) such that for every ordered pair of vertices (vi , vi+1 ), there exists an outgoing edge in the graph from vi to vi+1 . The length of a path is the number of edges in the path, or one less than the number of vertices. A graph is called strongly connected if there is a path from every node to every other node in the graph. Note that every connected undirected graph is also strongly connected because every undirected edge incident to a vertex is also outgoing. Of the two connected components of directed graph G1 , only one of them is strongly connected. 1 These are “walks” in 6.042. A “path” in 6.042 does not repeat vertices, which we would call a simple path. Recitation 9 2 Graph Representations There are many ways to represent a graph in code. The most common way is to store a Set data structure Adj mapping each vertex u to another data structure Adj(u) storing the adjacencies of v, i.e., the set of vertices that are accessible from v via a single outgoing edge. This inner data structure is called an adjacency list. Note that we don’t store the edge pairs explicitly; we store only the out-going neighbor vertices for each vertex. When vertices are uniquely labeled from 0 to |V | − 1, it is common to store the top-level Set Adj within a direct access array of length |V |, where array slot i points to the adjacency list of the vertex labeled i. Otherwise, if the vertices are not labeled in this way, it is also common to use a hash table to map each u ∈ V to Adj(u). Then, it is common to store each adjacency list Adj(u) as a simple unordered array of the outgoing adjacencies. For example, the following are adjacency list representations of G1 and G2 , using a direct access array for the top-level Set and an array for each adjacency list. 1 2 3 4 5 A1 = [[1], [2], [0], [4], []] A2 = [[1, 4, 3], [0], [3], [0, 2], [0]] # # # # # 0 1 2 3 4 Using an array for an adjacency list is a perfectly good data structures if all you need to do is loop over the edges incident to a vertex (which will be the case for all algorithms we will discuss in this class, so will be our default implementation). Each edge appears in any adjacency list at most twice, so the size of an adjacency list representation implemented using arrays is Θ(|V | + |E|). A drawback of this representation is that determining whether your graph contains a given edge (u, v) might require Ω(|V |) time to step through the array representing the adjacency list of u or v. We can overcome this obstacle by storing adjacency lists using hash tables instead of regular unsorted arrays, which will support edge checking in expected O(1) time, still using only Θ(|V |+|E|) space. However, we won’t need this operation for our algorithms, so we will assume the simpler unsorted-array-based adjacency list representation. Below are representations of G1 and G2 that use a hash table for both the outer Adj Set and the inner adjacency lists Adj(u), using Python dictionaries: 1 2 3 4 5 S1 = {0: 1: 2: 3: {1}, {2}, {0}, {4}} S2 = {0: 1: 2: 3: 4: {1, 3, 4}, {0}, {3}, {0, 2}, {0}} # # # # # 0 1 2 3 4 Recitation 9 3 Breadth-First Search Given a graph, a common query is to find the vertices reachable by a path from a queried vertex s. A breadth-first search (BFS) from s discovers the level sets of s: level Li is the set of vertices reachable from s via a shortest path of length i (not reachable via a path of shorter length). Breadth-first search discovers levels in increasing order starting with i = 0, where L0 = {s} since the only vertex reachable from s via a path of length i = 0 is s itself. Then any vertex reachable from s via a shortest path of length i + 1 must have an incoming edge from a vertex whose shortest path from s has length i, so it is contained in level Li . So to compute level Li+1 , include every vertex with an incoming edge from a vertex in Li , that has not already been assigned a level. By computing each level from the preceding level, a growing frontier of vertices will be explored according to their shortest path length from s. Below is Python code implementing breadth-first search for a graph represented using indexlabeled adjacency lists, returning a parent label for each vertex in the direction of a shortest path back to s. Parent labels (pointers) together determine a BFS tree from vertex s, containing some shortest path from s to every other vertex in the graph. 1 2 3 4 5 6 7 8 9 10 11 12 def bfs(Adj, s): parent = [None for v in Adj] parent[s] = s level = [[s]] while 0 < len(level[-1]): level.append([]) for u in level[-2]: for v in Adj[u]: if parent[v] is None: parent[v] = u level[-1].append(v) return parent # # # # # # # # # # # Adj: adjacency list, s: starting vertex O(V) (use hash if unlabeled) O(1) root O(1) initialize levels O(?) last level contains vertices O(1) amortized, make new level O(?) loop over last full level O(Adj[u]) loop over neighbors O(1) parent not yet assigned O(1) assign parent from level[-2] O(1) amortized, add to border How fast is breadth-first search? In particular, how many times can the inner loop on lines 9–11 be executed? A vertex is added to any level at most once in line 11, so the loop in line 7 processes each vertex v at most once. The loop in line 8 cycles P through all deg(v) outgoing edges from vertex v. Thus the inner loop is repeated at most O( v∈V deg(v)) = O(|E|) times. Because the parent array returned has length |V |, breadth-first search runs in O(|V | + |E|) time. Recitation 9 4 Exercise: For graphs G1 and G2 , conducting a breadth-first search from vertex v0 yields the parent labels and level sets below. 1 2 3 4 5 P1 = [0, 0, 1, None, None] L1 = [[0], [1], [2], []] P2 = [0, 0, 3, 0, 0] L2 = [[0], [1,3,4], [2], []] # # # # # 0 1 2 3 4 We can use parent labels returned by a breadth-first search to construct a shortest path from a vertex s to vertex t, following parent pointers from t backward through the graph to s. Below is Python code to compute the shortest path from s to t which also runs in worst-case O(|V | + |E|) time. 1 2 3 4 5 6 7 8 9 10 def unweighted_shortest_path(Adj, s, t): parent = bfs(Adj, s) if parent[t] is None: return None i = t path = [t] while i != s: i = parent[i] path.append(i) return path[::-1] # # # # # # # # # O(V + E) BFS tree from s O(1) t reachable from s? O(1) no path O(1) label of current vertex O(1) initialize path O(V) walk back to s O(1) move to parent O(1) amortized add to path O(V) return reversed path Exercise: Given an unweighted graph G = (V, E), find a shortest path from s to t having an odd number of edges. Solution: Construct a new graph G0 = (V 0 , E 0 ). For every vertex u in V , construct two vertices uE and uO in V 0 : these represent reaching the vertex u through an even and odd number of edges, respectively. For every edge (u, v) in E, construct the edges (uE , vO ) and (uO , vE ) in E 0 . Run breadth-first search on G0 from sE to find the shortest path from sE to tO . Because G0 is bipartite between even and odd vertices, even paths from sE will always end at even vertices, and odd paths will end at odd vertices, so finding a shortest path from sE to tO will represent a path of odd length in the original graph. Because G0 has 2|V | vertices and 2|E| edges, constructing G0 and running breadth-first search from sE each take O(|V | + |E|) time.