CODEWITHSUNDEEP
javaalgorithmgraphsparse-matrix
Ardahan
Ardahan

Reputation: 1

Dense and Sparse Run Time

I am trying to make a program which finds the shortest path in a graph. For example, I make 100 vertices and 100 edges then 100 vertices again and 500 edges and measure their run time.

My question is how can I understand whether this is dense or sparse?

Upvotes: 0

Views: 449

Answers (2)

TravisJ
TravisJ

Reputation: 1622

Unfortunately "dense" and "sparse" are not easy to apply to an individual graph. Typically, a sparse graph is one whose edge density is o(n^2) and a dense graph is one whose edge density is not o(n^2). But, this cannot be applied to a single graph just a family of graphs whose size is growing to infinity.

A "heuristic" that you could use is this: If I have a graph on n vertices, (or a family of graphs on n vertices), do I have c*n edges (c is a constant, relatively small), e.g. 2n edges, or 3n edges, or 7n edges? If yes, then you have a sparse graph. Otherwise, do I have something like 1/2 n^2 edges? or 1/3 n^2 edges? or 1/10 n^2 edges? If yes, it is dense.

In your examples, 100 vertices and 500 edges is quite sparse since 5*n edges seems more "reasonable" than 1/200 n^2.

Upvotes: 0

Mike Samuel
Mike Samuel

Reputation: 120546

The density is the ratio of the number of edges in the graph to the number of edges in a complete graph with the same vertex set.

Both of these graphs are reasonably sparse, though the first is sparser.

Often the density of a graph is used to decide what data structure to use to represent a graph

  • An adjacency matrix makes sense for dense graphs where enumerating outbound edges is not a common operation.
  • Edge lists make sense for sparse graphs or where enumerating outbound edges is done frequently.

It's a trade-off though. Adjacency graphs take up more memory as the vertex count scales, but getting a list of the edges between two vertices is fast. Scanning all outbound edges is slow.

Edge lists take less memory as the vertex count increases, looking for edges between two vertices is slower, but enumerating outgoing edges is fast.

Upvotes: 2

Related Questions