NUHMAN.com

Implementing a Weighted Graph in Java

A weighted graph associates a weight (or cost) with each edge between nodes. It’s commonly used in algorithms like Dijkstra or Bellman-Ford.

One of the most space-efficient ways to represent it is using an adjacency list, where each node points to a list of outgoing edges with their respective weights.

🧩 Step 1: Define the Edge Class

Each edge has a target node and a weight.

java

class Edge {
    int target;
    int weight;

    public Edge(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "(" + target + ", " + weight + ")";
    }
}

🏗️ Step 2: Define the Graph Class

We'll use a Map<Integer, List<Edge>> as the adjacency list.

java

import java.util.*;

class Graph {
    private Map<Integer, List<Edge>> adjList;

    public Graph() {
        this.adjList = new HashMap<>();
    }

    // Add a vertex to the graph
    public void addVertex(int vertex) {
        adjList.putIfAbsent(vertex, new ArrayList<>());
    }

    // Add an edge to the graph
    public void addEdge(int source, int target, int weight) {
        addVertex(source);
        addVertex(target);
        adjList.get(source).add(new Edge(target, weight));
    }

    // Get the adjacency list
    public Map<Integer, List<Edge>> getAdjList() {
        return adjList;
    }

    // Print the graph
    public void printGraph() {
        for (int vertex : adjList.keySet()) {
            System.out.print("Vertex " + vertex + " is connected to: ");
            for (Edge edge : adjList.get(vertex)) {
                System.out.print(edge + " ");
            }
            System.out.println();
        }
    }
}

🚀 Step 3: Create and Use the Graph

Here’s how you can create a graph, add edges, and print its structure:

java

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();

        // Add edges
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 3, 4);
        graph.addEdge(3, 4, 2);

        // Print the graph
        graph.printGraph();
    }
}

🖨️ Sample Output

vbnet

Vertex 0 is connected to: (1, 4) (2, 3) 
Vertex 1 is connected to: (2, 1) (3, 2) 
Vertex 2 is connected to: (3, 4) 
Vertex 3 is connected to: (4, 2) 
Vertex 4 is connected to:

📘 Key Concepts

• Adjacency List: Space-efficient graph structure using maps/lists.
• Edge Class: Represents a weighted connection to a target vertex.
• Graph Construction: Easily add vertices and weighted edges.
• Scalability: This structure is ideal for sparse graphs.