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 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;
}
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments