Test on Graph and breadth-first and depth-first search

Question 1: Unweighted edges are characterized by having an associated numerical value representing properties such as distance or cost.

A. Yes

B. No

Explanation: Unweighted edges are defined as edges without an associated weight, implying all connections have equal 'cost' or 'distance'.

Question 2: Which of the following statements accurately describe the Adjacency Matrix representation of a graph, based on the provided study materials?

A. It requires O(V²) space complexity, regardless of the number of edges.

B. Checking if an edge exists between two specific vertices takes O(1) time.

C. It is best suited for sparse graphs because it only stores existing edges.

D. For undirected graphs, the matrix is symmetric, meaning A[i][j] = A[j][i].

Explanation: The study materials state that the Adjacency Matrix has a space complexity of O(V²), irrespective of the number of edges, making option 0 correct. It also explicitly mentions that checking for an edge between two specific vertices takes O(1) time, confirming option 1. Furthermore, the materials specify that for undirected graphs, the adjacency matrix is symmetric, with A[i][j] = A[j][i], making option 3 correct. Option 2 is incorrect because the materials state that the Adjacency Matrix is best suited for dense graphs, not sparse graphs, as it requires V² storage cells even if many are zero.

Question 3: Network broadcasting is considered an application of Breadth-First Search (BFS).

A. Yes

B. No

Explanation: The study materials explicitly list network broadcasting as one of the key applications for Breadth-First Search (BFS).

Question 4: According to the study materials, which property of Breadth-First Search (BFS) guarantees that it finds the shortest path in an unweighted graph?

A. It processes vertices in O(V + E) time when using an adjacency list.

B. It explores vertices layer by layer, ensuring the first reach is the shortest path.

C. It uses a queue data structure to manage vertex exploration.

D. It identifies all connected components within the graph.

Explanation: The study materials state that 'BFS guarantees finding the shortest path (in terms of the number of edges) from the source vertex to all other reachable vertices in an unweighted graph. This is because it explores vertices layer by layer, ensuring that the first time a vertex is reached, it is via the shortest possible path.' The other options describe other aspects or applications of BFS but not the specific reason for its shortest path guarantee in unweighted graphs.

Question 5: Cycle detection is an application of Depth-First Search.

A. Yes

B. No

Explanation: The study materials list 'Cycle detection' as one of the key applications of Depth-First Search.