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?
Add a comment
|
4 Answers
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).
4 Comments
ueg1990
i had a question abt the above implementation of graph. for undirected graphs, when i implement an addEdge function, should i add edges in both directions in the same functions??
mikera
@ueg1990 - you can do it that way. It depends on your data structure, it can certainly speed up some graph searches to have two-way pointers. Another way to do it is a list where each undirected edge is stored once as (a,b) where vertices a and b are in sorted order (e.g. sorted by vertex ID).
ueg1990
but for an undirected graph, if we have an edge from a to b, then by definition we should add an edge from b to a also, right??
abhinav
Each vertex object has ArrayList<Vertex> in it. How to represent all the vertices of a graph ? Map or a list is better ?
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)
Comments
This is not really specific to Java. The two most common representations are adjacency matrix and list. Details here
If you want a library, JGraphT is nice
2 Comments
Andre Roque
My doubt is how i make the code, like: public class Vertex{ ... } public class Edge{ ... } and if that's the case, what i put as attributes. By the way, the objective is to make the Minimum spanning tree with Prim's algorithm. What representation is better?
Andre Roque
I'm supposed to made the structure myself, not to use a library or something
This rather depends on your use case, but you might want to try and leverage a 'graph database' like neo4j
1 Comment
Arnout Engelen
(i know you have to make the structure yourself, but other people with the same question might not :) )