Complexity Analysis of Depth-First Search (DFS)

 

Complexity Analysis of Depth-First Search (DFS)

When the graph is represented using adjacency lists, the running time of DFS is:

Θ(V+E)​

The  analysis uses aggregate analysis, just as it does for BFS.

The key idea is:

DFS-VISIT is executed exactly once for every vertex, and the adjacency list of every vertex is examined exactly once.

Let's understand this carefully.

1. DFS Algorithm

Recall the  DFS procedures:

DFS(G)

1   for each vertex u ∈ G.V
2       u.color = WHITE
3       u.π = NIL
4   time = 0

5   for each vertex u ∈ G.V
6       if u.color == WHITE
7           DFS-VISIT(G,u)

and:

DFS-VISIT(G,u)

1   time = time + 1
2   u.d = time
3   u.color = GRAY

4   for each vertex v ∈ G.Adj[u]
5       if v.color == WHITE
6           v.π = u
7           DFS-VISIT(G,v)

8   time = time + 1
9   u.f = time
10  u.color = BLACK

We analyze the different parts separately.

2. Initialization Cost

The first loop of DFS:

for each vertex u ∈ G.V
    u.color = WHITE
    u.π = NIL

visits every vertex exactly once.

There are V vertices.

The work done for each vertex is constant:

  • assign WHITE
  • assign NIL

Therefore:

Θ(V)​

time.

The initialization of:

time = 0

takes:

Θ(1)

and does not affect the overall complexity.

3. How Many Times Is DFS-VISIT Called?

This is the most important observation in the analysis.

The procedure:

DFS-VISIT(G,u)

is called only when:

u.color == WHITE

When DFS-VISIT(G,u) starts, its first action is:

u.color = GRAY

Therefore, once DFS-VISIT has been called for vertex u, that vertex can never again be WHITE.

So:

DFS-VISIT is called exactly once for every vertex​

Since there are V vertices:

V calls to DFS-VISIT​

This remains true even if the graph is disconnected.

4. What About a Disconnected Graph?

This is worth emphasizing because DFS can create multiple trees.

Suppose:

Component 1          Component 2

A --- B              E --- F
|                    |
C                    G

DFS might do:

DFS-VISIT(A)
    ↓
B
    ↓
C

Then, when the outer loop reaches E:

DFS-VISIT(E)
    ↓
F
    ↓
G

So DFS-VISIT is called once for:

A, B, C, E, F, G

Thus:

calls in total.

Some calls are made directly by the outer DFS procedure, while others are made recursively, but every vertex is the argument of exactly one DFS-VISIT call.

5. Cost of One DFS-VISIT Call

Consider:

DFS-VISIT(G,u)

time = time + 1
u.d = time
u.color = GRAY

for each v ∈ Adj[u]
    ...
    
time = time + 1
u.f = time
u.color = BLACK

Apart from the recursive calls, the operations before and after the loop take:

Θ(1)

Therefore, if we temporarily ignore the recursive calls, the cost associated with vertex u is:

which is:

6. How Many Times Is the Adjacency List Scanned?

When DFS-VISIT(G,u) is called, DFS executes:

for each vertex v ∈ G.Adj[u]

The adjacency list of u is scanned.

Since DFS-VISIT is called exactly once for u, the adjacency list:

Adj[u]

is scanned exactly once.

Therefore, across the entire DFS:

Each adjacency list is scanned exactly once​

7. Total Number of Adjacency-List Entries

Now we sum the lengths of all adjacency lists:

u∈V    ∑​∣Adj[u]∣

For a directed graph:

because every directed edge occurs in exactly one adjacency list.

For an undirected graph, every edge occurs twice:

Since 2 is a constant:

Therefore, in either case:

u∈V∑​∣Adj[u]∣=Θ(E)​

8. Total Cost of the Adjacency-List Loops

For every vertex u, the loop executes:

∣Adj[u]∣

times.

Therefore the total number of executions of the loop body is:

u∈V∑​∣Adj[u]∣

which is:

Θ(E)

Hence:

Total adjacency-list scanning cost=Θ(E)​

9. Cost of the Other Operations in DFS-VISIT

Every call to DFS-VISIT performs a constant number of operations outside the adjacency-list loop:

time = time + 1
u.d = time
u.color = GRAY

and later:

time = time + 1
u.f = time
u.color = BLACK

These are all O(1).

Since DFS-VISIT is called V times:

Therefore:

Non-loop DFS-VISIT work=O(V)​

10. What About the Recursive Calls?

This is an important point.

Inside the adjacency-list loop we have:

if v.color == WHITE
    v.π = u
    DFS-VISIT(G,v)

At first glance, the recursive nature may make DFS appear expensive.

But a recursive call occurs only when a vertex is first discovered.

Since each vertex is discovered only once:

At most one DFS-VISIT call per vertex​

Thus there are exactly V total calls to DFS-VISIT.

The recursive calls do not multiply the complexity beyond V.

11. Putting the Costs Together

We have:

Initialization

Θ(V)

DFS-VISIT calls

Θ(V)

Scanning all adjacency lists

Θ(E)

Therefore:

which simplifies to:

Θ(V+E)​

This is the CLRS result.

12. Why Is It Not O(VE)?

This is a common student misconception.

The DFS code contains:

for each vertex u
    ...
    DFS-VISIT(u)

        for each v in Adj[u]

Students may see two loops and think:

But that is incorrect.

