3 Replies - 4583 Views - Last Post: 24 March 2011 - 06:48 AM Rate Topic: -----

#1 ellemrac721   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 03-February 11

Need help understanding time complexity for graph structure

Posted 23 March 2011 - 01:34 PM

Hi, I need help understanding this bit from this:

"Assume that graph is connected. Depth-first search visits every vertex in the graph and checks every edge its edge. Therefore, DFS complexity is O(V + E). As it was mentioned before, if an adjacency matrix is used for a graph representation, then all edges, adjacent to a vertex can't be found efficiently, that results in O(V^2) complexity."
From: http://www.algolist....th-first_search

Why does it take θ(n^2) for a connected graph structure (represented by adjacency matrix) to perform DFS?

I don't understand the O(V^2) part completely for adjacency matrices. Really grateful if someone could explain it thoroughly :)

Thanks in advance!

Is This A Good Question/Topic? 0
  • +

Replies To: Need help understanding time complexity for graph structure

#2 Alex_H   User is offline

  • New D.I.C Head

Reputation: 22
  • View blog
  • Posts: 44
  • Joined: 27-January 11

Re: Need help understanding time complexity for graph structure

Posted 23 March 2011 - 02:00 PM

The reason for the different complexity is because you are using an adjacency matrix. It takes more time to find all the edges in an adjacency matrix then it would if you represent the connected graph in a different way.

For example pretend that we have the graph and its adjacency matrix shown below:Posted Image

This matrix is for a connected graph with 6 vertices. When we start a DFS, the first thing we need to do is find all the edges from this matrix. To do that, we must search each cell of this matrix and see if it is an edge or not. This of course takes V^2 steps. Now that we have the edges, we can perform the depth first seach which takes approximatly V + E steps. So all together we have: V^2 + V + E which in Big O notation is O(V^2).
Was This Post Helpful? 2
  • +
  • -

#3 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12566
  • View blog
  • Posts: 45,688
  • Joined: 27-December 08

Re: Need help understanding time complexity for graph structure

Posted 23 March 2011 - 05:34 PM

Personally, I dislike matrix representations of Graphs. They aren't intuitive, since Graphs are Node-based structures, not list/matrix based. Matrices have their uses in Graph theory, like finding the number of paths of length x from A to B by exponentiating the matrix. When dealing with programming Graph algorithms, you will often find the Node-based structure easier to deal with. Alex_H is spot on with his explanation, illustrating why Node-based Graphs are better in this case. :)
Was This Post Helpful? 0
  • +
  • -

#4 ellemrac721   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 03-February 11

Re: Need help understanding time complexity for graph structure

Posted 24 March 2011 - 06:48 AM

Thanks so much for the help :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1