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 - The Coding Shala

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
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.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala