Open In App

Add and Remove vertex in Adjacency List representation of Graph

Last Updated : 22 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Prerequisites: Linked List, Graph Data Structure

In this article, adding and removing a vertex is discussed in a given adjacency list representation. Let the Directed Graph be: The graph can be represented in the Adjacency List representation as: It is a Linked List representation where the head of the linked list is a vertex in the graph and all the connected nodes are the vertices to which the first vertex is connected. For example, from the graph, it is clear that vertex 0 is connected to vertex 4, 3 and 1. The same is represented in the adjacency list(or Linked List) representation.

Adding a Vertex in the Adjacency List:

To add a vertex in the graph, the adjacency list can be iterated to the place where the insertion is required and the new node can be created using linked list implementation. For example, if 5 needs to be added between vertex 2 and vertex 3 such that vertex 3 points to vertex 5 and vertex 5 points to vertex 2, then a new edge is created between vertex 5 and vertex 3 and a new edge is created from vertex 5 and vertex 2. After adding the vertex, the adjacency list changes to: 

Removing a Vertex in Adjacency List:

To delete a vertex in the graph, iterate through the list of each vertex if an edge is present or not. If the edge is present, then delete the vertex in the same way as delete is performed in a linked list. For example, the adjacency list translates to the below list if vertex 4 is deleted from the list: 
Below is the implementation of the above approach: 

C++ 
#include <iostream>

using namespace std;

// Node to store adjacency list
class AdjNode {
public:
    int vertex;
    AdjNode* next;
    AdjNode(int data)
    {
        vertex = data;
        next = NULL;
    }
};

// Adjacency List representation
class AdjList {
private:
    int v;
    AdjNode** graph;

public:
    AdjList(int vertices)
    {
        v = vertices;
        graph = new AdjNode*[v];
        for (int i = 0; i < v; ++i)
            graph[i] = NULL;
    }

    // Function to add an edge from a source vertex
    // to a destination vertex
    void addEdge(int source, int destination)
    {
        AdjNode* node = new AdjNode(destination);
        node->next = graph[source];
        graph[source] = node;
    }

    // Function to add a vertex between two vertices
    void addVertex(int vk, int source, int destination)
    {
        addEdge(source, vk);
        addEdge(vk, destination);
    }

