6 006 Intro to Algorithms QUIZ 2 REVIEW NOTES Part 2 April 12 2011 Graph Representation The two main graph representations we use when talking about graph problems are the adjacency list and the adjacency matrix It s important to understand the tradeoffs between the two representations Let G V E be our graph where V is the set of vertices and E is the set of edges where each edge is represented as a tuple of vertices Adjacency List An 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 Matrix An 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 factor here is small since each entry in the matrix is just a bit Comparison The worst case storage of an adjacency list is when the graph is dense i e E V 2 This gives us the same space complexity as the adjacency matrix representation The V E space complexity for the general case is usually more desirable however Furthermore adjacency lists give you 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 neighbors of a vertex has been essential 6 006 Intro to Algorithms QUIZ 2 REVIEW NOTES Part 2 April 12 2011 BFS BFS breadth first search is an algorithm to find the shortest paths from a given vertex in an unweighted graph It takes V E time DFS DFS depth first search is an algorithm that explores an unweighted graph DFS is useful for many other algorithms including finding strongly connected components topological sort detecting cycles 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 2011 Edge Classification We 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 three types Selected Past Test Questions 6 006 Intro to Algorithms QUIZ 2 REVIEW NOTES Part 2 April 12 2011 Other Important Topics We 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 components
View Full Document
Unlocking...