Implementation of Graph in Java

Types of Graphs

1. Directed Graph (Digraph)

A directed graph in Java is a graph where edges have a direction, meaning they point from one vertex to another. The direction implies a one-way relationship. These are often represented using adjacency lists or matrices in Java.
Example: In a social media platform, if User A follows User B, but not vice versa, this is a directed relationship.

graph.addEdge("A", "B"); // A ➝ B

Real-world uses include task scheduling, web page links, and citation networks.

2. Undirected Graph

An undirected graph Java example would involve edges that do not have a specific direction. The connection between two nodes goes both ways. If A is connected to B, then B is also connected to A.
Example: A road network where roads between cities allow travel in both directions.

graph.addEdge("A", "B"); // A — B

This type is used in modeling relationships like friendships, network topologies, or file sharing.

3. Weighted Graph

A weighted graph has values (weights) assigned to its edges. These weights often represent cost, distance, or time.
Example: In a navigation app, the roads (edges) have weights like distance in kilometers.

graph.addEdge("A", "B", 5); // Weight of 5 units between A and B

Weighted graphs are crucial in algorithms like Dijkstra’s and Prim’s.

4. Unweighted Graph

An unweighted graph has no values on its edges. All edges are treated equally.
Example: A friend recommendation system, where each friend connection is treated the same, regardless of closeness.

graph.addEdge("User1", "User2"

These graphs are useful when the presence of a connection is more important than the cost of that connection.

Comparison Table

Why Learn Graph Implementation in Java?

1. Real-World Applications of Graphs

Graphs are fundamental in solving real-world problems across domains. In social networks, graphs represent user relationships. In navigation systems, cities are nodes and roads are edges with distances (weights). Recommendation systems (like Netflix or Amazon) use graphs to find related products.
In Java, you can use libraries like JGraphT or implement custom structures using HashMap<String, List<String>> for unweighted graphs or HashMap<String, List<Edge>> for weighted ones. Mastery of graph structures helps developers model and solve dynamic, connected problems efficiently.

2. Graphs in Interviews and Competitive Programming

Graph-related questions are a staple in coding interviews at Google, Amazon, and other top tech companies. Interviewers test knowledge of BFS, DFS, Dijkstra’s, Topological Sort, and Union-Find.
Understanding graph implementation in Java helps in solving questions involving shortest paths, cycle detection, and connectivity. It’s also essential in competitive programming, where efficient graph solutions can determine your ranking in contests.

Implementation of Graph - Using Adjacency Matrix

A graph can be represented using an adjacency Matrix. An adjacency matrix is a square matrix of size V * V, where V is the number of vertices in the graph. The values in the matrix show whether a given pair of nodes are adjacent to each other in the graph structure or not. In the adjacency matrix, 1 represents an edge from node X to node Y, while 0 represents no edge from X to Y.

For an undirected graph, the adjacency matrix is always symmetric. For a weighted graph, instead of 0 and 1, the value of weights w is used to indicate that there is an edge from I to j.

Before moving to the code, let us look at the adjacency matrix of directed, undirected and weighted graphs.
 

Directed Graph
Undirected Graph
Weighted Graph

Algorithm

• Make a matrix of size V*V where V is the number of vertices in the graph. 
• A new vertex in the graph is added by connecting it with other vertices, and an edge is thus formed. To indicate that there is an edge from vertex i to vertex j, mark matrix[i][j] = 1 and if there is no edge then mark matrix[i][j] = 0.
   

Implementation

The below program is used to implement an undirected graph using Adjacency Matrix representation.

public class AdjacencyMatrix {
    // A variable to store the number of vertices in the graph
    int vertexCount;
    // A variable to store the adjacency matrix of the graph
    int matrix[][];

    // Constructor to create an adjacency matrix
    // of dimensions vertexCount*vertexCount
    AdjacencyMatrix(int vertexCount) {
        this.vertexCount = vertexCount;
        matrix = new int[vertexCount][vertexCount];
        /*
         * The matrix[][] for vertexCount = 4 will look like this upon initialization
         * '-' indicates 0
         * [-, -, -, -] 
         * [-, -, -, -] 
         * [-, -, -, -] 
         * [-, -, -, -]
         */
    }

    // Function to add an edge from source to destination
    // i.e. there is an edge from source to destination
    // O(1) time complexity
    public void addEdgeInMatrix(int source, int destination) {
        // Add a link from source to destination
        matrix[source][destination] = 1;
        
        // Add a link from destination to source
        matrix[destination][source] = 1;
    }

    // Function to delete an edge from source to destination
    // O(1) time complexity
    public void deleteEdgeInMatrix(int source, int destination)
    {
        // Deleting an edge from source to destination
        matrix[source][destination] = 0;

        // Deleting edge from destination to source
        matrix[destination][source] = 0;
    }
    // Utility function to print a graph
    public void printGraph() {
        System.out.println("Representation of Graph in the form of Adjacency Matrix: ");
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                System.out.print(matrix[i][j] + "   ");
            }

            System.out.println();
        }

        for (int i = 0; i < vertexCount; i++) {
            System.out.print("Vertex " + i + " is connected to: ");
            for (int j = 0; j < vertexCount; j++) {
                if (matrix[i][j] == 1) {
                    System.out.print(j + " ");
                }
            }

            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyMatrix adj = new AdjacencyMatrix(5);
        // 0 ----- 1
        adj.addEdgeInMatrix(0, 1);

        // 0 ----- 1
        // |
        // |
        // |
        // 4
        adj.addEdgeInMatrix(0, 4);

        // 0 ----- 1 ---- 2
        // |
        // |
        // |
        // 4
        adj.addEdgeInMatrix(1, 2);

        // 0 ----->1 ---> 2
        // |       |
        // |       |
        // |       |
        // 4       3
        adj.addEdgeInMatrix(1, 3);

        // 0 ----->1 ---> 2
        // |     / |
        // |    /  |
        // |   /   |
        // 4  /    3
        adj.addEdgeInMatrix(1, 4);

        // 0 ----->1----2
        // |    / |   /
        // |   /  |  /
        // |  /   | /
        // 4       3 
        adj.addEdgeInMatrix(2, 3);
        // 0 ----->1----2
        // |    / |   /
        // |   /  |  /
        // |  /   | /
        // 4  ----3 
        adj.addEdgeInMatrix(3, 4);

        adj.printGraph();
        System.out.println("\nDeleting an edge from 3 to 4");
        adj.deleteEdgeInMatrix(3, 4);
        adj.printGraph();

    }
}

