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?
You can make the Node a private inner class like this:
public class Graph<T> {
/* code */
private class Node<T> {
/* code */
}
}
For link weights: instead of saving the neighbouring Nodes as a List, save them as a HashMap<Node, Double> which maps each node to a certain weight.
Note: this implementation would actually be a directed graph.
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 Nodes. Edge can have an attribute cost for weighted graph. If you need undirected graph, you can store either two directed Edges 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;
}
}
I suggest that you should learn a thirdparty package named JGraphT, and study how it build a graph with different attributes.