6.006 Intro to Algorithms QUIZ 2 REVIEW NOTES - Part 2 April 12, 2011Graph RepresentationThe two main graph representations we use when talking about graph problems are the adjacencylist and the adjacency matrix. It’s important to understand the tradeoffs between the two repre-sentations. Let G = (V, E) be our graph where V is the set of vertices and E is the set of edgeswhere each edge is represented as a tuple of vertices.Adjacency ListAn adjacency list is a list of lists. Each list corresponds to a vertex u and contains a list of edges(u, v) that originate from u. Thus, an adjacency list takes up Θ(V + E) space.Adjacency MatrixAn adjacency matrix is a |V | × |V | matrix of bits where element (i, j) is 1 if and only if the edge(vi, vj) is in E. Thus an adjacency matrix takes up Θ(|V |2) storage (note that the constant factorhere is small since each entry in the matrix is just a bit).ComparisonThe worst case storage of an adjacency list is when the graph is dense, i.e. E = Θ(V2). This givesus the same space complexity as the adjacency matrix representation. The Θ(V + E) space com-plexity for the general case is usually more desirable, however. Furthermore, adjacency lists giveyou the set of adjacent vertices to a given vertex quicker than an adjacency matrix O(neighbors)for the former vs O(V ) for the latter. In the algorithms we’ve seen in class, finding the neighborsof a vertex has been essential.6.006 Intro to Algorithms QUIZ 2 REVIEW NOTES - Part 2 April 12, 2011BFSBFS (breadth first search) is an algorithm to find the shortest paths from a given vertex in anunweighted graph. It takes Θ(V + E) time.DFSDFS (depth first search) is an algorithm that explores an unweighted graph. DFS is useful for manyother algorithms, including finding strongly connected components, topological sort, detectingcycles. DFS does not necessarily find shortest paths. It also runs in Θ(V + E) time.6.006 Intro to Algorithms QUIZ 2 REVIEW NOTES - Part 2 April 12, 2011Edge ClassificationWe classify the edges in the resulting DFS tree as one of the following four types:1. Tree edge - an edge that is traversed during the search.2. Back edge - an edge (u, v) that goes from a node u to an ancestor of it in the DFS tree.3. Forward edge - an edge (u, v) that goes from a node u to a descendant of it in the DFS tree.4. Cross edge - any other edge in the original graph not classified as one of the above threetypes.Selected Past Test Questions6.006 Intro to Algorithms QUIZ 2 REVIEW NOTES - Part 2 April 12, 2011Other Important TopicsWe did not have time to cover all possible topics regarding Graphs/BFS/DFS at the review session.You should also review anything else in the lecture/recitation notes. For example:• Beginning/Finishing times for DFS• Topological sort• BFS queue vs DFS stack• Rubik’s cube graph• Proofs of correctness and runtime• DAG’s• Connected
View Full Document