CS 6515 Graph Algorithms Test Questions and Answers Solved Correctly
DFS outputs - Answerspre array, post array, ccnum array, prev array
BFS outputs - Answersdist array, prev array
Explore outputs - Answersvisited array.
When to use Dijkstra's? - AnswersWorks for both directed and undirected graphs. Must have only non-
negative edge weights.
Dijkstra's outputs - Answersdist array, prev array
Dijkstra's runtime? - AnswersO((n+m) log n)
log n is from using the min heap (to get the lowest cost weight)
When to use Bellman Ford? - AnswersUse when there is a graph with negative edge weights. Gives us
the shortest path from s to every other vertex v. Slower than Dijkstra's algorithm. Dijkstra's was
O((n+m)logn), but this is O(n*m). Can also be used to detect negative weight cycles IF the cycle is
reachable from sources.
Bellman ford runtime - AnswersO(n*m)
Remember, this uses a dynamic programming table. Will have found the shortest path distances after n -
1 iterations. If the distances keep updating, there is a negative weight cycle.
Floyd Warshall output - AnswersReturns an n by n matrix of shortest path costs between EVERY pair of
vertices.
Floyd Warshall runtime - AnswersO(n^3)
When to use SCC algorithm? - AnswersOnly useful for directed graphs. Use to get a metagraph of
connected components. Each SCC is represented as a single node. The resulting metagraph is always a
DAG.
SCC algorithm time complexity - AnswersO(n+m)
Uses topological sort (O(n+m)) on the reverse graph
Complexity to find an MST - AnswersO(m log n) for both Kruskal's and for Prim's
When to use Kruskal's or Prim's? - AnswersTo find the MST of an undirected graph
Kruskal's vs. Prim's? Differences in approach? - AnswersKruskal's greedily takes the cheapest edges and
adds them to our MST (if they don't create cycles). Checking for cycles is accomplished via the union find
data structure.
DFS outputs - Answerspre array, post array, ccnum array, prev array
BFS outputs - Answersdist array, prev array
Explore outputs - Answersvisited array.
When to use Dijkstra's? - AnswersWorks for both directed and undirected graphs. Must have only non-
negative edge weights.
Dijkstra's outputs - Answersdist array, prev array
Dijkstra's runtime? - AnswersO((n+m) log n)
log n is from using the min heap (to get the lowest cost weight)
When to use Bellman Ford? - AnswersUse when there is a graph with negative edge weights. Gives us
the shortest path from s to every other vertex v. Slower than Dijkstra's algorithm. Dijkstra's was
O((n+m)logn), but this is O(n*m). Can also be used to detect negative weight cycles IF the cycle is
reachable from sources.
Bellman ford runtime - AnswersO(n*m)
Remember, this uses a dynamic programming table. Will have found the shortest path distances after n -
1 iterations. If the distances keep updating, there is a negative weight cycle.
Floyd Warshall output - AnswersReturns an n by n matrix of shortest path costs between EVERY pair of
vertices.
Floyd Warshall runtime - AnswersO(n^3)
When to use SCC algorithm? - AnswersOnly useful for directed graphs. Use to get a metagraph of
connected components. Each SCC is represented as a single node. The resulting metagraph is always a
DAG.
SCC algorithm time complexity - AnswersO(n+m)
Uses topological sort (O(n+m)) on the reverse graph
Complexity to find an MST - AnswersO(m log n) for both Kruskal's and for Prim's
When to use Kruskal's or Prim's? - AnswersTo find the MST of an undirected graph
Kruskal's vs. Prim's? Differences in approach? - AnswersKruskal's greedily takes the cheapest edges and
adds them to our MST (if they don't create cycles). Checking for cycles is accomplished via the union find
data structure.
