What is a Graph?
Learn what a graph data structure is, vertices vs edges, adjacency list vs matrix, and how to answer this interview question clearly.
Expected Interview Answer
A graph is a data structure made of nodes (vertices) connected by edges, used to model relationships and connections such as networks, maps, or dependencies, and it can be directed or undirected, weighted or unweighted.
Vertices represent entities and edges represent relationships between them; an edge can carry a weight (like distance or cost) and can be one-directional or bidirectional. Graphs are commonly stored as an adjacency list, which is space-efficient for sparse graphs, or an adjacency matrix, which gives O(1) edge lookup but uses O(V²) space. Traversal algorithms like BFS and DFS, and shortest-path algorithms like Dijkstra, all operate on this vertex-and-edge structure. Trees are actually a special case of graphs — connected, acyclic, with exactly one path between any two nodes.
- Models real-world relationships naturally
- Supports flexible traversal and shortest-path algorithms
- Adjacency list is memory-efficient for sparse data
- Generalizes trees, networks, and dependency structures
AI Mentor Explanation
A graph is like a map of head-to-head rivalries between cricket teams: each team is a node, and a line drawn between two teams is an edge showing they have played each other. Some rivalries are one-way in record-keeping terms, like “Team A beat Team B” as a directed edge, while a simple “played against” link is undirected. A weighted edge could represent how many times two teams have faced off. Traversing this rivalry graph with BFS finds the fewest head-to-head links connecting any two teams, even ones that have never played directly.
Step-by-Step Explanation
Step 1
Identify vertices and edges
Vertices are the entities; edges are the relationships or connections between them.
Step 2
Decide directed vs undirected
Directed edges have a one-way relationship; undirected edges are symmetric.
Step 3
Decide weighted vs unweighted
Weighted edges carry a cost, distance, or value; unweighted edges just represent connection.
Step 4
Pick a representation
Adjacency list for sparse graphs (space-efficient); adjacency matrix for dense graphs (O(1) edge lookup).
What Interviewer Expects
- Define vertices and edges clearly
- Distinguish directed vs undirected and weighted vs unweighted
- Compare adjacency list vs adjacency matrix tradeoffs
- Connect graphs to traversal/shortest-path algorithms (BFS, DFS, Dijkstra)
Common Mistakes
- Confusing a graph with a tree without noting trees are a restricted special case
- Forgetting adjacency matrix costs O(V²) space
- Not distinguishing directed from undirected edges when asked to model a scenario
- Assuming all graphs are connected (many are not)
Best Answer (HR Friendly)
“A graph is a way to represent things and the connections between them, like people in a social network or cities on a map. I use graphs whenever the problem is really about relationships and paths between items, not just a flat list.”
Code Example
class Graph:
def __init__(self, directed=False):
self.adjacency = {}
self.directed = directed
def add_edge(self, u, v, weight=1):
self.adjacency.setdefault(u, []).append((v, weight))
if not self.directed:
self.adjacency.setdefault(v, []).append((u, weight))
def neighbors(self, u):
return self.adjacency.get(u, [])
graph = Graph(directed=True)
graph.add_edge("A", "B", weight=4)
graph.add_edge("B", "C", weight=2)
print(graph.neighbors("A")) # [('B', 4)]Follow-up Questions
- What is the difference between an adjacency list and an adjacency matrix?
- How would you detect if a graph is connected?
- How is a tree a special case of a graph?
- How would you find the shortest path in a weighted graph?
MCQ Practice
1. What does an edge in a graph represent?
Edges represent the relationship or connection between two vertices, optionally carrying direction and weight.
2. What is the space complexity of an adjacency matrix for a graph with V vertices?
An adjacency matrix stores a V by V grid regardless of the number of edges, giving O(V²) space.
3. Which statement correctly relates trees and graphs?
A tree is a special case of a graph that is connected and acyclic, with exactly one path between any two nodes.
Flash Cards
What are the two core components of a graph? — Vertices (nodes) and edges (connections between them).
What is the difference between directed and undirected edges? — Directed edges are one-way; undirected edges are symmetric (two-way).
When is an adjacency list preferred over an adjacency matrix? — For sparse graphs, since it uses O(V + E) space instead of O(V²).
How does a tree relate to a graph? — A tree is a connected, acyclic graph with exactly one path between any two nodes.