Java

TOPIC 25 – GRAPH DATA STRUCTURE

LESSON NOTE

IMPLEMENTATION

There are many ways to implement Graphs. In particular, there are many different tweaks to graph implementations that are possible.

IMPLEMENTATION STRATEGY - TABLE

One implementation strategy is to create a table where each vertex is listed as a header for a row and for a column. We then place a "1" where the vertex of the row connects to the vertex of a column and a "0" where they do not connect.

EXAMPLE

IMPLEMENTATION STRATEGY - REFERENCES

Another option to create a graph is to simply hold references to all vertices and edges. Each vertex holds references to its connected neighbours or to edges that specify the connection and its weight.

We will work with such an implementation in the class? Why? Simply because an author made such an implementation available online and it is relatively easy to understand.

WHAT DOES OUR GRAPH LOOK LIKE IN MEMORY?

Unfortunately, because there are so many objects that are referencing other objects, it's a bit of a mess. Below shows a single Vertex object referencing its list of Edges. The edges then reference the original vertex (creating a circular reference) and the other vertex that it connects.

Of course, this would be really messy if we wanted to display a few vertices and all the edges. Plus, the Graph object itself holds references to each vertex and edge.

The good news is that we do not need to worry too much about these details as our focus is on creating Graph structures.