Thursday, October 16, 2025

Java Program to Add and Remove in Graph

In this post we'll see how to write Java program for addition and removal from a graph data structure.

Addition and removal in a graph can be done in the following scenarios-

  1. Adding a vertex
  2. Adding an edge
  3. Removing a vertex
  4. Removing an edge

Another thing to consider while writing Java program for graph addition, removal is the representation of graph-

  1. Graph is represented using adjacency matrix
  2. Graph is represented using adjacency list

Please refer following posts to know more about graph representations- Graph Adjacency Representation - Java Program
Weighted Graph Adjacency Representation - Java Program

Graph addition removal Java program - Adjacency list representation

In the program, Map storing lists of its neighbours is used as adjacency list representation.

A separate class called Vertex is also there to encapsulate vertex information.

Adding a vertex means, adding that vertex as a key in the Map, along with a new ArrayList as a value.

Adding an edge means adding both the start vertex and the end vertex and the reverse link too if it is an undirected graph.

Removing a vertex means removing that particular key from the Map. Also remove where ever the removed vertex is listed as neighbour for other vertices.

Removing an edge means removing the link from starting point to end point, reverse link for the same vertices should also be removed for an undirected graph.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * Insert, delete in graph represented as adjacency list
 */
public class GraphDSAL {
  Map<Vertex, List<Vertex>> adjList = new HashMap<>();
  // Vertex class as nested class
  static class Vertex{
    String label;
    Vertex(String label){
      this.label = label;
    }
    public String getLabel() {
      return label;
    }
    public void setLabel(String label) {
      this.label = label;
    }
    @Override
    public int hashCode() {
      return Objects.hash(label);
    }
    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      Vertex other = (Vertex) obj;
      return Objects.equals(label, other.label);
    }
    
  }
  
  public void addVertex(Vertex v) {
    adjList.putIfAbsent(v, new ArrayList<Vertex>());
  }
  
  public void removeVertex(Vertex v) {
    // remove vertex
    adjList.remove(v);
    // remove where ever the removed vertex is listed as neighbour
    adjList.values().forEach(e -> e.remove(v));
  }
  
  public void addEdge(String source, String destination) {
    Vertex vs = new Vertex(source);
      Vertex vd = new Vertex(destination);
    if(!adjList.containsKey(vs)) {
      addVertex(vs);
    }
    if(!adjList.containsKey(vd)) {
      addVertex(vd);
    }
    adjList.get(vs).add(vd);
    // Reverse link also required for undirected graph
    adjList.get(vd).add(vs);
  }
  
  public void removeEdge(String source, String destination) {
    Vertex vs = new Vertex(source);
      Vertex vd = new Vertex(destination);
      adjList.get(vs).remove(vd);
      // Reverse link removal also required for undirected graph
      adjList.get(vd).remove(vs);
  }
  // Method to display graph
  public void printGraph() {
    adjList.forEach((k, v) -> {
      System.out.print("Vertex " + k.getLabel() + " connects to ");
      v.forEach(e -> System.out.print(e.getLabel() + " "));
      System.out.println();
    });
  }

  public static void main(String[] args) {
    GraphDSAL graph = new GraphDSAL();
    graph.addVertex(new Vertex("A"));
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("A", "E");
    graph.addEdge("C", "D");
    graph.addEdge("D", "E");
    
    graph.printGraph();
    
    graph.removeVertex(new Vertex("A"));
    //graph.removeEdge("A", "C");
    System.out.println("After removal");
    graph.printGraph();
        
  }

}

Output

Vertex A connects to B C E 
Vertex B connects to A 
Vertex C connects to A D 
Vertex D connects to C E 
Vertex E connects to A D 
After removal
Vertex B connects to 
Vertex C connects to D 
Vertex D connects to C E 
Vertex E connects to D 

Graph addition removal Java program - Adjacency matrix representation

When graph is represented as an adjacency matrix, that means using a 2-D array to represent a graph.

Adding a vertex means, incrementing the rows and columns of the adjacency matrix by 1 to accommodate new vertex. Copy the rows and columns from the old adjacency matrix to this new one and then assign the new adjacency matrix as the adjacency matrix of the graph.

Adding an edge means changing the row, column value to 1 for the array element, mapping to the start and end vertices for the added edge.

