Reputation: 109
The objective of this program to implement a graph in JAVA without using any libraries. This is not a homework assignment, just some practice. I am trying to implement a unidirected weighted graph which can be later passed in as a parameter to a Kruskal's or a Prim's algorithm to implement Minimum Spanning Tree. Since I am new to datastructures, I am having a hard time to figure how to go about implementing a graph. Adjacency Matrix/List is something I would want to avoid, can I go forward with the following approach:
/**
* Graph.java: This is the main file.
*/
public class Graph {
public static void main(String[] args)
{
Node n1 = new Node("A");
Node n2 = new Node("B");
Node n3 = new Node("C");
Node n4 = new Node("D");
Node n5 = new Node("E");
Node n6 = new Node("F");
Edges e1 = new Edges(n1, n2, 5);
Edges e2 = new Edges(n1, n3, 3);
Edges e3 = new Edges(n2, n4, 5);
Edges e4 = new Edges(n2, n5, 2);
Edges e5 = new Edges(n3, n6, 7);
}
}
/**
* Node.java class used to represent vertices
*/
public class Node {
private String name;
public Node(String name)
{
this.name = name;
}
}
/**
* Edges.java class used to represent edges.
*/
public class Edges {
private int weight;
private Node sNode;
private Node dNode;
public Edges(Node sNode, Node dNode, int weight)
{
this.sNode = sNode;
this.dNode = dNode;
this.weight = weight;
}
}
Upvotes: 1
Views: 3233
Reputation: 21902
Personally I would keep the edges attached to the nodes. I realize it doubles the number of edges (because they are bidirectional in your case) but it makes traversing nodes a lot faster because you don't have to iterate through your edges to find where you can go next. I realize you mentioned you're not interested in adjacency lists but it seems like a better approach in most cases in terms of performance, although I'm sure you have your reasons. So I'm posting the code anyway, just so it's there for others.
(no get/set on purpose to keep the code succinct)
public class Node {
private String name;
private List<Edge> neighbors;
public Node(String name) {
this.name = name;
}
public void AddUndirectedEdge(Node destination, int weight) {
neighbors.Add(new Edge(destination, weight));
destination.neighbors.Add(new Edge(this, weight));
}
private static class Edge {
public Node destination;
public int weight;
public Edge(Node destination, int weight) {
this.destination = destination;
this.weight = weight;
}
}
}
Upvotes: 5