CS6515 EXAM 2 2026/2027
ACTUAL QUESTIONS WITH
VERIFIED ANSWERS.
BFS Algorithm - correct answer -Input: Directed or Undirected
Graph G, and start vertex s
Output:
1. dist[u] - distance from s to u if s can reach u, inf otherwise
2. prev[z] - the parent index of vertex z
Runtime: O(m+n)
- Use this for unweighted Single Source Shortest Path
- Dist is given as the number of edges from s to u, not the sum of
weights
DFS Algorithm - correct answer -Input: Graph G
Output:
1. prev[z] - parent index of vertex z
,2. pre[z] - pre number of vertex z
3. post[z] - post number of vertex z
4. ccnum[z] - connected component number of z
Runtime: O(m+n)
Dijkstra's Algorithm - correct answer -Input: Graph (directed/un-
directed), Start vertex.
Output:
1. dist[u] - distance from s to u if s can reach u
2. prev[z] - parent index of vertex z
Runtime: O( (n + m) * log(n) )
More sophisticated BFS that utilizes miniheap data structure.
Such requires an additional log(n) time over BFS because of this
SCC Algorithm - correct answer -Input: Directed Graph
Output:
1. Metagraph of G.
, 2. Connected Component Numbers for each vertex (this comes
from DFS, explained above)
Runtime: O(n + m)
Kruskal Algorithm - correct answer -Input: connected undirected
graph G, edge weights w
Output: minimum spanning tree defined by the edges
Runtime: O(m log(m)) or O(m log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
How it works: Basically Sorts edges from least to greatest and
starts building the tree.
Prim's Algorithm - correct answer -Runtime: O(m log(m)) or O(m
log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
Output: The Minimum Spanning Tree of the graph.
ACTUAL QUESTIONS WITH
VERIFIED ANSWERS.
BFS Algorithm - correct answer -Input: Directed or Undirected
Graph G, and start vertex s
Output:
1. dist[u] - distance from s to u if s can reach u, inf otherwise
2. prev[z] - the parent index of vertex z
Runtime: O(m+n)
- Use this for unweighted Single Source Shortest Path
- Dist is given as the number of edges from s to u, not the sum of
weights
DFS Algorithm - correct answer -Input: Graph G
Output:
1. prev[z] - parent index of vertex z
,2. pre[z] - pre number of vertex z
3. post[z] - post number of vertex z
4. ccnum[z] - connected component number of z
Runtime: O(m+n)
Dijkstra's Algorithm - correct answer -Input: Graph (directed/un-
directed), Start vertex.
Output:
1. dist[u] - distance from s to u if s can reach u
2. prev[z] - parent index of vertex z
Runtime: O( (n + m) * log(n) )
More sophisticated BFS that utilizes miniheap data structure.
Such requires an additional log(n) time over BFS because of this
SCC Algorithm - correct answer -Input: Directed Graph
Output:
1. Metagraph of G.
, 2. Connected Component Numbers for each vertex (this comes
from DFS, explained above)
Runtime: O(n + m)
Kruskal Algorithm - correct answer -Input: connected undirected
graph G, edge weights w
Output: minimum spanning tree defined by the edges
Runtime: O(m log(m)) or O(m log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
How it works: Basically Sorts edges from least to greatest and
starts building the tree.
Prim's Algorithm - correct answer -Runtime: O(m log(m)) or O(m
log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
Output: The Minimum Spanning Tree of the graph.
