Java: how to represent graphs?

user_147601 0
Viewed 122300

I'm implementing some algorithms to teach myself about graphs and how to work with them. What would you recommend is the best way to do that in Java? I was thinking something like this:

public class Vertex {

    private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map.

    //methods to manipulate outnodes
}

public class Graph {
    private ArrayList<Vertex> nodes;
    //algorithms on graphs
}

But I basically just made this up. Is there a better way?

Also, I want it to be able to support variations on vanilla graphs like digraphs, weighted edges, multigraphs, etc.

graph java
12 Answers

When learning algorithms, the programming language (Java) should not be considered in deciding the representation. Each problem could benefit from a unique representation, and moreover designing it can add a bit of learning. Solve the problem first without relying on a particular language, then the representation for any particular language will flow naturally.

Of course, general representations and libraries are useful in real-world applications. But some of them could benefit from some customization as well. Use the other answers to know the different techniques available, but consider customization when appropriate.

user_58005270
Related