L13 (Graph Representations and DFS)

Question 1

A graph is specified by two sets of items. What are these?

Answer 1

1. A set of Vertices, V
2. A set of Edges, E

Thus, we say a graph G = (V, E)

Question 2

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

Answer 2

• Directed Edge: (u, v)
• Undirected Edge: {u, v}

Question 3

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

Answer 3

• 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

Question 4

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?

Answer 4

• 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

Question 5

What is the runtime of DFS?

Answer 5

O(V + E) assuming that the graph G is an adjacency list - it is linear with respect to the input size

Question 6

Suppose we have a fully connected graph with V vertices. What is the upper and lower bound on the number of edges?

Answer 6

The number of edges will be minimum V-1 and maximum V^2