Graph Representation Using Adjacency List - The Coding Shala

Home >> Data Structures >> Graph Representation Using Adjacency List

Graph Representation Using Adjacency List

In this post, we will see how to represent a Graph using the Adjacency List. We used an array of lists. The Size of the array is the number of vertices and arr[i] represents the list of vertices adjacent to the ith vertex. The following example shows how to represent a graph using adjacency list:

Graph Representation using Adjacency list Java Program

We have given the number of edges 'E' and vertices 'V' of a bidirectional graph. Now our task is to build a graph through the adjacency list and print the adjacency list for each vertex.

Example 1:

Input:

5 7  //vertex and edges

0 1

0 4

1 2

1 3

1 4

2 3

3 4

Output:

0-> 1-> 4

1-> 0-> 2-> 3-> 4

2-> 1-> 3

3-> 1-> 2-> 4

4-> 0-> 1-> 3

Java Code: 

import java.util.*;

class Graph{
    int v;
    LinkedList<Integer>[] adjList;
    
    Graph(int v){
        this.v = v;
        adjList = new LinkedList[v];
        
        for(int i=0; i<v; i++){
            adjList[i] = new LinkedList();
        }
    }
    
    void Connect(int point1, int point2){
        adjList[point1].add(point2);
        adjList[point2].add(point1); //bidirectional
    }
    
    void Display(){
        for(int i=0; i<v; i++){
            System.out.print(i); //print node
            for(Integer curr : adjList[i]){
                System.out.print("-> "+curr);
            }
            System.out.println();
        }
    }
}

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt(); //no. of test cases
        while(tc-->0){
            int vertex = sc.nextInt();
            int edges = sc.nextInt();
            
            Graph g = new Graph(vertex);
            
            while(edges-->0){
                int v1 = sc.nextInt();
                int v2 = sc.nextInt();
                
                g.Connect(v1, v2);
            }
            
            g.Display();
        }
    }
}

Other Posts You May Like

• Design Linked List
• Introduction to String
• Introduction to Array
• Find Number of Islands
• Height of a Binary Tree

Prev<< Introduction to Graph Data Structure                                                                  NEXT >>#

Please leave a comment below if you like this post or found some error, it will help me to improve my content.