The inner loop does not execute E times for every vertex.

For vertex u, it executes only:

∣Adj[u]∣

times.

So the total is:

which is:

Θ(E)

Therefore:

Θ(V+E)​

13. A Concrete Example

Suppose a graph has:

vertices and:

edges.

DFS performs:

Vertex processing

At most:

6

DFS-VISIT calls.

So:

O(6)

vertex-related work.

Edge processing

For a directed graph, there are exactly:

8

adjacency-list entries.

For an undirected graph, there are:

entries.

So the total work is proportional to:

for a directed graph, or:

for an undirected graph.

Both are:

Θ(V+E)​

14. Another Way to See the Analysis

A very usefulexplanation is to associate the work with vertices and edges.

Vertex work

Every vertex is:

  • initialized
  • discovered once
  • finished once

Therefore:

Θ(V)

Edge work

Every adjacency-list entry is examined once.

Therefore:

Θ(E)

Hence:

DFS time=Θ(V)+Θ(E)=Θ(V+E)​

15. DFS with Adjacency Matrix

The result assumes that the graph is represented using adjacency lists.

If the graph is represented using an adjacency matrix, DFS must examine an entire row of the matrix to find the neighbors of a vertex.

For each vertex:

Θ(V)

entries must be examined.

There are V vertices.

Therefore:

and the running time becomes:

Θ(V^2)​

Thus:

Graph Representation    DFS Time
Adjacency List    Θ(V + E)
Adjacency Matrix    Θ(V²)

16. Space Complexity

It is also useful to distinguish running time from space complexity.

DFS maintains several attributes for every vertex:

  • color
  • parent
  • discovery time
  • finishing time

These require:

Θ(V)

space.

The recursive implementation also uses the call stack.

In the worst case, the recursion depth can be V:

A
|
B
|
C
|
D
|
...
|
V

Therefore, the recursion stack can require:

O(V)

space.

Thus, the auxiliary space of DFS, excluding the input graph representation, is:

O(V)​

The adjacency-list representation itself requires:

space.

17. Final  Analysis

The complete analysis can be summarized as:

Work performed    Cost
Initialize all vertices        Θ(V)
Call DFS-VISIT once per vertex        Θ(V)
Examine all adjacency-list entries        Θ(E)
Discovery/finishing operations        Θ(V)
Total        Θ(V + E)

Therefore:

DFS running time=Θ(V+E)​

for an adjacency-list representation.

Although DFS uses recursion and contains nested loops, its running time is linear in the size of the adjacency-list representation because every vertex is processed exactly once and every adjacency-list entry is examined exactly once.


Comments

Post a Comment

Popular posts from this blog

Design and Analysis of Algorithms PCCST502 Semester 5 KTU CS 2024 Scheme - Dr Binu V P

About Me - Dr Binu V P Syllabus and Scheme Model Question Paper Design and Analysis of Algorithms PCCST502 KTU 2024 Scheme Module - I Introduction to Algorithms Criteria for Analyzing Algorithms - Time and Space Complexity Performance Analysis - Time and Space Complexity Asymptotic Analysis , Asymptotic Notations and their properties Comparing Growth Rates using Limits Standard Functions and notations Properties of Asymptotic Notations and common conjuctures Analyzing Algorithms - Insertion Sort ( Example ) Divide and Conquer Strategy using Merge Sort Divide and Conquer - Recurrences Analysis of Recursive Algorithms Iteration Method(Expansion Method) Substitution Method Example Problems - Substitution Method Recursion Tree Method Example Problems - Recursion Tree Method Master Method Example Problems-Master Method Akra-Bazzi Method Recurrences where the Master Theorem cannot be Applied Balanced Search Trees - AVL Trees Module - II Disjoint Sets Disjoint Sets (Union-Find Data Struc...
Read more

Introduction to Algorithms

  Introduction to Algorithms Algorithms form the foundation of Computer Science and software engineering. Every computational task—from searching the internet and processing transactions to artificial intelligence and scientific simulations—relies on algorithms. In the study of Algorithm Analysis and Design , understanding algorithms and their properties is essential before moving to advanced design techniques and complexity analysis. What is an Algorithm? An algorithm is a finite sequence of well-defined computational steps that transforms input into output to solve a particular problem. In simpler terms: An algorithm is a step-by-step procedure for solving a problem in a finite amount of time. An algorithm accepts some input , processes it through a sequence of instructions, and produces the required output . Formal Definition An algorithm can be viewed as: Algorithm = Input + Processing Steps + Output \text{Algorithm} = \text{Input} + \text{Processing Steps} + \...
Read more

Criteria for Analyzing Algorithms- Time and Space Complexity

  Criteria for Analyzing Algorithms Algorithm analysis is the process of evaluating an algorithm with respect to the resources it requires and its performance characteristics. The primary goal is to determine how efficiently an algorithm solves a problem as the size of the input increases. Different algorithms can solve the same problem, but their efficiencies may vary greatly. For example: One sorting algorithm may take seconds. Another may take hours for large datasets. Algorithm analysis helps us: Compare alternative algorithms Predict performance Select optimal solutions Understand scalability Estimate resource consumption Major Criteria for Analyzing Algorithms The important criteria used in algorithm analysis are: Time Complexity Space Complexity 1. Time Complexity Definition Time complexity measures the amount of computational time required by an algorithm as a function of input size. If input size is denoted by n n , then time complexity...
Read more