I am currently learning about data structures (eg LinkedList, DoublyLinkedList, ArrayList,...) and I was wondering how to implement a (not directed) graph in Java.
I was thinking about two classes: Graph
and Node<T>
Each node should know to which other nodes it is connected (is a List<Node<T>>
appropriate? What kind of List would be best?)
The Graph
class could then provide methods like boolean contains(T element)
The Node
class would have no other use so how do I restrict visibility so that only Graph
has access?
EDIT: furthermore how can I weigh the connections between nodes? I guess I would need a completely different Implementation than mentioned above since a simple List of connected nodes would not be enough?
A graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes or points together with a set E of edges or arcs or lines, which are 2-element subsets
Following definition should give you a clear way to organise your graph. It consists of Set<Node>
and Set<Edge>
(implementation surely would be HashSet
). Edge
is a pair of from
and to
Node
s. Edge
can have an attribute cost
for weighted graph. If you need undirected graph, you can store either two directed Edge
s indicating one undirected edge or add property undirected
to the Edge
class.
public class Graph<T> {
private Set<Node<T>> nodes;
private Set<Edge<T>> edges;
private class Node<T> {
private T value;
}
private class Edge<T> {
private Node<T> to;
private Node<T> from;
private Number cost;
}
}