Removing a vertex means, decrementing the rows and columns of the adjacency matrix to represent removal of a vertex. While copying the rows and columns from the old adjacency matrix to this new one ensure that the values for the row and column represented by the removed vertex are not added to the new adjacency matrix. Assign the new adjacency matrix as the adjacency matrix of the graph.

Removing an edge means changing the row, column value to 0 for the array element, mapping to the start and end vertices for the removed edge.

/**
 * Insert, delete in graph represented as adjacency matrix
 */
public class GraphDSAM {
  private int vertices;
  private int[][] adjMatrix;
  
  GraphDSAM(int vertices){
    this.vertices = vertices;
    adjMatrix = new int[vertices][vertices];
  }
  
  public void addEdge(int source, int destination) {
    if((source < 0 || source >= vertices) || (destination < 0 || destination >= vertices)) {
      System.out.println("Invalid edge addition");
      return;
    }
    adjMatrix[source][destination] = 1;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = 1;
  }
  
  public void removeEdge(int source, int destination) {
    if((source < 0 || source >= vertices) || (destination < 0 || destination >= vertices)) {
      System.out.println("Invalid edge removal");
      return;
    }
    adjMatrix[source][destination] = 0;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = 0;
  }
  
  public void addVertex() {
    int changedSize = vertices + 1;
    int[][] changedAdjMatrix = new int[changedSize][changedSize];

    // Copy existing connections
    for (int i = 0; i < vertices; i++) {
      for (int j = 0; j < vertices; j++) {
        changedAdjMatrix[i][j] = adjMatrix[i][j];
      }
    }
    this.adjMatrix = changedAdjMatrix;
    vertices = changedSize;
  }
  
  public void removeVertex(int v) {
    if(v < 0 || v >= vertices){
      System.out.println("Invalid vertex removal");
      return;
    }
    int[][] changedAdjMatrix = new int[vertices-1][vertices-1];
    // maintaining row for changedAdjMatrix
    int tempRow = 0;
    
    for(int i = 0; i < adjMatrix.length; i++) {
      if(i == v) {
        continue;
      }
      // maintaining col for changedAdjMatrix
      int tempCol = 0;
      for(int j = 0; j < adjMatrix[0].length; j++) {
        if(j == v) {
          continue;
        }
        changedAdjMatrix[tempRow][tempCol] = adjMatrix[i][j];
        tempCol++;
      }
      tempRow++;
      
    }
    this.adjMatrix = changedAdjMatrix;
  }
  
  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) {
    GraphDSAM graph = new GraphDSAM(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2); 
    graph.addEdge(0, 4); 
    graph.addEdge(2, 3); 
    graph.addEdge(3, 4); 

    graph.printGraph();
    
    System.out.println("After adding a vertex");
    graph.addVertex();
    graph.addEdge(3, 5); 
    graph.printGraph();
    System.out.println("After removal");
    graph.removeEdge(3, 4);
    graph.printGraph();

  }

}

Output

0	1	1	0	1	
1	0	0	0	0	
1	0	0	1	0	
0	0	1	0	1	
1	0	0	1	0	
After adding a vertex
0	1	1	0	1	0	
1	0	0	0	0	0	
1	0	0	1	0	0	
0	0	1	0	1	1	
1	0	0	1	0	0	
0	0	0	1	0	0	
After removal
0	1	1	0	1	0	
1	0	0	0	0	0	
1	0	0	1	0	0	
0	0	1	0	0	1	
1	0	0	0	0	0	
0	0	0	1	0	0	

That's all for this topic Java Program to Add and Remove in Graph. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Binary Tree Traversal Using Breadth First Search Java Program
  2. Binary Tree Traversal Using Depth First Search Java Program
  3. Binary Tree Implementation in Java - Insertion, Traversal And Search
  4. Sorted Linked List In Java
  5. Deque Implementation in Java Using Doubly Linked List

You may also like-

  1. Rabin-Karp Algorithm For Pattern Search - Java Program
  2. Two Sum - Elements in Array With Given Sum Java Program
  3. Java Program - Sieve of Sundaram to Find Prime Numbers
  4. How to Create Password Protected Zip File in Java
  5. Java CyclicBarrier With Examples
  6. static Reference to The Non-static Method or Field Error
  7. Difference Between @Controller And @RestController Annotations in Spring
  8. How to Create a Custom Structural Directive in Angular

No comments:

Post a Comment