Data Structures Graphs 2

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?

Accepted Answer

Dijkstra's

Answer

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?

Accepted Answer

A subgraph that contains all vertices and exactly V-1 edges with no cycles

Answer

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?

Accepted Answer

Directed Acyclic Graphs (DAGs) only

Answer

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?

Accepted Answer

Bellman-Ford

Answer

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?

Accepted Answer

A graph whose vertices can be split into two sets where all edges go between sets

Answer

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.

Data Structures Practice Test