L13 (Graph Representations and DFS) Flashcards
A graph is specified by two sets of items. What are these?
- A set of Vertices, V
- A set of Edges, E
Thus, we say a graph G = (V, E)
For two vertices u, v, what is the notation we use for:
- A directed edge between u and v
- An undirected edge between u and v
- Directed Edge: (u, v)
- Undirected Edge: {u, v}
What are the 2 different ways of representing a graph in linear memory? What is the space complexity for each?
In what case do these 2 ways have the same space complexity
- Adjacency matrix, takes up O(V^2) space
- Adjacency list, takes up O(V + E) space
- Space complexity will be the same in a fully connected graph because E = V^2 - V in that case
Whenever performing a DFS starting on a vertex v in a graph G, which parts of the graph will the DFS algorithm cover? which parts will it miss?
- DFS will find the portion of the graph that is reachable from v
- All vertices that are not in connected components will not be visited
What is the runtime of DFS?
O(V + E) assuming that the graph G is an adjacency list - it is linear with respect to the input size
Suppose we have a fully connected graph with V vertices. What is the upper and lower bound on the number of edges?
The number of edges will be minimum V-1 and maximum V^2