Menu
I don't understand why inserting an edge in adjacency matrix takes O(1) time. For example we want to add an edge from vertex 3 to 5, in oriented graph we need to change graph[2][4] to 1. In oriented do the other way round also. How can it possible be O(1), if we at least once have to go find the correct row in array, so its already O(|V|)?
535
The space complexity of the adjacency matrix is O ( V 2 ) O(V^{2}) O(V2). An adjacency list is more efficient, in terms of storage requirements, for representing a graph.
I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is O(1) because we can access it directly (i.e: M[i][j]).
The site http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html describes that when an adjacency list is used then, DFS and BFS have complexity O(V+E), and if an adjacency matrix is used, the complexity is O(V2).
The Time complexity of BFS is O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used, where V stands for vertices and E stands for edges.
In 2D array all operations are considered as O(1).
In 2D array you don't go linearly to find the find the row and the column to add the data.
Here
a[i][[j] = k
is an O(1) operation as you can refer the position of the array directly as index rather than going linearly.
However in Linkedlist it is true that you have to go and find the row/column by visiting all the row/column one by one.
195
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
