You are not logged in. Please login at www.codechef.com to post your questions!

×

Adjacency lists & Adjacency matrices

I recently implemented DFS by making an adjacency list using a vector of vectors and was pretty pleased about that. But yesterday, I read here http://web.stanford.edu/class/cs97si/ on the basic Graph algorithms slide that an array of vectors is slower than plain arrays.

For me, vectors of vectors was pretty easy to code but just arrays was hard as I had trouble just adding an edge and manipulating the 2 arrays. What do the rest of you recommend me to use taking into account time and memory efficiency? If you recommend arrays, could you also give me a good resource which explains how to easily implement it?

Also, I read that we should use an adjacency matrix only when the graph is dense (No. of vertices is almost equal to no. of edges). But what if the constraints (around 10^5 edges) are such that it is too large even for the global scope? What do I use to represent the edge relations in such a case?

asked 04 Jan '15, 16:24

sandy999's gravatar image

2★sandy999
39111638
accept rate: 10%

edited 04 Jan '15, 16:25


I have never come across any slowness issues using an array of vectors.

But do use an array of vectors, not a vector of vectors. Usually you know the number of vertexes, so

vector<int> e[MAXIMUM_NO_OF_VERTICES]

should be sufficient, where e[v][i] is the ith vertex that v is connected to. It's also easier IMO than a vector of vectors.

Also, dense means that the number of edges is nearly the number of pairs of vertices, not number of vertexes. A vertex with number of edges around the number of vertices is a very sparse graph.

An adjacency matrix is feasible only if N^2 is pretty small. For number of vertexes around 10^5 the size of an adjacency matrix is 4*10^10 (around 40 GB) which is certainly not going to fit within any memory limit. In such cases you must use an adjacency list, which will fit in O(number of edges) memory space. Number of edges can be around 10^5, it still takes up only around 800 KB. (4 bytes per int * 2 vertices per edge * 100000 edges)

link

answered 04 Jan '15, 16:42

superty's gravatar image

3★superty
36417
accept rate: 31%

edited 04 Jan '15, 16:48

1

Thanks a lot @superty :)

(05 Jan '15, 15:33) sandy9992★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×368

question asked: 04 Jan '15, 16:24

question was seen: 14,620 times

last updated: 05 Jan '15, 15:33