MIT 6 006 - QUIZ 2 REVIEW NOTES (4 pages)

Previewing page 1 of 4 page document View the full content.
View Full Document

QUIZ 2 REVIEW NOTES



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

QUIZ 2 REVIEW NOTES

61 views

Other


Pages:
4
School:
Massachusetts Institute of Technology
Course:
6 006 - Introduction to Algorithms
Introduction to Algorithms Documents

Unformatted text preview:

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



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view QUIZ 2 REVIEW NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view QUIZ 2 REVIEW NOTES and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?