Graphs

Question 1

What are the four “types” of graphs?

Answer 1

Undirected, Directed, unweighted, weighted

Question 2

What is the difference in the direction type?

Answer 2

Undirected: Can move either way along an edge
Directed: Can move one way along an edge

Question 3

What is the difference in the weight type?

Answer 3

Unweighted: There is no “cost” to travel an edge
Weighted: Some edges “cost” more than others to travel

Question 4

How can graphs be represented?

Answer 4

An adjacency list or adjacency matrix

Question 5

What a two examples of graph exploration algorithms?

Answer 5

Breadth First Search and Depth First Search

Question 6

In an adjacency list, how many nodes are there compared to the amount of edges?

Answer 6

There are twice as many nodes as edges

Question 7

What are the pros and cons of an adjacency list?

Answer 7

Easy to read, memory is O(|v| + 2|E|), but doesn’t guarantee a deterministic solution

Question 8

What are the pros and cons of an adjacency matrix?

Answer 8

Easy to implement, guarantees deterministic solution, but memory is O(|v|^2) and it is difficult to read

Question 9

What are the basic steps of the BFS algorithm?

Answer 9

1. Chose a start vertex and enque
2. While Q is not empty:
   A. Dequeue first value
   B. For every vertex w in v’s adjacency list, check if found
   C. If not then adjust bookkeeping and enque
3. Repeat until Q is empty

Question 10

What is the time complexity of BFS, for AL AND AM?

Answer 10

AL: O(|E| + |v|)
AM: O(|v|^2)

Question 11

What are the basic steps of the DFS algorithm?

Answer 11

1. Choose a start vertex and push onto stack
2. While S is not empty
   A. Pop top of stack
   B. For the FIRST value w in v’s adjaceny list, check if found
   C. If not then adjust bookkeeping and push
3. Repeat until S is empty

Question 12

What is the time complexity of DFS, for AL AND AM?

Answer 12

AL: O(|E| + |v|)
AM: O(|v|^2)

Question 13

For this problem, should you apply BFS or DFS?

Checking if G is a tree

Answer 13

Both, BFS and DFS

Question 14

For this problem, should you apply BFS or DFS?

Checking if G is bipartite

Answer 14

Both, BFS and DFS

Question 15

For this problem, should you apply BFS or DFS?

Checking if G is connected

Answer 15

Both, BFS and DFS

Question 16

For this problem, should you apply BFS or DFS?

Checking if G is biconnected

Answer 16

Only DFS

Question 17

For this problem, should you apply BFS or DFS?

Finding the vertex with a given property that is closest to the source

Answer 17

Both, BFS and DFS

Question 18

For this problem, should you apply BFS or DFS?

Check if G does or doesn’t have a cycle

Answer 18

Both, BFS and DFS

Question 19

For this problem, should you apply BFS or DFS?

Finding all leaves in G

Answer 19

Neither, BFS and DFS are overkill
Look at AL, and if v is connected to only one other node, then v is a leaf

Question 20

What is a DAG?

Answer 20

An unweighted directed graph that does not have a cycle

Question 21

What is topological sorting in a DAG?

Answer 21

A linear ordering of a directed graph so that for every edge v -> w, v comes before w

Question 22

What is the indegree of a vertex?

Answer 22

The amount of edges going in to that vertex

Question 23

What is a basic topological sorting algorithm?

Answer 23

1. Compute the indegree of every vertex
2. Place all 0 degree vertices in Q
3. Dequeue vertex and check AL for any adjacencies of v
4. If adjacency found, reduce w’s indegree by one
5. Repeat steps 2 - 4 until all indegrees are 0

Question 24

What are the time and space complexities of a basic topological sorting algorithm?

Answer 24

TIME:
Computing indegree: O(|v| + |E|)
Enqueues: O(|v|)
Dequeues: O(|v| + |E|)

SPACE:
Queue: O(|v|)

TOTAL: O(|v| + |E|)

Question 25

What is Single Source Shortest Path?

Answer 25

Given a source vertex, find the shortest path to all reachable vertices

Question 26

What kind of graph can Single Source Shortest Path be used on?

Answer 26

Weighted Directed Graph AND Weighted Undirected Graph

Question 27

What is the colloquial name for the most common Single Source Shortest Path algorithm?

Answer 27

Dijkstra's Algorithm

Question 28

What bookkeeping is necessary for Dijkstra's algorithm?

Answer 28

The parent of each vertex, the shortest distance of from each vertex to the source, and if a vertex has been visited

Question 29

How is the adjacency list of a WDG formatted?

Answer 29

vertex | (w, weight), (w2, weight), ...

Question 30

What is the starting set up for Dijkstra's algorithm?

Answer 30

Source vertex: distance = 0, parent = null, add to MinHeap Other vertices: distance = infinity, parent = null

Question 31

What is the basic loop of Dijkstra's algorithm?

Answer 31

1. Remove the vertex with the smallest distance from the MinHeap 2. Set as visited, add unvisitd neighbors to MinHeap 3. If neighbor's current distance is greater than the distance to the current vertex, then update distance and parent 4. Repeat until all vertices are visited

Question 32

How much memory is used to store a WDG's adjacency list?

Answer 32

O(3|E| + |v|)

Question 33

When using a MinHeap, what is the time complexity of Dijkstra's algorithm?

Answer 33

Step1: 3|v| = O(|v|) Step2: O(|v|log(|v|)) Step3: |v|deleteMin + |E|reduce =|v|log(|v|) + |E|log|v|) =(|v| + |E|) log(|v|) Dominant term is Step 3: O((|v| + |E|) log(|v|)

Question 34

What is a Minimum Spanning Tree?

Answer 34

The set of edges in G that span each vertex once while also minimizing the sum of the weights

Question 35

What are the two approaches for finding an MST?

Answer 35

Kruskal's and Prim's

Question 36

What is the BEST approach for finding an MST?

Answer 36

Prim's, it is easier to implement and it has a smaller time complexity than Kruskal's

Question 37

Explain Kruskal's Algorithm

Answer 37

1. Start with each vertex as its own tree 2. Consider all edges in increasing order 3. Incorporate an edge if it unites vertices in different trees 4. Repeat until all edges are in the MST

Question 38

Explain Prim's Algorithm

Answer 38

1. Start with every vertex having a parent of null and a distance of infinity 2. Choose a random starting vertex and set its distance to 0 3. Add the edge with the minimum weight that connects an unvisited vertex to a visited one 4. Repeat until all edges are in the MST