There's a question in my CS class asking that if the graph is a sparse graph, which is n^2 >> m, whether unsorted list with O(n^2) is more efficient than the binary heap O((m+n)logn). I'm a little bit confused with this one because I thought (m+n)logn is always better than n^2. Can anyone give some insights on this?
-
m (the number of edges) varies from 0 to approximately n^2/2. You can see if m is small enough (ie: the graph is sparse enough) then (m+n)log n is better than n^2, and if m is large enough (ie: the graph is dense enough) then (m+n)log n is worse than n^2.Paul Hankin– Paul Hankin2022-04-06 11:05:52 +00:00Commented Apr 6, 2022 at 11:05
-
Hi @Elon, please let me know if the explanation below was helpful.Muhteva– Muhteva2022-04-14 17:53:32 +00:00Commented Apr 14, 2022 at 17:53
Add a comment
|
1 Answer
a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph.
from wikipedia.
Suppose we have a sparse graph with n nodes and m edges. Time complexity of the Prim's Algorithm is O( (n + m) log(n)) if we use a binary heap data structure. If we use an unsorted array (assuming you meant an adjacency matrix), then it becomes O(n^2) as you stated.
Compare the time complexities: O((n + m)log(n)) and O(n^2).
If our graph is sparse, then n > m. Therefore n^2 > mlog(n), which means that it's a better idea to implement the algorithm with a binary heap rather than an adjacency matrix.
If we have a dense graph, then we can at most m = n*(n-1) number of edges for a simple graph.
It means that n^2 < mlog(n) ~ n^2 log(n). Therefore, now it's logical to use an adjacency matrix. If our graph is not simple, then there may be more than one edges between two nodes - therefore we can have more than n* (n-1) edges.
However, the distinction between sparse and dense graphs is rather vague, and depends on the context. Therefore it's not guarantee that in a dense graph we will have m >= n*(n-1) number of nodes.