Rise over run.
A Data Structures and Algorithms Ruby Assignment from the Viking Code School using Trees and Graphs
Benny and Will
-
What are the advantages and disadvantages of using an Adjacency Matrix vs an Adjacency List relative to size and speed of common operations?
Adjacency matrices waste a lot of space unless you a highly connected graph. Lists are slow to look up on highly connected graphs since the linked lists get really long.
-
What would the Big O be of inserting a new EDGE to:
- An Edge List? O(1)
- An Adjacency Matrix? O(1)
- An Adjacency List? O(1)
-
What would the Big O be of inserting a new VERTEX to:
- An Edge List? O(1)
- An Adjacency Matrix? O(n)
- An Adjacency List? O(1)
-
What would the Big O be of REMOVING a vertex or edge from:
- An Edge List? O(V + E)
- An Adjacency Matrix? Edge: O(1), Vertex: O(n)? O(n^2)?
- An Adjacency List? O(V + E)
-
How would you find all the nodes connected to a particular vertex in:
- An Edge List? Filter the whole list
- An Adjacency Matrix? Check the appropriate row and column
- An Adjacency List? Check the appropriate linked list