Data Structures Graphs 1 — Questions and Answers
Question 1: Which data structure is used to implement Breadth-First Search (BFS) in a graph?
- Stack
- Queue (Correct answer)
- Priority Queue
- Deque
Correct answer: Queue
BFS uses a queue to visit nodes level by level, ensuring FIFO order of exploration.
Question 2: In an adjacency matrix representation of a graph with V vertices, what is the space complexity?
- O(V)
- O(E)
- O(V + E)
- O(V²) (Correct answer)
Correct answer: O(V²)
An adjacency matrix stores a V×V grid of values, requiring O(V²) space regardless of the number of edges.
Question 3: What is a directed acyclic graph (DAG)?
- A graph with no vertices
- A graph where all edges are bidirectional
- A directed graph with no cycles (Correct answer)
- A graph where every vertex has equal degree
Correct answer: A directed graph with no cycles
A DAG is a directed graph that contains no directed cycles, making topological sorting possible.
Question 4: Which of the following best describes a weighted graph?
- A graph where each vertex has a numeric label
- A graph where edges have associated numeric values (Correct answer)
- A graph with exactly as many edges as vertices
- A graph where every vertex is connected to every other vertex
Correct answer: A graph where edges have associated numeric values
In a weighted graph, each edge carries a numeric value (weight) representing cost, distance, or capacity.
Question 5: What is the degree of a vertex in an undirected graph?
- The number of vertices in the graph
- The shortest path from that vertex to all others
- The number of edges incident to that vertex (Correct answer)
- The number of vertices adjacent to it minus one
Correct answer: The number of edges incident to that vertex
The degree of a vertex is the count of edges connected to it; self-loops are typically counted twice.
Question 6: Which graph representation is more space-efficient for sparse graphs?
- Adjacency matrix
- Incidence matrix
- Adjacency list (Correct answer)
- Edge matrix
Correct answer: Adjacency list
An adjacency list stores only the existing edges, using O(V + E) space, which is efficient when E << V².
Question 7: What is the time complexity of Depth-First Search (DFS) on a graph represented as an adjacency list?
- O(V)
- O(E)
- O(V + E) (Correct answer)
- O(V × E)
Correct answer: O(V + E)
DFS visits each vertex once and traverses each edge once, giving O(V + E) time complexity.
Data Structures Graphs 1
Which data structure is used to implement Breadth-First Search (BFS) in a graph?