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

enter image description here

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?
    – user7043
    Commented May 21, 2012 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
    Commented May 21, 2012 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
    Commented May 22, 2012 at 4:39
  • Like the one in the picture, so you can assume no edge are missing.
    – han42
    Commented May 22, 2012 at 4:59

1 Answer 1


You may not necessarily need to solve your problem through a specialized data structure; you can, for instance, find an addressing scheme for each node, which allows you to locate neighbouring nodes in O(1) time, and use a generic data structure to navigate.

A simple scheme here would be assigning to each node a tuple (n, m), where n is the tier and m is the index of the node (assuming 0-indexed, for a node to be valid 0 <= m <= n). For any node, deriving all possible neighbour nodes (ni, mi) is straightforward (smth like (n-1, m-1), (n-1,m), (n, m-1), (n, m+1) etc) - of these you keep those who are valid (0 <= mi <= ni < your triangle size here).

The values can be stored in a vector, the index of node (n, m) is, uniquely, n(n+1)/2 + m.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.