In the article Graph Adjacency Representation - Java Program, we saw how to represent an unweighted graph using adjacency list or adjacency matrix. In this post we'll see what is a weighted graph and how to represent a weighted graph using adjacency list or adjacency matrix in Java.
Weighted graph
In a weighted graph, numerical values called weights are assigned to edges. These weights may represent distance, cost, time etc. For example, if vertices in a graph represent cities, then weight of the edges may mean the distances between the cities, cost t travel between cities or time it takes to drive between cities.
Weighted graph representation using adjacency matrix
An adjacency matrix is a 2-D array in which weight of the edge is used as elements to indicate whether an edge is present between two vertices or not. For example, adjMat[i][j] stores the weight of the edge between i and j vertices.
If the edge is not present it is represented by value as infinity or zero for that cell in the matrix.
For the above image which represents an undirected weighted graph the adjacency matrix can be visualized as shown below. An undirected graph means that the edges don't have direction and you can traverse both ways. You can go from vertex A to vertex B or from vertex B to vertex A.
Weighted Undirected Graph adjacency matrix Java Program
public class WtGraphAdjMatrix {
private int vertices;
private int[][] adjMatrix;
WtGraphAdjMatrix(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) {
WtGraphAdjMatrix graph = new WtGraphAdjMatrix(5);
graph.addEdge(0, 1, 5); //A-B
graph.addEdge(0, 2, 10); //A-C
graph.addEdge(0, 4, 7); //A-E
graph.addEdge(2, 3, 15); //C-D
graph.addEdge(3, 4, 8); //D-E
graph.printGraph();
}
}
Output
0 5 10 0 7 5 0 0 0 0 10 0 0 15 0 0 0 15 0 8 7 0 0 8 0
Weighted Directed Graph adjacency matrix Java Program
In a directed graph you can traverse in only one direction. The allowed direction is shown with an arrow at the end of the edge.
Adjacency matrix for the above weighted directed graph can be visualized as-
Java code for the directed Graph adjacency matrix requires just commenting a single line in the above code for the undirected graph, the reverse link in the matrix.
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;
}
If you run the code after commenting the line, output is-
0 5 10 0 7 0 0 0 0 0 0 0 0 15 0 0 0 0 0 8 0 0 0 0 0
Weighted Graph representation using adjacency list
Another way to represent a weighted graph is using an adjacency list which is an array of lists or a list of lists. Each vertex has an associated list storing all the adjacent vertices. In this associated list each element will have two values connected vertex and the weight between two vertices.
Adjacency list for the above weighted undirected graph can be visualized as-
Weighted Undirected Graph adjacency list Java Program
In the Java program Map and List collections are used to represent adjacency list. Each map key has an associated list to show the adjacent vertices. There is also a class named Edge that encapsulates the adjacent vertex and weight fields.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class WtGraphAdjList {
int vertices;
Map<String, List<Edge>> adjList;
static class Edge{
String destination;
int weight;
Edge(String destination, int weight){
this.destination = destination;
this.weight = weight;
}
}
WtGraphAdjList(int vertices){
this.vertices = vertices;
adjList = new HashMap<>();
}
void addEdge(String source, String destination, int weight) {
adjList.computeIfAbsent(source, k->new ArrayList<>()).add(new Edge(destination, weight));
// For undirected graph
adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(new Edge(source, weight));
}
public void printGraph() {
for(Map.Entry<String, List<Edge>> es : adjList.entrySet()) {
System.out.print("Vertex " + es.getKey() + " connects to: ");
List<Edge> list = es.getValue();
for (Edge e : list) {
System.out.print("[" + e.destination + " with weight " + e.weight + "] ");
}
System.out.println();
}
}
public static void main(String[] args) {
WtGraphAdjList graph = new WtGraphAdjList(5);
graph.addEdge("A", "B", 5);
graph.addEdge("A", "C", 10);
graph.addEdge("A", "E", 7);
graph.addEdge("C", "D", 15);
graph.addEdge("D", "E", 8);
graph.printGraph();
}
}
Output
Vertex A connects to: [B with weight 5] [C with weight 10] [E with weight 7] Vertex B connects to: [A with weight 5] Vertex C connects to: [A with weight 10] [D with weight 15] Vertex D connects to: [C with weight 15] [E with weight 8] Vertex E connects to: [A with weight 7] [D with weight 8]
Weighted Directed Graph adjacency list Java Program
In case of directed graph, you can traverse in only one direction.
Java code for the directed Graph adjacency matrix requires just commenting the line that creates a reverse link in the list.
void addEdge(String source, String destination, int weight) {
adjList.computeIfAbsent(source, k->new ArrayList<>()).add(new Edge(destination, weight));
// For undirected graph
//adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(new Edge(source, weight));
}
With that change the output is-
Vertex A connects to: [B with weight 5] [C with weight 10] [E with weight 7] Vertex C connects to: [D with weight 15] Vertex D connects to: [E with weight 8]
That's all for this topic Weighted Graph Adjacency Representation - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Advanced Tutorial Page
Related Topics
You may also like-
No comments:
Post a Comment