Data Structures Graphs 3

Question 1

What is the time complexity of Dijkstra's algorithm when implemented with a binary min-heap?

Accepted Answer

O((V + E) log V)

Answer

O(V²)

Answer

O(V + E)

Answer

O(E log E)

Question 2

Which of the following is NOT a valid graph traversal algorithm?

Accepted Answer

Inorder Traversal

Answer

Breadth-First Search

Answer

Depth-First Search

Answer

Best-First Search

Question 3

What is the key difference between Prim's and Kruskal's algorithms for finding a minimum spanning tree?

Accepted Answer

Prim's grows the tree from a starting vertex, Kruskal's adds the globally cheapest edge each time

Answer

Prim's works on directed graphs, Kruskal's on undirected

Answer

Prim's uses DFS, Kruskal's uses BFS

Answer

Prim's finds shortest paths, Kruskal's finds minimum cuts

Question 4

In a graph with V vertices and E edges, what is the maximum number of edges possible in an undirected simple graph?

Accepted Answer

V(V - 1) / 2

Answer

V

Answer

V - 1

Answer

V²

Question 5

Which algorithm is commonly used to find all strongly connected components in a directed graph?

Accepted Answer

Kosaraju's algorithm

Answer

Dijkstra's algorithm

Answer

Kruskal's algorithm

Answer

Prim's algorithm

Question 6

What problem does the Floyd-Warshall algorithm solve?

Accepted Answer

All-pairs shortest paths

Answer

Single-source shortest path with negative weights

Answer

Minimum spanning tree

Answer

Maximum flow in a network

Question 7

What is an Euler path in a graph?

Accepted Answer

A path that traverses every edge exactly once

Answer

A path that visits every vertex exactly once

Answer

The shortest path between two vertices

Answer

A cycle that passes through all vertices