0

I am having a hard time finding information on how Graphs and spanning tree's work and how to construct/structure them. The reason is that I'm using a Delaunay Triangulation algorithm within the LibGDX framwork and this got me an array of indices. I can draw my triangles and points but how to properly setup a graph/MST structure is a problem.

I supply my vertices's as an array of floats as well:

float[] points = new float[6] {80, 30, 40, 45, 0, 10};

Each pair refers to a point of the map. Using DelaunayTriangulator.computeTriangles I get an array of indices, in this case

ShortArray indices = triangulator.computeTriangles(points, false);
System.out.println(indices);
//Output [1, 0, 2, 1, 2, 3]

Now I can draw all the edges and I'm actually doing this just using this data. But I suppose I create a node and graph class to help me out here, I just don't have a clue how this should look. For example, should I have multiples of the same points with different parents, or should I have a single node for a point with a list of points it is connected to? I'm very new to graphs and MST and there is plenty of information on the subject but I cannot find good practical examples.

1

Your idea for "single node for a point with a list of points it is connected to" should work, as it describes an adjacency list. Two canonical ways to represent graphs are via adjacency lists and adjacency matrices, for which the Wikipedia pages have some simple examples:

https://en.wikipedia.org/wiki/Adjacency_list

https://en.wikipedia.org/wiki/Adjacency_matrix

In the case of an adjacency list, it often makes sense to use a dictionary/mapping data structure, e.g. a HashMap in Java.

Just one example to note two additional caveats... let's say the below represents a graph with four nodes and three edges:

(1) -- (2) -- (3)
        |
       (4)

An adjacency list could be represented like so: {1: [2], 2: [1, 3, 4], 3: [2]}

Note that:

  • The above graph is unweighted -- if it were weighted, the the edge weights would need to be represented, e.g. as a possible implementation that follows the above adjacency list {1: [(2, 3)], 2: [(1, 5), (3, 2)...] ...} where 1: (2, 3) means the edge between node 1 and node 2 has weight of 3.
  • The above graph is undirected -- if it were directed, the adjacency list would potentially contain fewer edges.

MSTs are edge subsets of graphs, so usually no additional structure is required to represent them.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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