Directed graph with million of nodes, most with only a few edges but a few with hundreds of thousands

Question

Suppose a directed graph has a million nodes, most nodes have only a few edges, but a few nodes have hundreds of thousands of edges.

To represent this graph, I used an adjacency matrix but, as it turns out, its running time is O(n²) and for adjacency matrix random access is not efficient.

How can I represent this graph in an efficient way that could solve both random access and works faster?

What kind of random access? What are you actually doing with this graph? — harold, Nov 06 '15 at 19:33
http://stackoverflow.com/questions/2218322/what-is-better-adjacency-lists-or-adjacency-matrices-for-graph-problems-in-c — reos, Nov 06 '15 at 20:07

score 1 · Answer 1 · answered Nov 06 '15 at 19:43

1

use the adjacency list, see a description here

answered Nov 06 '15 at 19:43

Leo

1,829
4
27
51

Directed graph with million of nodes, most with only a few edges but a few with hundreds of thousands

1 Answers1