In this post we'll see how to write a Java program to create a weighted graph.
What is a weighted graph
A weighted graph is a graph structure where numerical values called weights are assigned to edges. These weights may represent distance, cost, time etc.
Weighted graph may be directed (traversed one way only from source to destination) or undirected.
Weighted graph Java program
A weighted graph in Java can be implemented using either an adjacency matrix or an adjacency list.
If it is a sparse graph, meaning it has relatively few edges compared to the number of vertices, then adjacency list is preferred because it will take less space. It takes less memory because adjacency list only stores actual connections unlike adjacency matrices that allocate space for all possible edges.
If we take the below graph as example-
Then adjacency list can be visualized as-
And adjacency matrix can be visualized as-
Weighted graph Java implementation using adjacency list
import java.util.ArrayList;
import java.util.List;
public class Graph {
int vertices;
List<List<Edge>> adjList;
static class Edge{
int destination;
int weight;
Edge(int destination, int weight){
this.destination = destination;
this.weight = weight;
}
}
Graph(int vertices){
this.vertices = vertices;
adjList = new ArrayList<>();
for(int i = 0; i < vertices; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination, int weight) {
adjList.get(source).add(new Edge(destination, weight));
// For undirected graph need both sides
adjList.get(destination).add(new Edge(source, weight));
}
public void printGraph() {
for(int i = 0; i < vertices; i++) {
System.out.print("Vertex " + i + " connects to: ");
for (Edge e : adjList.get(i)) {
System.out.print("[" + e.destination + " with weight " + e.weight + "] ");
}
System.out.println();
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 30);
graph.addEdge(1, 3, 40);
graph.addEdge(3, 4, 50);
graph.printGraph();
}
}
Output
Vertex 0 connects to: [1 with weight 10] [4 with weight 5] Vertex 1 connects to: [0 with weight 10] [2 with weight 30] [3 with weight 40] Vertex 2 connects to: [1 with weight 30] Vertex 3 connects to: [1 with weight 40] [4 with weight 50] Vertex 4 connects to: [0 with weight 5] [3 with weight 50]
As you can see here adjacency list is declared as an ArrayList of ArrayList, which should be clear from the visual representation of the adjacency list shown above. There is a static inner class Edge with fields as destination and weight.
Weighted graph Java implementation using adjacency matrix
public class GraphMatrix {
private int vertices;
private int[][] adjMatrix;
GraphMatrix(int vertices){
this.vertices = vertices;
adjMatrix = new int[vertices][vertices];
}
public void addEdge(int source, int destination, int weight) {
if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
System.out.println("Invalid edge addition");
return;
}
adjMatrix[source][destination] = weight;
// For undirected graph reverse setting also required
adjMatrix[destination][source] = weight;
}
public void printGraph() {
for(int i = 0; i < adjMatrix.length; i++) {
for(int j = 0; j < adjMatrix[0].length; j++) {
System.out.print(adjMatrix[i][j] + "\t");
}
System.out.println();
}
}
public static void main(String[] args) {
GraphMatrix graph = new GraphMatrix(5);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 5);
graph.addEdge(1, 2, 30);
graph.addEdge(1, 3, 40);
graph.addEdge(3, 4, 50);
graph.printGraph();
}
}
Output
0 10 0 0 5 10 0 30 40 0 0 30 0 0 0 0 40 0 0 50 5 0 0 50 0
That's all for the topic Weighted Graph Java Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment