L13 (Graph Representations and DFS) Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

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

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A
  • Directed Edge: (u, v)
  • Undirected Edge: {u, v}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the runtime of DFS?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly