Directed vs Undirected Graphs: What is the Difference?
Understand the difference between directed and undirected graphs, in-degree/out-degree, and cycle detection for this interview question.
Expected Interview Answer
A directed graph has edges with a specific one-way direction from one vertex to another, while an undirected graph has edges that are symmetric, meaning a connection between two vertices goes both ways automatically.
In a directed graph, an edge from A to B does not imply an edge from B to A — think of a “follows” relationship on social media, where following someone does not mean they follow back. In an undirected graph, an edge between A and B is inherently bidirectional, like a “friendship” where the connection applies equally to both sides. This distinction changes how algorithms behave: cycle detection differs (a directed graph needs to track the recursion stack, not just visited nodes), and concepts like in-degree versus out-degree only exist for directed graphs. Representation-wise, an undirected graph’s adjacency list adds each edge to both vertices’ neighbor lists, while a directed graph’s adjacency list adds the edge only to the source vertex’s list.
- Directed edges model one-way relationships (follows, prerequisites)
- Undirected edges model inherently mutual relationships (friendship, roads)
- In-degree/out-degree only meaningful for directed graphs
- Cycle detection algorithm differs between the two
AI Mentor Explanation
A directed graph is like a “beat” relationship between teams in a tournament bracket: Team A beating Team B does not mean Team B beat Team A, so the edge only points one way, from winner to loser. An undirected graph is like a “played against” relationship, where if Team A played Team B, that fact is automatically true from both sides at once. Counting how many teams a given team has beaten is an out-degree question that only makes sense on the directed “beat” graph. On the undirected “played against” graph there is no winner-loser direction to count, just a symmetric list of opponents.
Step-by-Step Explanation
Step 1
Determine relationship symmetry
If A relating to B always implies B relating to A, the graph is undirected; otherwise it is directed.
Step 2
Build the adjacency list accordingly
Undirected: add the edge to both vertices’ lists. Directed: add it only to the source vertex’s list.
Step 3
Track in-degree and out-degree for directed graphs
In-degree counts incoming edges, out-degree counts outgoing edges; both only apply to directed graphs.
Step 4
Adjust cycle detection for direction
Directed cycle detection needs a recursion-stack check (three-color DFS); undirected only needs a visited/parent check.
What Interviewer Expects
- Give a clear real-world example of each type
- Explain that undirected edges are added to both adjacency lists
- Mention in-degree/out-degree as directed-only concepts
- Explain the cycle-detection difference between the two
Common Mistakes
- Assuming an edge in a directed graph always implies the reverse edge
- Using undirected cycle detection logic (visited/parent) on a directed graph, giving false results
- Confusing in-degree with out-degree
- Forgetting that trees, as commonly discussed, are typically treated as undirected or rooted-directed depending on context
Best Answer (HR Friendly)
“A directed graph has one-way connections, like following someone on social media, where the relationship does not automatically go both ways. An undirected graph has connections that are automatically mutual, like a friendship. I pick directed when the relationship genuinely has a direction, and undirected when it is inherently symmetric.”
Code Example
class Graph:
def __init__(self, directed=False):
self.adjacency = {}
self.directed = directed
def add_edge(self, u, v):
self.adjacency.setdefault(u, []).append(v)
self.adjacency.setdefault(v, self.adjacency.get(v, []))
if not self.directed:
self.adjacency[v].append(u)
def has_cycle_directed(graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = {v: WHITE for v in graph.adjacency}
def visit(u):
color[u] = GRAY
for v in graph.adjacency[u]:
if color[v] == GRAY:
return True
if color[v] == WHITE and visit(v):
return True
color[u] = BLACK
return False
return any(color[v] == WHITE and visit(v) for v in graph.adjacency)Follow-up Questions
- How does cycle detection differ between directed and undirected graphs?
- What is topological sort, and why does it only apply to directed acyclic graphs?
- How would you convert a directed graph into an undirected one?
- What is a strongly connected component, and why is it directed-graph specific?
MCQ Practice
1. In a directed graph, does an edge from A to B imply an edge from B to A?
Directed edges are one-way by definition; a reverse edge only exists if explicitly added.
2. Which concept only applies meaningfully to directed graphs?
In-degree (incoming edges) and out-degree (outgoing edges) are distinct only when edges have direction.
3. What extra tracking does directed-graph cycle detection need compared to undirected?
Directed cycle detection needs to distinguish nodes fully processed from nodes still on the current path, unlike simple visited tracking for undirected graphs.
Flash Cards
What defines a directed graph edge? — A one-way connection from a source vertex to a target vertex.
What defines an undirected graph edge? — A symmetric connection that applies equally in both directions.
What are in-degree and out-degree? — In-degree counts incoming edges to a vertex; out-degree counts outgoing edges — both only meaningful in directed graphs.
How does undirected cycle detection differ from directed? — Undirected only needs visited/parent tracking; directed needs a recursion-stack (three-color) check to avoid false positives from back edges.