Java Program to Represent Graph Using Incidence List

This is a java program to represent graph as a incidence list. The incidence matrix of G is a n × m matrix (b_{ij}), where n and m are the numbers of vertices and edges respectively, such that b_{ij} = 1 if the vertex v_i and edge x_j are incident and 0 otherwise. If this relationship is represented by a list, list is known as incidence list.

Here is the source code of the Java Program to Represent Graph Using Incidence List. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to represent graph as a incidence list
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Represent_Graph_Incidence_List 
{
    private Map<Integer, List<Integer>> incidenceList;
    private int v;
 
    public Represent_Graph_Incidence_List(int vertices) 
    {
        v = vertices;
        incidenceList = new HashMap<Integer, List<Integer>>();
        for (int i = 1; i <= v; i++)
            incidenceList.put(i, new LinkedList<Integer>());
    }
 
    public void setEdge(int to, int from, int edge_number) 
    {
        List<Integer> slist = incidenceList.get(to);
        slist.add(edge_number);
        List<Integer> dlist = incidenceList.get(from);
        dlist.add(edge_number);
 
    }
 
    public List<Integer> getEdge(int vertex) 
    {
        return incidenceList.get(vertex);
    }
 
    public static void main(String args[]) 
    {
        int v, e, count = 1, to, from, edgeNumber;
        Scanner sc = new Scanner(System.in);
        Represent_Graph_Incidence_List glist;
        try 
        {
            System.out.println("Enter the number of vertices: ");
            v = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            e = sc.nextInt();
 
            glist = new Represent_Graph_Incidence_List(v);
 
            System.out
                    .println("Enter the edges in the graph : <edgenumber> <to> <from>");
            while (count <= e) 
            {
                edgeNumber = sc.nextInt();
                to = sc.nextInt();
                from = sc.nextInt();
 
                glist.setEdge(to, from, edgeNumber);
                count++;
            }
 
            System.out
                    .println("The Incidence List Representation of the graph is: ");
 
            System.out.println("Vertex   EdgeNumber");
            for (int vertex = 1; vertex <= v; vertex++) 
            {
                System.out.print(vertex + "\t:");
                List<Integer> edgeList = glist.getEdge(vertex);
                for (int j = 1;; j++) 
                {
                    if (j != edgeList.size())
                        System.out.print(edgeList.get(j - 1) + "\t");
                    else 
                    {
                        System.out.print(edgeList.get(j - 1));
                        break;
                    }
                }
                System.out.println();
            }
        } 
        catch (Exception E) 
        {
            System.out.println("Something went wrong");
        }
        sc.close();
    }
}

Output:

$ javac Represent_Graph_Incidence_List.java
$ java Represent_Graph_Incidence_List
 
Enter the number of vertices: 
5
Enter the number of edges: 
5
Enter the edges in the graph : <edgenumber> <to> <from>
1 1 2
2 2 4 
3 5 4
4 4 3
5 5 1
The Incidence List Representation of the graph is: 
Vertex   EdgeNumber
1	:1	5
2	:1	2
3	:4
4	:2	3	4
5	:3	5

Related posts:

Java Program to Perform LU Decomposition of any Matrix
Multi Dimensional ArrayList in Java
Simplify the DAO with Spring and Java Generics
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Tìm hiểu cơ chế Lazy Evaluation của Stream trong Java 8
Serve Static Resources with Spring
Jackson – Marshall String to JsonNode
Hashtable trong java
Java – Reader to InputStream
JUnit 5 for Kotlin Developers
Java Program to Implement the String Search Algorithm for Short Text Sizes
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
A Guide To UDP In Java
Upload and Display Excel Files with Spring MVC
Java Program to Implement D-ary-Heap
Lập trình đa luồng với CompletableFuture trong Java 8
Netflix Archaius with Various Database Configurations
Java Program to Check if it is a Sparse Matrix
Java – Combine Multiple Collections
Java Program to Implement RoleUnresolvedList API
Static Content in Spring WebFlux
Quản lý bộ nhớ trong Java với Heap Space vs Stack
REST Web service: Tạo ứng dụng Java RESTful Client với Jersey Client 2.x
Java Program to Implement Efficient O(log n) Fibonacci generator
Refactoring Design Pattern với tính năng mới trong Java 8
Guide to java.util.concurrent.Future
Biểu thức Lambda trong Java 8 – Lambda Expressions
SOAP Web service: Authentication trong JAX-WS
Java Program to Implement Brent Cycle Algorithm
Java Program to Implement Min Hash
Quick Guide to @RestClientTest in Spring Boot