BPSC TRE – Graphs, Searching & Sorting Algorithms | Test 1

When a graph is represented as an adjacency list, BFS visits every vertex once and examines every edge once, resulting in a time complexity of O(V + E).

BFS uses a First-In-First-Out (FIFO) Queue to explore adjacent vertices level-by-level.

Depth-First Search (DFS) uses a Last-In-First-Out (LIFO) Stack or function recursion call stack to traverse graph vertices deep into each path.

An Adjacency Matrix uses a 2D V x V array to represent edge connections, taking O($V^2)$ space regardless of the number of edges.

Both Dijkstra's and Bellman-Ford algorithms solve the single-source shortest-path problem for graphs with non-negative edge weights. Dijkstra is typically more efficient, while Bellman-Ford is more general and can also handle negative edges when there is no reachable negative-weight cycle. Therefore, more than one of the above is correct.