Graphs

Question 1

What algorithms can you use to solve shortest path problems?

Answer 1

• BFS (if graph is unweighted)
• Dijkstra
• Bellman-Ford
• Floyd-Warshall
• A*

Question 2

What algorithms can you use to solve connectivity problems?

Answer 2

Union find data structure, DFS, BFS

Question 3

What algorithms can you use to solve negative cycles problems?

Answer 3

• Bellman-Ford

- Floyd-Warshall

Question 4

What algorithms can you use to solve strongly connected components problems?

Answer 4

• Tarjan’s

- Kosaraju’s

Question 5

What algorithms can you use to solve minimum spanning tree problems?

Answer 5

• Kruskal’s

- Prim’s & Boruvkas

Question 6

What algorithms can you use to solve Network flow: max flow problems?

Answer 6

• Ford-Fulkerson

- Edmonds-Karp & Dinic’s

Question 7

Whats the time complexity of DFS?

Answer 7

O(V+E) vertices + edges

Question 8

Whats the time complexity of BFS?

Answer 8

O(V+E) vertices + edges

Question 9

What’s the main if statements in a loop checking for bridges?

Answer 9

if (!visited) {
  dfs()
  low[at] = min(low[at], low[to]);
  if (ids[at] < low[to]) {
      // found bridge
  }
} else {
  low[at] = min(low[at], ids[to]);
}