Weighted Graph Implementation – JAVA

We have already discussed about Graph basics. We recommend reading this before you continue to read this article.

What is Weighted Graph?

A Graph is called weighted graph when it has weighted edges which means there are some cost associated with each edge in graph.

Example:

Implementation:

  • Each edge of a graph has an associated numerical value, called a weight.
  • Usually, the edge weights are nonnegative integers.
  • Weighted graphs may be either directed or undirected.
  • The weight of an edge is often referred to as the “cost” of the edge.
  • Will create an Edge class to put weight on each edge

Complete Code:

import java.util.LinkedList;
public class WeightedGraph {
static class Edge {
int source;
int destination;
int weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
static class Graph {
int vertices;
LinkedList<Edge> [] adjacencylist;
Graph(int vertices) {
this.vertices = vertices;
adjacencylist = new LinkedList[vertices];
//initialize adjacency lists for all the vertices
for (int i = 0; i <vertices ; i++) {
adjacencylist[i] = new LinkedList<>();
}
}
public void addEgde(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
adjacencylist[source].addFirst(edge); //for directed graph
}
public void printGraph(){
for (int i = 0; i <vertices ; i++) {
LinkedList<Edge> list = adjacencylist[i];
for (int j = 0; j <list.size() ; j++) {
System.out.println("vertex-" + i + " is connected to " +
list.get(j).destination + " with weight " + list.get(j).weight);
}
}
}
}
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
graph.addEgde(0, 1, 4);
graph.addEgde(0, 2, 3);
graph.addEgde(1, 3, 2);
graph.addEgde(1, 2, 5);
graph.addEgde(2, 3, 7);
graph.addEgde(3, 4, 2);
graph.addEgde(4, 0, 4);
graph.addEgde(4, 1, 4);
graph.addEgde(4, 5, 6);
graph.printGraph();
}
}

view raw
WeightedGraph.java
hosted with ❤ by GitHub


Output:

vertex-0 is connected to 2 with weight 3
vertex-0 is connected to 1 with weight 4
vertex-1 is connected to 2 with weight 5
vertex-1 is connected to 3 with weight 2
vertex-2 is connected to 3 with weight 7
vertex-3 is connected to 4 with weight 2
vertex-4 is connected to 5 with weight 6
vertex-4 is connected to 1 with weight 4
vertex-4 is connected to 0 with weight 4

Reference: here