16

Why DFS algorithm is having O(V2) compelxity in adjacency matrix representation and O(V+E) in adjacency list representations.

RBT
  • 24,161
  • 21
  • 159
  • 240
user269270
  • 171
  • 1
  • 1
  • 4
  • 1
    possible duplicate of [how time complexity of bfs and dfs depends upon graph representation being used?](http://stackoverflow.com/questions/23925009/how-time-complexity-of-bfs-and-dfs-depends-upon-graph-representation-being-used) – templatetypedef Jun 07 '14 at 20:44

1 Answers1

13

For matrix:

There is one row and one column for each vertex. Position i,j contains 1 if there is an edge from vertex i to vertex j.

The size of the whole matrix is |V|^2

Why the complexity is |V|^2?

Because each position in the matrix is visited once.

For adjacency linked list:

Collection of linked lists with one list for each vertex such that the list for vertex v is the list of all vertices adjacent to vertex v.

Why the complexity is |E|+|V|? Because each position in the adjacency linked list is visited once and there are |V| vertices and |E| edges.

xiaoyu2er
  • 707
  • 8
  • 7