why should I prefer the edge list implementation over the adjacency list implementation in this algorithm’s code?
About the implementation
hello @Senjuti256
for this algorithm u should go with edge list.
because here we need corners of edges .
But we can get the end points of the edges from adjacency list too.
@Senjuti256
yeah u can but then in that case time complexity wil be V *( E+V) also implementation will have some corner cases to avoid counting same edge again .
whereas for edge list it will ve V * E and implentation will be very easy
Pls can you explain me how the complexity in that adjacency list case be V*(E+V)? Sir I am getting too much confused with the time complexity of these algorithms in these graph section. Pls can you help me out pls
V is for outer loop ( we r running it V-1 times )
now E+V is becuase we are using adjaceny list . so to get all edges we need to traverse the whole adjaceny list which is E+V in size
that why V * (E+V)
There I am facing problem because I can understand how the size of adjacency list be V+E? And to traverse it whole why will the time complexity be O(V+E) and not O(E) only?
no not O(E) becuase to get edges u need to visit vertices in adjacency list right?(becuase edge info is stored in terms of vertices)
from there u get information of other corner of edge
thats why O(E+V) whereas in edge list we can get this info directly that why we prefer edgelist
So it means that O(1) for visiting each vertex and then traversing the corresponding list in O(k) time where k is the size of the list attached to that vertex. So for all vertices O(V+E) time complexity and space complexity right?
yeah correct. . . . .
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.