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(); | |
| } | |
| } |
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