    // Function to print the graph
    void printGraph()
    {
        for (int i = 0; i < v; ++i) {
            cout << i << " ";
            AdjNode* temp = graph[i];
            while (temp != NULL) {
                cout << "-> " << temp->vertex << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    }

    // Function to delete a vertex
    void delVertex(int k)
    {
        // Iterate through all the vertices of the graph
        for (int i = 0; i < v; ++i) {
            AdjNode* temp = graph[i];
            if (i == k) {
                graph[i] = temp->next;
                temp = graph[i];
            }
            // Delete the vertex using linked list concept
            while (temp != NULL) {
                if (temp->vertex == k) {
                    break;
                }
                AdjNode* prev = temp;
                temp = temp->next;
                if (temp == NULL) {
                    continue;
                }
                prev->next = temp->next;
                temp = NULL;
            }
        }
    }
};

int main()
{
    int V = 6;
    AdjList graph(V);
    graph.addEdge(0, 1);
    graph.addEdge(0, 3);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(3, 2);
    graph.addEdge(4, 3);

    cout << "Initial adjacency list" << endl;
    graph.printGraph();

    // Add vertex
    graph.addVertex(5, 3, 2);
    cout << "Adjacency list after adding vertex" << endl;
    graph.printGraph();

    // Delete vertex
    graph.delVertex(4);
    cout << "Adjacency list after deleting vertex" << endl;
    graph.printGraph();

    return 0;
}
Java 
// GFG
// JAVA implementation of the above approach
// Implementing Linked List representation

import java.util.*;

// Node to store adjacency list
class AdjNode {
    int vertex;
    AdjNode next;

    public AdjNode(int data)
    {
        vertex = data;
        next = null;
    }
}

// Adjacency List representation
class AdjList {
    private int v;
    private AdjNode[] graph;

    public AdjList(int vertices)
    {
        v = vertices;
        graph = new AdjNode[v];
        for (int i = 0; i < v; ++i) {
            graph[i] = null;
        }
    }

    // Function to add an edge from a source vertex
    // to a destination vertex
    public void addEdge(int source, int destination)
    {
        AdjNode node = new AdjNode(destination);
        node.next = graph[source];
        graph[source] = node;
    }

    // Function to add a vertex between two vertices
    public void addVertex(int vk, int source,
                          int destination)
    {
        addEdge(source, vk);
        addEdge(vk, destination);
    }

    // Function to print the graph
    public void printGraph()
    {
        for (int i = 0; i < v; ++i) {
            System.out.print(i + " ");
            AdjNode temp = graph[i];
            while (temp != null) {
                System.out.print("-> " + temp.vertex + " ");
                temp = temp.next;
            }
            System.out.println();
        }
    }

    // Function to delete a vertex
    public void delVertex(int k)
    {
        // Iterate through all the vertices of the graph
        for (int i = 0; i < v; ++i) {
            AdjNode temp = graph[i];
            if (i == k) {
                graph[i] = temp.next;
                temp = graph[i];
            }
            // Delete the vertex using linked list concept
            while (temp != null) {
                if (temp.vertex == k) {
                    break;
                }
                AdjNode prev = temp;
                temp = temp.next;
                if (temp == null) {
                    continue;
                }
                prev.next = temp.next;
                temp = null;
            }
        }
    }
}

public class Main {
    public static void main(String[] args)
    {
        int V = 6;
        AdjList graph = new AdjList(V);
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(3, 2);
        graph.addEdge(4, 3);

        System.out.println("Initial adjacency list");
        graph.printGraph();

        // Add vertex
        graph.addVertex(5, 3, 2);
        System.out.println(
            "Adjacency list after adding vertex");
        graph.printGraph();

        // Delete vertex
        graph.delVertex(4);
        System.out.println(
            "Adjacency list after deleting vertex");
        graph.printGraph();
    }
}
// This code is written by SUNDARAM.
Python 
# Python implementation of the above approach
# Implementing Linked List representation


class AdjNode(object):
    def __init__(self, data):
        self.vertex = data
        self.next = None

# Adjacency List representation


class AdjList(object):

    def __init__(self, vertices):
        self.v = vertices
        self.graph = [None] * self.v

    # Function to add an edge from a source vertex
    # to a destination vertex
    def addedge(self, source, destination):
        node = AdjNode(destination)
        node.next = self.graph[source]
        self.graph[source] = node

    # Function to call the above function.
    def addvertex(self, vk, source, destination):
        self.addedge(source, vk)
        self.addedge(vk, destination)

    # Function to print the graph
    def print_graph(self):
        for i in range(self.v):
            print(i, end=" ")
            temp = self.graph[i]
            while temp:
                print("->", temp.vertex, end=" ")
                temp = temp.next
            print("\n")

    # Function to delete a vertex
    def delvertex(self, k):

        # Iterating through all the vertices of the graph
        for i in range(self.v):
            temp = self.graph[i]
            if i == k:
                self.graph[i] = temp.next
                temp = self.graph[i]

            # Delete the vertex using linked list concept
            if temp:
                if temp.vertex == k:
                    self.graph[i] = temp.next
                    temp = None

            while temp:
                if temp.vertex == k:
                    break
                prev = temp
                temp = temp.next

            if temp == None:
                continue  # Move to the next vertex

            prev.next = temp.next
            temp = None


# Driver code
if __name__ == "__main__":

    V = 6
    graph = AdjList(V)
    graph.addedge(0, 1)
    graph.addedge(0, 3)
    graph.addedge(0, 4)
    graph.addedge(1, 2)
    graph.addedge(3, 2)
    graph.addedge(4, 3)

    print("Initial adjacency list")
    graph.print_graph()

    # Add vertex
    graph.addvertex(5, 3, 2)
    print("Adjacency list after adding vertex")
    graph.print_graph()

    # Delete vertex
    graph.delvertex(4)
    print("Adjacency list after deleting vertex")
    graph.print_graph()
C# 
// C# implementation of the above approach Implementing
// Linked List representation

using System;

// Node to store adjacency list
class AdjNode {
    public int vertex;
    public AdjNode next;

    public AdjNode(int data)
    {
        vertex = data;
        next = null;
    }
}

// Adjacency List representation
class AdjList {
    private int v;
    private AdjNode[] graph;

    public AdjList(int vertices)
    {
        v = vertices;
        graph = new AdjNode[v];
        for (int i = 0; i < v; ++i) {
            graph[i] = null;
        }
    }

    // Function to add an edge from a source vertex
    // to a destination vertex
    public void addEdge(int source, int destination)
    {
        AdjNode node = new AdjNode(destination);
        node.next = graph[source];
        graph[source] = node;
    }

    // Function to add a vertex between two vertices
    public void addVertex(int vk, int source,
                          int destination)
    {
        addEdge(source, vk);
        addEdge(vk, destination);
    }

    // Function to print the graph
    public void printGraph()
    {
        for (int i = 0; i < v; ++i) {
            Console.Write(i + " ");
            AdjNode temp = graph[i];
            while (temp != null) {
                Console.Write("-> " + temp.vertex + " ");
                temp = temp.next;
            }
            Console.WriteLine();
        }
    }

    // Function to delete a vertex
    public void delVertex(int k)
    {
        // Iterate through all the vertices of the graph
        for (int i = 0; i < v; ++i) {
            AdjNode temp = graph[i];
            if (i == k) {
                graph[i] = temp.next;
                temp = graph[i];
            }
            // Delete the vertex using linked list concept
            while (temp != null) {
                if (temp.vertex == k) {
                    break;
                }
                AdjNode prev = temp;
                temp = temp.next;
                if (temp == null) {
                    continue;
                }
                prev.next = temp.next;
                temp = null;
            }
        }
    }
}

public class GFG {

    static public void Main()
    {

        // Code
        int V = 6;
        AdjList graph = new AdjList(V);
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(3, 2);
        graph.addEdge(4, 3);

        Console.WriteLine("Initial adjacency list");
        graph.printGraph();

        // Add vertex
        graph.addVertex(5, 3, 2);
        Console.WriteLine(
            "Adjacency list after adding vertex");
        graph.printGraph();

        // Delete vertex
        graph.delVertex(4);
        Console.WriteLine(
            "Adjacency list after deleting vertex");
        graph.printGraph();
    }
}

// This code is contributed by karthik.
Javascript 
// JavaScript code implementation:

// Node to store adjacency list
class AdjNode {
  constructor(data) {
    this.vertex = data;
    this.next = null;
  }
}

// Adjacency List representation
class AdjList {
  constructor(vertices) {
    this.v = vertices;
    this.graph = new Array(this.v).fill(null);
  }

  // Function to add an edge from a source vertex to a destination vertex
  addEdge(source, destination) {
    const node = new AdjNode(destination);
    node.next = this.graph[source];
    this.graph[source] = node;
  }

  // Function to add a vertex between two vertices
  addVertex(vk, source, destination) {
    this.addEdge(source, vk);
    this.addEdge(vk, destination);
  }

  // Function to print the graph
  printGraph() {
    for (let i = 0; i < this.v; ++i) {
      let str = i + " ";
      let temp = this.graph[i];
      while (temp != null) {
        str += "-> " + temp.vertex + " ";
        temp = temp.next;
      }
      console.log(str + "<br>");
    }
  }

  // Function to delete a vertex
  delVertex(k) {
    // Iterate through all the vertices of the graph
    for (let i = 0; i < this.v; ++i) {
      let temp = this.graph[i];
      if (i === k) {
        this.graph[i] = temp.next;
        temp = this.graph[i];
      }
      // Delete the vertex using linked list concept
      while (temp != null) {
        if (temp.vertex === k) {
          break;
        }
        let prev = temp;
        temp = temp.next;
        if (temp == null) {
          continue;
        }
        prev.next = temp.next;
        temp = null;
      }
    }
  }
}

const V = 6;
const graph = new AdjList(V);
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(3, 2);
graph.addEdge(4, 3);

console.log("Initial adjacency list<br>");
graph.printGraph();

// Add vertex
graph.addVertex(5, 3, 2);
console.log("Adjacency list after adding vertex<br>");
graph.printGraph();

// Delete vertex
graph.delVertex(4);
console.log("Adjacency list after deleting vertex<br>");
graph.printGraph();

// This code is contributed by lokesh.

Output
Initial adjacency list
0 -> 4 -> 3 -> 1 
1 -> 2 
2 
3 -> 2 
4 -> 3 
5 
Adjacency list after adding vertex
0 -> 4 -> 3 -> 1 
1 -> 2 
2 
3 -> 5 -> 2 
4 -> 3 
5 -> 2 
Adjacency list after deleting vertex...


R
RADHIKAGARG
Improve
Next Article
Add and Remove vertex in Adjacency Matrix representation of Graph

Similar Reads

Add and Remove vertex in Adjacency Matrix representation of Graph
A graph is a presentation of a set of entities where some pairs of entities are linked by a connection. Interconnected entities are represented by points referred to as vertices, and the connections between the vertices are termed as edges. Formally, a graph is a pair of sets (V, E), where V is a collection of vertices, and E is a collection of edg
15+ min read
Comparison between Adjacency List and Adjacency Matrix representation of Graph
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. In this article, we will understand the difference between the ways of representation of the graph. A graph can be represented in mainly two ways. They ar
4 min read
Convert Adjacency Matrix to Adjacency List representation of Graph
Prerequisite: Graph and its representations Given a adjacency matrix representation of a Graph. The task is to convert the given Adjacency Matrix to Adjacency List representation. Examples: Input: arr[][] = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ] Output: The adjacency list is: 0 -&gt; 2 1 -&gt; 2 2 -&gt; 0 -&gt; 1Input: arr[][] = [ [0, 1, 0, 0, 1], [1,
6 min read
Convert Adjacency List to Adjacency Matrix representation of a Graph
Given an adjacency list representation of a Graph, the task is to convert the given Adjacency List to Adjacency Matrix representation. Examples: Input: adjList[] = {{0 --&gt; 1 --&gt; 3}, {1 --&gt; 2}, {2 --&gt; 3}} Output: 0 1 0 10 0 1 00 0 0 10 0 0 0 Input: adjList[] = {{0 --&gt; 1 --&gt; 4}, {1 --&gt; 0 --&gt; 2 --&gt; 3 --&gt; 4}, {2 --&gt; 1 -
9 min read
Add and Remove Edge in Adjacency List representation of a Graph
Prerequisites: Graph and Its RepresentationIn this article, adding and removing edge is discussed in a given adjacency list representation. A vector has been used to implement the graph using adjacency list representation. It is used to store the adjacency lists of all the vertices. The vertex number is used as the index in this vector. Example: Be
8 min read
Add and Remove Edge in Adjacency Matrix representation of a Graph
Prerequisites: Graph and its representationsGiven an adjacency matrix g[][] of a graph consisting of N vertices, the task is to modify the matrix after insertion of all edges[] and removal of edge between vertices (X, Y). In an adjacency matrix, if an edge exists between vertices i and j of the graph, then g[i][j] = 1 and g[j][i] = 1. If no edge ex
13 min read
Check if incoming edges in a vertex of directed graph is equal to vertex itself or not
Given a directed Graph G(V, E) with V vertices and E edges, the task is to check that for all vertices of the given graph, the incoming edges in a vertex is equal to the vertex itself or not. Examples: Input: Output: Yes Explanation: For vertex 0 there are 0 incoming edges, for vertex 1 there is 1 incoming edge. Same for vertex 2 nd 3. Approach: Th
6 min read
Check if vertex X lies in subgraph of vertex Y for the given Graph
Given an undirected graph and two vertices X and Y, our task is to check whether the vertex X lies in the subgraph of the vertex Y. Examples: Input: X = 2, Y = 3 Output: No Explanation: Subgraph of a vertex Y = 3 is set of all the vertex which lies below Y and are reachable by Y. Here subgraph of 3 contains {6} not 2. Input: X = 6, Y = 1 Output: Ye
10 min read
Check if every vertex triplet in graph contains two vertices connected to third vertex
Given an undirected graph with N vertices and K edges, the task is to check if for every combination of three vertices in the graph, there exists two vertices which are connected to third vertex. In other words, for every vertex triplet (a, b, c), if there exists a path between a and c, then there should also exist a path between b and c. Examples:
9 min read
Level order traversal by converting N-ary Tree into adjacency list representation with K as root node
Given the root node of an N-ary tree and an integer K, the task is to convert the given tree into adjacency list representation and print the level order traversal considering vertex K as the root node. Example: Input: Tree in the image below, K = 5 Output:5 1 9 10 11 2 3 4 6 7 8 Input: Tree in the image below, K = 5 Output:5 12 3 4 7 8 Approach: T
9 min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox