search
Log In
0 votes
141 views

How to understand this: For a connected graph, V = O(E))

SOURCE http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-mst-for-adjacency-list-representation/

prims algorithm time complexity for adjacency list representation. Also same is given in CLRS but no reason 

in Algorithms 141 views
0
It means that the in a connected graph the no. of vertices can never exceed the no. of edges because minimum edges in a connected graph of $n$ nodes will be $O(n)$ and maximum no of edges will be $O(n^2)$
0
Thanks but can you share some resources to understand it better.

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
558 views
On other sources, it is given that we need to assign high priorities to newly inserted element in case of stack otherwise low priority to newly inserted element in case of queue. My doubt here is that shouldn't stack be implemented with max-heap priority queue and queue with min-heap priority queue keeping above assumption of assigning priorities to newly inserted element?
asked Jun 17, 2018 in Algorithms pallaviamu 558 views
0 votes
2 answers
2
828 views
Select a data structure that you have seen previously, and discuss its strengths and limitations.
asked Mar 4, 2016 in DS Anurag_s 828 views
1 vote
0 answers
3
198 views
For a sparse graph $G=(V,E)$ where $|E|=\Theta (V)$ ... Plz tell me difference between Sparse and Dense graph here? How Dense graph implemented and how it make difference for this question
asked Aug 24, 2018 in Algorithms srestha 198 views
1 vote
0 answers
4
304 views
suppose that a graph G has MST already computed. How quickly can we update the MST if we add a new vertex and incident edges to it. I know for the best case scenario when a single edge is incident from the newly added vertex. but for the worst case, when ... many edges. This will end up being linear time since we can reuse part of the DFS that we had already computed before detecting each cycle.
asked Aug 19, 2018 in Algorithms aambazinga 304 views
...