Data Structures Graphs 2 ā Questions and Answers
Question 1: Which algorithm is used to find the shortest path from a single source to all other vertices in a graph with non-negative edge weights?
- Bellman-Ford
- Dijkstra's (Correct answer)
- Floyd-Warshall
- Kruskal's
Correct answer: Dijkstra's
Dijkstra's algorithm efficiently finds single-source shortest paths when all edge weights are non-negative using a greedy approach.
Question 2: What is a spanning tree of a connected graph?
- A subgraph that contains all vertices and exactly V-1 edges with no cycles (Correct answer)
- A tree that spans the entire memory of the system
- A graph where every vertex has exactly two children
- A path that visits every vertex exactly once
Correct answer: A subgraph that contains all vertices and exactly V-1 edges with no cycles
A spanning tree includes all V vertices of the graph connected by exactly V-1 edges, forming a tree with no cycles.
Question 3: What is topological sorting applicable to?
- Any undirected graph
- Directed Acyclic Graphs (DAGs) only (Correct answer)
- Weighted graphs only
- Complete graphs only
Correct answer: Directed Acyclic Graphs (DAGs) only
Topological sorting orders vertices so that for every directed edge uāv, u comes before v, which is only possible in a DAG.
Question 4: Which graph algorithm can detect negative weight cycles?
- Dijkstra's
- Prim's
- Bellman-Ford (Correct answer)
- BFS
Correct answer: Bellman-Ford
Bellman-Ford can detect negative weight cycles because it will keep relaxing edges indefinitely if a negative cycle exists.
Question 5: In graph theory, what is a bipartite graph?
- A graph with exactly two vertices
- A graph whose vertices can be split into two sets where all edges go between sets (Correct answer)
- A directed graph with two source vertices
- A graph where every vertex has degree 2
Correct answer: A graph whose vertices can be split into two sets where all edges go between sets
A bipartite graph has vertices divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
Question 6: What is the primary goal of Kruskal's algorithm?
- Finding the shortest path between two vertices
- Finding the minimum spanning tree of a graph (Correct answer)
- Detecting cycles in a directed graph
- Performing topological sort
Correct answer: Finding the minimum spanning tree of a graph
Kruskal's algorithm builds a minimum spanning tree by greedily adding the lowest-weight edges that don't form a cycle.
Question 7: What does it mean for a graph to be 'strongly connected'?
- Every vertex has the same degree
- There exists a path between every pair of vertices in both directions (Correct answer)
- The graph has no cycles
- Every vertex is connected to every other vertex by a direct edge
Correct answer: There exists a path between every pair of vertices in both directions
A directed graph is strongly connected if there is a directed path from every vertex to every other vertex.
Data Structures Graphs 2
Which algorithm is used to find the shortest path from a single source to all other vertices in a graph with non-negative edge weights?