Time Complexity: Directed vs undirected graphs
O(n + m)
0
0
Directed vs undirected graphs in Data Structures Theory - Performance Comparison
Understanding Time Complexity
When working with graphs, it is important to understand how the direction of edges affects the time it takes to process them.
We want to see how the number of edges and their direction influence the work done when exploring a graph.
Scenario Under Consideration
Analyze the time complexity of traversing a graph using Depth-First Search (DFS).
function DFS(node, visited, graph) {
visited.add(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
DFS(neighbor, visited, graph);
}
}
}
// graph can be directed or undirected
// visited is a set to track visited nodes
// graph[node] gives neighbors of node
This code visits all nodes reachable from a starting node by following edges.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Visiting each node and exploring its neighbors.
- How many times: Each node is visited once; each edge is checked once in directed graphs, twice in undirected graphs.
How Execution Grows With Input
As the number of nodes and edges grows, the work to visit all nodes and edges grows roughly in proportion to their total count.
| Input Size (n nodes, m edges) | Approx. Operations |
|---|---|
| 10 nodes, 15 edges | ~25 (10 nodes + 15 edges) |
| 100 nodes, 200 edges | ~300 (100 + 200) |
| 1000 nodes, 5000 edges | ~6000 (1000 + 5000) |
Pattern observation: The total work grows roughly with the sum of nodes and edges.
Final Time Complexity
Time Complexity: O(n + m)
This means the time to traverse the graph grows linearly with the number of nodes plus the number of edges.
Common Mistake
[X] Wrong: "Directed and undirected graphs always take the same time to traverse because they have the same number of edges."
[OK] Correct: In undirected graphs, each edge connects two nodes and is counted twice during traversal (once from each node), so the traversal checks edges differently than in directed graphs.
Interview Connect
Understanding how graph direction affects traversal time helps you explain your approach clearly and choose the right algorithms in real problems.
Self-Check
"What if the graph is represented using an adjacency matrix instead of adjacency lists? How would the time complexity change?"