Graphs implementation in java

Question

I am trying to create a Graph class that uses another class, the Vertex class to represent all the vertices of the graph. I am not sure if I need an Edge class that will represent the possible connections between two vertices, because every vertex can keep track of the other nodes it is connected to. But I am not sure if this is correct. What do you think?

Thank you.

• paulsm4: Q: Is this "homework"? If so, please flag it as such. In any case, take a look at this: en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29
• FranXh: It is not homework. I know how to implement the class with and without using the edge class. I just want to know if it is correct without the Edge class. Anw thanks for the link.

Answer 1

You don't have to use an Edge class. You can use adjacency lists and still represent an unweighted graph correctly. For a weighted graph you need a way to represent edge costs, and thus using an Edge class would be appropriate.

class Graph<E> {
 private List<Vertex<E>> vertices;
 private static class Vertex<E> {
 E elem;
 List<Vertex<E>> neighbors;
 }
}

• FranXh: Yes this is what I was thinking. To keep track of the other vertices without using an Edge class at all. Thank you!!!!
• Andrew T Finnell: All well and good until you need a weighted directed graph. Then you'll need metadata or better yet an Edge class.

Answer 2

Typically, a representation is chosen based in its suitability to the intended use. In this simple example, GraphPanel uses nothing more than a List<Edge> as its model.