Key Concepts

Question 1

What is a DAGs?

Answer 1

Directed, Acyclic Graphs

Question 2

What are Strongly Connected Components?

Answer 2

subsets of vertices in a directed graph such that there is a directed path from any vertex in the subset to every other vertex in the same subset.

Question 3

What are Sources?

Answer 3

In a directed graph, a source is a vertex in a directed graph that has no incoming edges.

Question 4

What are Sinks?

Answer 4

In a directed graph, a sink is a vertex in a directed graph that has no outgoing edges.

Question 5

What are Trees?

Answer 5

is a specific type of undirected graph that is connected and acyclic.In a directed graph, each vertex, except the root, has one incoming edge (from its parent) and may have multiple outgoing edges (to its children). The tree will be acyclic.

Question 6

What is a MST?

Answer 6

MST is Minimum Spanning Tree. a connected, undirected graph is a tree that spans all the vertices of the graph, with the minimum possible total edge weight

Question 7

What are Flow Networks?

Answer 7

is a directed graph in which each edge has a capacity and a flow

Question 8

In runtime, O(m+n), what does m signify and what does n signify?

Answer 8

m signify edgesn signify vertices

Question 9

In runtime O(C m), what does C signify?

Answer 9

Size of the max flow

Question 10

What algorithm does Ford-Fulkerson use internally?

Answer 10

DFS

Question 11

What algorithm does SCC use internally?

Answer 11

2 DFS

Question 12

What algorithm does Edmond-Karp use internally?

Answer 12

BFS

Question 13

Why would use Djistra’s over Belman Ford and Floyd Warshall?

Answer 13

Dijkstra’s are more efficient for postive weights only.

Question 14

Why would use Belman Ford and Floyd Warshall over Djikstra’s?

Answer 14

Bellman Ford and Floyd Warshall works on negative weights, whereas Djikstra’s does not.

Question 15

Why would you use Floyd Warshall over Bellman Ford?

Answer 15

Floyd Warshall is good for finding shortest path from all vertices, whereas Bellman Ford is only good for finding shortest path from 1 vertex.

Question 16

Why would you use Bellman Ford over Floyd Warshall ?

Answer 16

Floyd Warshall is good for finding shortest path from all vertices, whereas Bellman Ford is only good for finding shortest path from 1 vertex to all other vertices.

Question 17

Why would you choose Kruskal’s over Prim or vice versa?

Answer 17

It does not matter which algorithm you use. Choose one which is easier to remember. Reference: https://edstem.org/us/courses/50892/discussion/4313106?comment=10048285

Question 18

Why would you use DFS over BFS or vice versa?

Answer 18

BFS is good for finding the shortest path for unweighted graphs from a starting vertex using dist(u). DFS is good at topologically sorting a DAG and finding connected components.

Question 19

Do Kruskal’s and Prims algorithm work on directed and undirected graphs?

Answer 19

No. They don’t work on directed graphs.

Question 20

Why would you choose Explore over DFS?

Answer 20

Explore takes a starting vertex as an input. Explore only visits all reachable vertices from the starting vertex. We’ll get a visited array with reachable vertices marked as TRUE and non-reachable vertices marked as FALSE. whereas DFS explores all vertices regardless if they are reachable from the starting vertex. The visited array for DFS will always return TRUE for all vertices.

Question 21

What is the Cut Property?

Answer 21

if edges X are part of a minimum spanningtree of graph G, we can pick any subset of nodes S for which X doesnot cross between S and V-S, and let e be the lightest edge acrossthis partition. Then X U {e} is a part of some MST.

Question 22

What is the difference between Ford-Fulkerson and Edmonds-Karp algorithm?

Answer 22

Edmonds-Karp only needs positive capacities whereas Ford-Fulkerson requires positive integer capacities.

Question 23

What are the different types of graphs?

Answer 23

• connected vs disconnected* undirected vs directed* cycle vs acyclic* weighted vs unweighted * positive vs negative weights