Java Program to Describe the Representation of Graph using Incidence List

This Java program,to describe the representation of graph using incident list. Vertices and edges are stored as records or objects. Each vertex stores its incident edges, and each edge stores its incident vertices. This data structure allows the storage of additional data on vertices and edges.

Here is the source code of the Java program to describe the representation of graph using incident list. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.HashMap;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import java.util.Map;
  5. import java.util.Scanner;
  6.  
  7. public class IncidentList
  8. {
  9.     private Map<Integer, List<Integer>> incidentList;
  10.     private int numberOfVertices;
  11.  
  12.     public IncidentList(int numberOfVertices)
  13.     {
  14.         this.numberOfVertices = numberOfVertices;
  15.         incidentList = new HashMap<Integer, List<Integer>>();
  16.  
  17.         for (int vertex = 1; vertex <= numberOfVertices; vertex++)
  18.             incidentList.put(vertex, new LinkedList<Integer>());
  19.     }
  20.  
  21.     public void setEdge(int sourcevertex, int destinationvertex, int edgeNumber)
  22.     {
  23.         List<Integer> slist = incidentList.get(sourcevertex);
  24.         slist.add(edgeNumber);
  25.         return;
  26.     }
  27.  
  28.     public List<Integer> getEdge(int vertex)
  29.     {
  30.         return incidentList.get(vertex);
  31.     }
  32.  
  33.     public void printIncidentList()
  34.     {
  35.         System.out.println("Vertex   EdgeNumber");
  36.         for (int vertex = 1; vertex <= numberOfVertices; vertex++)
  37.         {
  38.             System.out.print(vertex + ":");
  39.             List<Integer> edgeList = getEdge(vertex);
  40.  
  41.             for (int j = 1; ; j++)
  42.             {
  43.                 if (j != edgeList.size())
  44.                     System.out.print(edgeList.get(j - 1) + "\t");
  45.                 else
  46.                 {
  47.                     System.out.print(edgeList.get(j - 1));
  48.                     break;
  49.                 }
  50.             }
  51.             System.out.println();
  52.         }
  53.     }
  54.  
  55.     public static void main(String... arg)
  56.     {
  57.         int numberOfVertices, numberOfEdges;
  58.         int source, destination, edgeNumber;
  59.         int edgeCount = 1;
  60.  
  61.         Scanner scanner = new Scanner(System.in);
  62.         System.out.println("Enter the number of vertices");
  63.         numberOfVertices = scanner.nextInt();
  64.  
  65.         IncidentList incidentList = new IncidentList(numberOfVertices);
  66.         System.out.println("Enter the number of edges");
  67.         numberOfEdges = scanner.nextInt();
  68.  
  69.         System.out.println("Enter the edges format : <edgeNumber> <source> <destination>");
  70.         while (edgeCount <= numberOfEdges)
  71.         {
  72.             edgeNumber = scanner.nextInt();
  73.             source = scanner.nextInt();
  74.             destination = scanner.nextInt();
  75.             incidentList.setEdge(source, destination, edgeNumber);
  76.             edgeCount++;
  77.         }
  78.  
  79.         System.out.println("\nThe Incident List is ");
  80.         incidentList.printIncidentList();
  81.         scanner.close();
  82.     }
  83. }


$javac IterativeDeepening.java
$java IterativeDeepening
Enter the number of vertices
5
Enter the number of edges
5
Enter the edges format : <edgeNumber> <source> <destination>
1 1 2
2 2 4 
3 5 4
4 4 3
5 5 1
 
The Incident List is 
Vertex   EdgeNumber
  1    : 1 5
  2    : 1 2
  3    : 4
  4    : 2 3 4
  5    : 3 5

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.