3
$\begingroup$

If a graph with $v$ vertices is represented in the form of adjacency matrix .

Then, adding a new vertex to the existing graph requires how much time ?

Is it $O(v^2)$ or $O(2v)$ .

We have the adjacency matrix of the graph with $v$ vertices , by adding a new vertex we have to enter a row (for edges leaving the new vertex) and a column(for incident edges of new vertex) and an entry for self loop . So ,there is a need to update $2v+1$ new entries. So i am in favor of $O(2v)$. Did i miss something ? Is there any need for creating new empty matrix of size $(v+1)^2$ and then copying $v^2$ existing elements and updating remaining $2v+1$ entries of new vertex , which takes $O(v^2)$ time.

Thanks in advance .

$\endgroup$
5
$\begingroup$

This is completely implementation-dependent. As you say, if you need to copy the existing matrix, you have $n^2$ entries to copy, which takes $\Theta(n^2)$ steps; if you only need to add the new entries (for example, if you've pre-allocated a large matrix but you're adding the vertices one at a time), you only need to write $O(n)$ entries each time.

If you did have to copy the matrix every time you grow it, a more time-efficient option would be to start with a small matrix (say, $10\times 10$) and double it every time it fills up. Doing it that way means you need fewer expensive copies but the potential down-side is that you could waste a lot of space. For example, if your graph ends up having 21 vertices, you'll have allocated a $40\times 40$ matrix, most of which is empty. You could mitigate that by not growing the array so aggressively (say, making it 25% bigger each time it grows, instead of 100%).

$\endgroup$
  • $\begingroup$ So if memory is not an issue , then is both adjacency list and adjacency matrix are comparable (time) for inserting a new vertex ? or which one is better ? $\endgroup$ – hanugm Aug 14 '14 at 10:02
  • 1
    $\begingroup$ @hanugm in my opinion, inserting a new vertex V to adjacency list should be an O(1) operation if and only if you consider adding related edges of vertex V as a separate operation. $\endgroup$ – Usman Jan 4 '17 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.