What problem does Dijkstra's algorithm solve?
A Minimum spanning tree
B All pairs connectivity only
C Single source shortest paths
D String pattern search
Answer: C. Single source shortest paths. Dijkstra computes shortest paths from a source when edge weights are nonnegative.
What edge weight condition does Dijkstra require?
A Nonnegative weights
B All weights equal one
C Negative weights only
D No weighted edges
Answer: A. Nonnegative weights. Negative edges can invalidate Dijkstra's greedy settlement step.
Which algorithm supports negative edge weights?
A Dijkstra
B Bellman Ford
C Kruskal
D Binary search
Answer: B. Bellman Ford. Bellman Ford relaxes edges repeatedly and supports negative weights.
What does Floyd Warshall compute?
A One minimum spanning tree
B Single pattern match
C Only unweighted reachability
D All pairs shortest paths
Answer: D. All pairs shortest paths. Floyd Warshall updates distances between every pair through intermediate vertices.
What is edge relaxation?
A Delete a heavy edge
B Try improving a known distance
C Reverse a graph path
D Mark a vertex visited
Answer: B. Try improving a known distance. Relaxation checks whether an edge provides a shorter path to a vertex.
What does a minimum spanning tree minimize?
A Number of vertices
B Total edge weight
C Longest path length
D Maximum vertex degree
Answer: B. Total edge weight. An MST connects all vertices with minimum total edge weight and no cycles.
How does Kruskal's algorithm select edges?
A Decreasing weight with cycles
B Breadth first by distance
C Increasing weight without cycles
D Randomly until connected
Answer: C. Increasing weight without cycles. Kruskal adds light edges that join distinct components.
Which structure helps Kruskal detect components?
A Stack
B Disjoint set union
C Trie
D Circular queue
Answer: B. Disjoint set union. A disjoint set structure tracks whether endpoints are already connected.
How does Prim's algorithm grow a spanning tree?
A Sorts all vertices by name
B DFS from every edge
C Removes the lightest vertex
D Adds light crossing edge
Answer: D. Adds light crossing edge. Prim repeatedly adds a cheapest edge connecting the growing tree to a new vertex.
What does topological sorting require?
A Undirected cycle
B Directed acyclic graph
C Complete weighted graph
D Binary search tree
Answer: B. Directed acyclic graph. Topological order exists for directed acyclic graphs.
What does indegree count?
A Outgoing paths only
B All reachable vertices
C Distinct graph components
D Incoming directed edges
Answer: D. Incoming directed edges. The indegree of a vertex counts edges directed into it.
Which traversal is useful for topological sorting?
A Binary search
B Heap sort
C Depth first search
D Linear probing
Answer: C. Depth first search. A DFS finishing order can produce a topological order in a DAG.
What is a strongly connected directed graph?
A Every edge has equal weight
B It has no cycles
C Every vertex reaches every other
D It contains one source only
Answer: C. Every vertex reaches every other. Strong connectivity means each vertex can reach every other following edge directions.
What does Kosaraju's algorithm find?
A Minimum spanning tree
B Negative weight cycles
C Strongly connected components
D String prefixes
Answer: C. Strongly connected components. Kosaraju uses DFS passes on a graph and its transpose to find SCCs.
What does A star prioritize?
A Only number of vertices
B Largest edge weight
C Random priority values
D Path cost plus heuristic
Answer: D. Path cost plus heuristic. A star ranks a state using known cost plus an estimate to the goal.
What does an admissible A star heuristic guarantee?
A Never overestimates remaining cost
B Always equals exact cost
C Can be negative only
D Ignores goal distance
Answer: A. Never overestimates remaining cost. An admissible heuristic is an optimistic lower bound on remaining cost.
What does breadth first search find shortest paths for?
A Graphs with negative weights
B All weighted graphs
C Only directed cycles
D Unweighted graphs
Answer: D. Unweighted graphs. BFS minimizes edge count in an unweighted graph.
What does depth first search commonly help detect?
A Cycles and connectivity
B Sorted numeric order
C Minimum weights only
D Hash collisions
Answer: A. Cycles and connectivity. DFS can explore graph structure for cycles, reachability, and components.
What is a bridge in an undirected graph?
A Edge whose removal disconnects graph
B Edge in every cycle
C Vertex with no neighbors
D Minimum weight edge
Answer: A. Edge whose removal disconnects graph. A bridge is an edge whose removal increases the number of connected components.
What is an articulation vertex?
A Vertex of maximum degree
B Vertex whose removal disconnects graph
C Vertex with no outgoing edges
D A source in every path
Answer: B. Vertex whose removal disconnects graph. An articulation vertex is a cut vertex whose removal disconnects a connected component.
What is an Euler circuit?
A Path visiting every vertex once
B Cycle with minimum weight
C Walk using every vertex twice
D Closed walk, each edge once
Answer: D. Closed walk, each edge once. An Euler circuit traverses each edge exactly once and returns to its start.
What is a Hamiltonian cycle?
A Cycle visiting every vertex once
B Cycle using every edge once
C Shortest weighted path
D A tree with every leaf
Answer: A. Cycle visiting every vertex once. A Hamiltonian cycle visits each vertex once before returning to its start.
What is transitive closure of a graph?
A Reachability relation between vertices
B Minimum spanning edge set
C Sorted adjacency list
D Shortest path tree only
Answer: A. Reachability relation between vertices. Transitive closure records whether a path exists for each vertex pair.
What does a negative cycle allow in shortest path problems?
A Path cost decreases indefinitely
B Every path becomes unique
C All distances become positive
D The graph becomes acyclic
Answer: A. Path cost decreases indefinitely. Traversing a reachable negative cycle repeatedly can reduce path cost indefinitely.
What does a graph cut separate?
A Edges by weight only
B Cycles from paths
C Vertices into two groups
D Source code into modules
Answer: C. Vertices into two groups. A cut partitions vertices into sets and identifies edges crossing between them.