The output of the above program is:

The time complexity for adding an edge in O(1).

The space complexity is O(V^2), where V is the number of vertices in the graph.

Note that in the case of a weighted graph instead of 0 and 1, respective weights will be added in the adjacency matrix.  

Recommended topic: Application of graph data structure

Advantages of Adjacency Matrix Representation

1. Insertion and deletion of an edge can be done in O(1) time complexity.
2. We can determine if two edges are adjacent to each other in constant time.

Disadvantages of Adjacency Matrix Representation

1. Using adjacency Matrix consumes a lot of memory of the order of V^2. In the case of graphs with few edges, this leads to a wastage of memory.
2. Traversal of a graph requires O(V^2) time complexity in case of adjacency matrix representation.
    

Implementation of Graph - Using Adjacency List

A graph can also be represented in the form of an adjacency list. An adjacency list represents a graph as an array of linked lists, wherein the index of the array represents a vertex and each element of the linked list represents other vertices that form an edge with the vertex.

Consider the following example wherein there is a directed graph of 5 nodes. The graph along with its adjacency list representation is shown in the below figure.

An array represents each node. A linked list is linked to each node, which represents the link of one node to another node, note that the node numbers are not in any specific order, though it's convenient to list the nodes in ascending order as shown in the below adjacency list representation.
 

In implementing a Graph representation of Graphs using Adjacency List, we will use an ArrayList of ArrayList. ArrayList is a class of Collection Framework; you may read more about it here. 

Implementation

// Adjacency List representation in Java
import java.util.*;

