# Which data structure to represent a triangular undirected graph

I was wanting to create a graph similar to this in C++:

The one I will implement will have more edges and vertices, but will use this triangle style. I was wanting to create something that I could perform various search algorithms on in order to find shortest paths to selected vertices (or longest without loops etc.). It is an unweighted graph to begin with; however, I was planning to give the edges weights in the future.

I was having some trouble with how I would represent this graph for a couple of reasons: since I want to have more vertices (maybe 105 vertices), any kind of list would be tedious to write out which vertices are connected to which in every object (or is there a way to automate the assignment of members of a vertex object signifying the connectedness?). Also, I was finding it strange trying to implement it in a 2d array because the array is square in nature, and I am dealing with triangles; thinking about the weighting of edges and assigning a value in between two vertices made it even less intuitive with an array.

-
Is it actually a "real" undirected graph, or just a bunch of recursive triangles? Which details need to be stored and which are assumed? – delnan May 21 '12 at 12:20
I was trying to make it a graph since I don't know any other way for finding paths other than breadth first/depth first/Dijkstra so I would need to store which vertices are connected to which so I can make a queue. Maybe later I would store a weight for every pair of vertices somewhere. I guess it doesn't matter if it's "real" because the searches wont create any loops, I don't think. – han42 May 21 '12 at 12:27
Is it going to be always complete like the one shown in the picture? Or is it possible that some elements (small triangles) are missing? – Giorgio May 22 '12 at 4:39
Like the one in the picture, so you can assume no edge are missing. – han42 May 22 '12 at 4:59