0

I need to generate a graph using integer arrays. Edges of the graphs are kept as edges[e][2] where e is the number of edges. I need my graph to be connected, i.e. you should be able to traverse from all nodes to all nodes.

edges[0] = {0,5} means an edge connects node 0 and node 5. Could you suggest an algorithm, please?

And please keep in mind that i will generate graphs with millions of nodes, so that it is better if algorithm complexity isn't too high.

Improve this question
2
  • What did you try so far? Where is the problem? Commented Apr 3, 2012 at 12:45
  • this is not an homework. a part of my academic study. Commented Apr 3, 2012 at 12:59

1 Answer 1

Reset to default
1

If each node is directly connected to each node, don't store all the edges ;)

If each node is reachable from each other node, but not necessarily directly, use an adjacency matrix. That's the simplest way if you need to use integer arrays.

If the matrix is sparse, I would store it differently, though. The best encoding depends on what graph algorithms you want to use it for. The wikipedia article on sparce matrices) lists the major ones.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.