9.2 (Graph Representations) Flashcards
Which graph operation inserts a new vertex into the graph?
Add Vertex
Which graph operation creates a connection between two vertices?
Add Edge
Which graph operation deletes a vertex and all its edges?
Remove Vertex
Which graph operation deletes a specific edge between two vertices?
Remove Edge
Which graph operation determines if there is an edge between two vertices?
Edge Exists
Which graph operation retrieves all adjacent vertices of a given vertex?
Get Neighbors
Which graph operation counts the number of edges connected to a vertex?
Get Degree
Which graph operation determines if all vertices are reachable?
Graph is Connected
What are the two common graph representations?
1) Adjacency Matrix Representation
2) Adjacency List Representation
Which representation is best for constant-time edge lookup and has dense graphs?
Adjacency Matrix Representation
Which representation is best for more sparse graphs and has fast traversal?
Adjacency List Representation
If a graph has V vertices, the number of edges E ranges between [ ______, ________]
[0, V/(V-1) / 2]
What is the adjacency matrix for hasEdge and addEdge?
O(1)
What is the adjacency matrix for Space?
O(v^2)
What is the adjacency matrix for getNeighbors?
O(v)
What is the adjacency list for addEdge and getNeighbors?
O(1)
What is the adjacency list for space?
O(v+e)
What is the adjacency list for hasEdge?
O(min(v, e))
Why is adjacency list representattino preferable?
it requires less space