public class AdjacencyList {
    int vertexCount;

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int source, int destination) {
        // Adding an edge from source to destination
        adj.get(source).add(destination);
        // Adding an edge from destination to source
        adj.get(destination).add(source);
    }

    // A utility function to delete an edge from source index of outer arraylist to
    // destination index of inner array list.
    static void deleteEdge(ArrayList<ArrayList<Integer>> adj, int source, int destination) {
        adj.get(source).remove(destination);

    }

    static void printGraph(ArrayList<ArrayList<Integer>> adj) {
        System.out.println("Adjacency List representation of Graph: ");
        for (int i = 0; i < adj.size(); i++) {
            System.out.println("Adjacency List of vertex " + i);
            System.out.print(i + " -> ");
            for (int j = 0; j < adj.get(i).size(); j++)
                System.out.print(adj.get(i).get(j) + " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // Basically we are forming a graph with vertexCount vertices
        // To do that an ArrayList of ArrayLists is created and each outer
        // ArrayList will contain vertexCount elements. Each vertex will have
        // an ArrayList of vertices that are adjacent to it.
        int vertexCount = 5;

        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(vertexCount);
        for (int i = 0; i < vertexCount; i++)
            adj.add(new ArrayList<Integer>());

        // Add edges to the graph

        // Adding an edge from 0 to 1
        addEdge(adj, 0, 1);

        // Adding an edge from 0 to 4
        addEdge(adj, 0, 4);

        // Adding an edge from 1 to 2
        addEdge(adj, 1, 2);

        // Adding an edge from 1 to 3
        addEdge(adj, 1, 3);

        // Adding an edge from 2 to 3
        addEdge(adj, 2, 3);

        // Adding an edge from 3 to 4
        addEdge(adj, 3, 4);
        printGraph(adj);


        System.out.println("After removing an edge from graph");
        deleteEdge(adj, 1, 2);
        printGraph(adj);

    }

}

The output of the above program is:

The time complexity of the get() and add() method of ArrayList is O(1). So the time complexity of the above program is O(1)

The space complexity of the above program is O(V + E) where V is the number of vertices and E is the number of edges formed by vertices. The space complexity will be O(V^2) in the worst case of a complete graph.

Check out this article - Upcasting and Downcasting in Java

Must Read Difference between ArrayList and LinkedList

Real-World Use Cases of Graphs in Java

1. Social Network Graphs

In social media platforms like Facebook or LinkedIn, each user is a node, and a connection (friend or follower) is an edge. This structure forms a graph that can be used for exploring relationships.
Java developers can use adjacency lists (Map<String, List<String>>) to model this graph. Algorithms like BFS or DFS help suggest mutual friends, detect communities, or measure network influence. For instance, finding second-degree connections (friend of a friend) is a BFS traversal problem.
Graph implementations in Java are critical for developing social networking features such as recommendations, feed personalization, and blocking/reporting relationships.

2. Navigation and Routing Systems

Apps like Google Maps model roads and intersections as weighted graphs, where nodes represent locations, and edges represent roads with distances or travel time as weights.
Java applications often implement Dijkstra’s algorithm or A Search* to find the shortest path between two points. A graph may be represented using a Map<String, List<Edge>> where Edge holds the destination and cost.
These graph techniques allow for real-time route optimization, traffic-based rerouting, and multi-stop pathfinding. Such implementations are core to logistics, delivery systems, and transport apps.

3. Dependency Graphs in Build Tools

Build tools like Maven and Gradle use dependency graphs to manage project build orders. Each module or library is a node, and an edge represents a dependency.
To determine the correct build sequence, Java uses topological sorting on Directed Acyclic Graphs (DAGs). For example, before compiling module B that depends on module A, the graph ensures A is built first.
In Java, such graphs can be implemented using a directed adjacency list (Map<String, List<String>>) and resolved using DFS with visited flags. Dependency graphs help avoid circular dependencies and maintain build integrity.

Frequently Asked Questions

Q1) What are Graphs in Data Structure?

Ans 1) A graph is a non-linear data structure that consists of nodes and edges. Formally, a graph can be defined as an ordered set G(V, E) where V represents the vertices and E represents the edges used to connect these vertices. 

You must read about Graph Theory and Graph Representation to know more about Graphs in addition to this blog.

Q2) How to represent a graph using an adjacency list?

Ans 2) A graph is represented using an adjacency list as shown below:

You may read more about it here.

Q3) How to represent a graph apart from the adjacency list and an adjacency matrix?

Ans 3) An edge list can also be used from the graph representation using the adjacency list and an adjacency matrix. An edge list is just a list or array of edges; to represent an edge, we have an array of two vertex numbers of the vertices that the edges are incident on.

The edge list of the above graph is [0, 1], [0, 2], [1, 2], [1, 4], [2, 3], [3, 4]]

Conclusion

Graphs are one of the most important data structures from an interview perspective in product-based companies. This article discusses the implementation of Graph in Java. With this done you must practice more and more questions related to Graphs on Coding Ninjas Studio. 

Recommended Readings:

• Has-A Relationship in Java