Geek Answers Handbook

Representation of large graphs in C ++

There may be similar questions, but I still have some parts that I could not understand. I am trying to imagine an undirected graph without weights, but only 1 for connected and 0 for unconnected. I am trying to imagine a graph (reading from a file) that has 80,500 nodes and more than 5.5 million edges. It was interesting to me:

  • This will be a huge impact if I change the adjacency matrix (the one I am currently using) to the adjacency list. I have no problem with the implementation, just asking if it should be converted to a list?
  • Since I just store 1 and 0 , there is a special data type that does not store it. I use, and I think byte data type will save a lot of time.
  • Any other structure than an adjacency matrix or a list that might be better for this typical problem?
+5
source share
2 answers

Lists of adherence are more efficient in space. Because then you just need to save 5.5 million * 2 numbers = 11,000,000 integers. Assuming you store short integers (2 bytes), you need 22,000,000 bytes.

, 80500 * 80500 = 6 480 250 000 . , 22 , , 6 .

EDIT: eges 4- , 44 000 000 . -, 8 . , 810 031 250 . , 20 .

+4

, , . ( , , , , ). , .

+1

More articles:


All Articles