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

Bellman-Ford

Answer

Floyd-Warshall

Answer

Kruskal's

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 tree that spans the entire memory of the system

Answer

A graph where every vertex has exactly two children

Answer

A path that visits every vertex exactly once

Question 3

What is topological sorting applicable to?

Accepted Answer

Directed Acyclic Graphs (DAGs) only

Answer

Any undirected graph

Answer

Weighted graphs only

Answer

Complete graphs only

Question 4

Which graph algorithm can detect negative weight cycles?

Accepted Answer

Bellman-Ford

Answer

Dijkstra's

Answer

Prim's

Answer

BFS

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 graph with exactly two vertices

Answer

A directed graph with two source vertices

Answer

A graph where every vertex has degree 2

Question 6

What is the primary goal of Kruskal's algorithm?

Accepted Answer

Finding the minimum spanning tree of a graph

Answer

Finding the shortest path between two vertices

Answer

Detecting cycles in a directed graph

Answer

Performing topological sort

Question 7

What does it mean for a graph to be 'strongly connected'?

Accepted Answer

There exists a path between every pair of vertices in both directions

Answer

Every vertex has the same degree

Answer

The graph has no cycles

Answer

Every vertex is connected to every other vertex by a direct edge