Graph representation in Java

Question

I have to make an application that uses Graphs (Data Structure) but I don't know how to represent them, and was asking if you can give me some hints.

Should I create a class Vertex and Edge? If yes, what should be their attributes?

Answer 1

I suggest using adjacency lists for graphs.

The simplest way is probably to make a Vertex class, which contains an ArrayList<Vertex> list of links to adjacent vertexes. This is sufficient to represent any graph, you don't need a separate Edge class.

You can add whatever other data attributes you like to the vertex class, but the list of links is all you strictly need.

Note that you can have either directed edges (one-way links) or undirected edges (adjacent vertices point back to each other).

Answer 2

You can represent it the typical ways. See here. For example:

• adjacency matrix (in Java: use a two-dimensional array: [][])
• adjacency list (in Java: use a List)