Jump to content
  • Advertisement
Sign in to follow this  
LostSource

Dense and Sparse Graphs

This topic is 4005 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm having the problem of determining what makes a spares (undirected) graph and what makes a dense (undirected) graph. For my personal learning experience I wanted to try and make a graph generator that makes sparse (undirected) and dense (undirected) graphs. The problem is I'm really unclear about the rules that makes a graph dense and what makes a graph sparse. Thank you for any, any, any help at all.

Share this post


Link to post
Share on other sites
Advertisement
It's my understanding that a graph is sparse if the number of connections is on the order of the number of nodes and dense if the number of connections is on the order or the number of nodes squared.

If a graph has n nodes and is expected to have something like 3n+2 connections then it would be sparse. If a graph has n nodes and is expected to have n*n/2-1 connections then it would be dense. This applies more to the sets of graphs that would be expected for an algorithm then it does to any individual graph. For example, this is the type of analysis I would do before deciding whether to use a connection list or an adjacency matrix.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!