Graphs

Question 1

Give an overview of how DFS is done for graphs

Answer 1

You pass DFS a start vertex and possibly an end vertex.
The start vertex is where the search will start and the end vertex if provided is where the search will stop

You have two running data structures: a list of visited vertices and a stack. The stack keeps track of

Question 2

When does it make more sense to use an adjacency matrix?

Answer 2

Because space complexity of adjacency matrix is O(|v|^2), it makes more sense to use an adjacency matrix when we have a lot of edges between vertices to keep track of. Adjacency matrix is good when the graph is dense i.e. when the number of edges is close to the number of vertices^2. Or when v^2 is so small that conserving space wouldn’t matter.

A good way to think about this is…does the adjacency matrix have a lot of 0’s in it? This means that the graph is sparse (few edges) between vertices. A graph becomes dense when every vertex is connected to every other vertex once. Think about facebook…adjacency matrix wouldn’t make sense because not every person is going to be friends with the billion other people in the planet. So there’s going to be a lot of empty edges.

Question 3

What is the space complexity of an adjacency list

Answer 3

O(|V| + |E|) (cardinality of vertices + cardinality of edges)

Question 4

Graphs are made up of _____ and _____

Answer 4

vertices and edges

Question 5

Whats the approach for determining if a directed graph has a cycle?

Answer 5

You have three sets, white, gray, and black.

Question 6

What is more space efficient? Adjacency list or adjacency matrix. In what situation is it more space efficient?

Answer 6

Adjacency list when the graph is sparse i.e. it has relatively few edges

Question 7

What is a strongly connected directed graph?

Answer 7

all vertices are reachable from all other vertices.

Question 8

What is the drawback of using an adjacency matrix? What’s its advantage?

Answer 8

You use a lot more space to record edges. The benefit of using this though is that it improves time complexities for common operations like search, insert, and remove.

Question 9

What does it mean for an undirected graph to be connected?

Answer 9

Connected undirected graph means that all vertices can be accessed from all other vertices

Question 10

What does it mean for an edge to be weighted?

Answer 10

Edges can be weighted or unweighted. Weighted edges represent something about that edge. For example, it might represent the distance between vertices.

Question 11

What is the time complexity of finding adjacent nodes in an adjacency matrix

Answer 11

If nodes have keys 1:1 with the indices in the adjacency matrix, if we wanted to find adjacent nodes of node 0, then searching for adjacent nodes would be O(v) because we have to search the second embedded list entirely

Question 12

Whats the data structure used for BFS? (hint: this is the same as BFS in a binary tree)

Answer 12

queue

Question 13

Time complexity for adding an edge in adjacency matrix vs. adjacency list?

Answer 13

matrix: O(1) because we can directly access the row and column in the list of lists without having to increase the size of the list
adjacency list: Could be amortized O(1) if its not required that the list is sorted. If it has to be sorted, then worst case of adding an edge is O(n)

Question 14

What does it mean for a graph to be sparse and dense?

Answer 14

sparse = few edges
dense = many edges

Question 15

What is the space complexity of an adjacency matrix?

Answer 15

O(|V|^2) (cardinality of vertices squared)

Question 16

Time complexity of searching if two nodes are connected in an adjacency matrix

Answer 16

O(1) because we just need to access self.ajd_matrix[row][column]

Question 17

What are directed edges?

Answer 17

Directed edges represent a one or two way connection from one vertex to the other

Question 18

When are vertices adjacent?

Answer 18

Vertices are adjacent when theres an edge connecting them

Question 19

What does it mean for a matrix to be symmetric?

Answer 19

This often occurs in undirected graphs. An edge between two vertices is reflected in the matrix in two positions for each vertex.

Question 20

What’s the data structure used for DFS? Why is a stack used?

Answer 20

Stack. A stack is used because in DFS we want to visit

Question 21

What is the time complexity of searching if node A and B are connected in an adjacency list?

Answer 21

O(v) if the list is unsorted. This is because in worst case, a given vertex can be connected to all other vertices.
It would be O(log v) if the adjacency list was sorted bc then we can do binary search

Question 22

The dijkstra algorithm from the quiz uses what data structure?

Answer 22

A priority queue. Start with the source vertex in the priority queue as a(0). Add the popped value to the reached column with its weight.

Question 23

How are edges represented in set form?

Answer 23

An edge is represented by vertex pairs e.g. E = {{v_1, v_2}, ….}

Question 24

Time complexity for finding all nodes connected to some vertex A?

Answer 24

O(v) because at worst case the node is connected to all other edges including itself

Question 25

Describe the flow of dijkstra’s algorithm

Answer 25

Start at source vertex and label it 0. Label the vertices connected to source by their distance.
Pick the vertex with the least distance. Update its connected vertices with distances.
Always picking the vertex with the least distance

Question 26

What are undirected edges?

Answer 26

Edges with no direction. It just represents a connection