Wednesday, October 15, 2025

Java Program to Check Prime Number

In this post we'll see a Java program to check whether given number is a prime number or not.

As we know that a number is a prime number if it is a natural number greater than 1 and it can be divided either by 1 or by the number itself. As example- 2, 3, 5, 7, 11, 13, 17 ….

First thing that may come to mind, while writing Java program for checking prime number, is to have a variable in a for loop that starts from 2 (as 1 will always divide the number) and increment it by one until it reaches the number that is checked for being prime number or not. In every iteration of the loop divide the number by variable, if remainder is zero at any time then the checked number is not a prime number.

That loop would look something like this-

for(int i = 2; i < num; i++){
  if(num % i == 0){
    flag = false;
    break;
  }
}

But that logic can be made more efficient. To check if a number is prime or not you need to run a loop starting from 2 till number/2 to check if number has any divisor.

For example, if number is 8 then you just need to check till 4 (8/2) to see if it divides by any number or not. Same way if you have a number 15 you just need to check till 7 to see if it divides completely by any number or not. We'll use the same logic to write our program to check for prime number.

Java program to check prime number or not

import java.util.Scanner;

public class PrimeCheck {
  public static void main(String[] args) {
    // take input from the user
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter number: ");

    int num = sc.nextInt();
    boolean flag = isPrime(num);
    if(flag){
      System.out.println(num + " is a prime number.");
    }else{
      System.out.println(num + " is not a prime number.");
    }
  }
    
  private static boolean isPrime(int num){
    boolean flag = true;
    // loop from 2, increment it till number/2
    for(int i = 2; i <= num/2; i++){
      // no remainder, means divides 
      if(num % i == 0){
        flag = false;
        break;
      }
    }
    return flag;
  }
}

Output

Enter number: 
16
16 is not a prime number.

Enter number: 
31
31 is a prime number.

Here scanner class is used to get input from the user.

Refer How to Read Input From Console in Java to see other ways to get input from user.

That's all for this topic Java Program to Check Prime Number. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Java Program to Display Prime Numbers
  2. Java Program - Sieve of Eratosthenes to Find Prime Numbers
  3. Java Program - Sieve of Sundaram to Find Prime Numbers
  4. Armstrong Number or Not Java Program
  5. Fibonacci Series Program in Java

You may also like-

  1. Reading File in Java Using BufferedReader
  2. Count Number of Words in a String Java Program
  3. Abstraction in Java
  4. Inheritance in Java
  5. static Keyword in Java With Examples
  6. Difference Between ReentrantLock and Synchronized in Java
  7. Dependency Injection in Spring Framework
  8. Difference Between Checked And Unchecked Exceptions in Java

Java Program to Display Prime Numbers

This post shows a Java program to display prime numbers.

As we know that a number is a prime number if it is a natural number greater than 1 and it can be divided either by 1 or by the number itself. As example- 2, 3, 5, 7, 11, 13, 17 ….

To check if a number is prime or not you need to run a loop starting from 2 till number/2 to check if number has any divisor.

For example, if number is 8 then you just need to check till 4 (8/2) to see if it divides by any number or not. Same way if you have a number 15 you just need to check till 7 to see if it divides completely by any number or not. We'll use the same logic to write our program to display prime numbers up to the given upper range.

Looking for more efficient way to display prime numbers. Refer these sieving algorithms- Java Program - Sieve of Eratosthenes to Find Prime Numbers, Java Program - Sieve of Sundaram to Find Prime Numbers

Java Program - Sieve of Sundaram to Find Prime Numbers

In this post we'll see how to write a program in Java to find prime numbers up to the given limit using Sieve of Sundaram algorithm.

Sieve of Sundaram algorithm

Sieve of Sundaram algorithm takes only odd numbers into consideration, completely eliminating even numbers from the beginning itself.

Two main points about the algorithm are-

  1. Let’s say we need prime number with in the range 0..n. Every odd number with in this range can be expressed as 2x+1, where x lies between 0 to n. So, to get odd numbers between 0..n we need to run loop till (n - 1)/2 only.
    For example, if you need all the prime number in the range 1 to 50 then you need to run the loop till (50 – 1)/2 = 24.5 which can be taken as 24. With that 2x+1 gives us 2 * 24 + 1= 49 which is the last odd number with in the range.
    Note that there is only one even prime number which is 2, that is why this algorithm takes that as a special case and concentrates only on odd numbers.
  2. In order to eliminate odd numbers which are not prime numbers x = i + j + 2ij equation is used.

How does sieve of Sundaram algorithm work

  1. A boolean array of length (n-1)/2 is created with all elements as false initially.
  2. With in the nested loops, mark the elements with indices of the form i + j + 2ij as true. This process eliminates all the odd composite numbers.
  3. Then you are left with only those elements, still marked as false in the array, which are prime numbers and of the form 2i+1.

Sieve of Sundaram Java program

public class SieveOfSundaram {
  private static void getPrimes(int n) {
  int limit = (n - 1) / 2;
  boolean[] marked = new boolean[limit + 1];

  // Mark all numbers of the form i + j + 2ij as true 
  // where 1 <= i <= j
  for (int i = 1; i <= limit; i++) {
    for (int j = i; (i + j + 2 * i * j) <= limit; j++) {
      marked[i + j + 2 * i * j] = true;
    }
  }

  // print even prime number
  if (n >= 2)
    System.out.print(2 + " ");
  // Print rest of the prime numbers with in the limit
  for (int i = 1; i <= limit; i++)
    if (marked[i] == false)
      System.out.print(2 * i + 1 + " ");

  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the number for range: ");
    int n = sc.nextInt();
    getPrimes(n);
    sc.close();

  }
}

Output

Enter the number for range: 
50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 

Explanation for the equation

You can verify that equation i+j+2ij maps to odd composite numbers, let's take n = 25 then the limit is 12.

With in this nested loop-

for (int i = 1; i <= limit; i++) {
  for (int j = i; (i + j + 2 * i * j) <= limit; j++) {
    marked[i + j + 2 * i * j] = true;
  }
}
When i = 1, j = 1, i+j+2ij = 4 so 2i+1 is 9 which is an odd composite number. 
i=1, j=2, then i+j+2ij = 7 so 2i+1 is 15 which is an odd composite number. 
i=1, j=3 then i+j+2ij = 10 so 2i+1 is 21 which is an odd composite number. 
Then i becomes 2, 
i=2, j=2 then i+j+2ij = 12 so 2i+1 is 25 which is an odd composite number. 

That's what this nested loop achieves by marking elements in the array.

Time and space complexity of Sieve of Sundaram algorithm

The time complexity of Sieve of Sundaram algorithm is O(n log n). The outer loop runs (n-1)/2 times which can be taken as O(n). The inner loop runs in logarithmic time as the number of iterations required to complete the loop keeps on decreasing.

A Boolean array of size (n - 1)/2 + 1 is required so the space complexity is O(n).

That's all for this topic Java Program - Sieve of Sundaram to Find Prime Numbers. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page


Related Topics

  1. Java Program - Sieve of Eratosthenes to Find Prime Numbers
  2. Fibonacci Series Program in Java
  3. Arrange Non-Negative Integers to Form Largest Number - Java Program
  4. Convert float to int in Java
  5. Binary Search Program in Java

You may also like-

  1. Insertion Sort Program in Java
  2. Check if Given String or Number is a Palindrome Java Program
  3. KMP Algorithm For Pattern Search - Java Program
  4. Difference Between Two Dates in Java
  5. Java Sealed Classes and Interfaces
  6. String Comparison in Java equals(), compareTo(), startsWith() Methods
  7. Comparing Two Strings in Python
  8. JavaScript filter Method With Examples

Monday, October 13, 2025

Java Programs

String

  1. Count Number of Words in a String Java Program
  2. Count Number of Times Each Character Appears in a String Java Program
  3. Check if Given String or Number is a Palindrome Java Program
  4. Java Program to Find The Longest Palindrome in a Given String
  5. How to Reverse a String in Java
  6. Reverse Each Word in a String Java Program
  7. Check Given Strings Anagram or Not Java Program
  8. Add Double Quotes to a String Java Program
  9. Split a String Java Program
  10. Find All Permutations of a Given String Java Program
  11. If Given String Sub-Sequence of Another String in Java
  12. Java Program to Find First Non-Repeated Character in a Given String
  13. Find The First Repeated Character in a String Java Program
  14. Find Duplicate Characters in a String With Repetition Count Java Program
  15. Convert String to int in Java
  16. Convert String to Byte Array Java Program
  17. Convert String to float in Java
  18. Convert String to double in Java
  19. Convert Char to String And String to Char in Java
  20. Convert String to Char Array in Java
  21. Removing Spaces Between Words in a String Java Program
  22. Manacher's Algorithm to Find The Longest Palindrome - Java Program
  23. Longest Prefix Suffix Java Program
  24. KMP Algorithm For Pattern Search - Java Program
  25. Rabin-Karp Algorithm For Pattern Search - Java Program
  26. Z Algorithm For Pattern Search - Java Program

Numbers

  1. Armstrong Number or Not Java Program
  2. Java Program to Reverse a Number
  3. Swap or Exchange Two Numbers Without Using Any Temporary Variable Java Program
  4. Java Program to Check Prime Number
  5. Java Program to Display Prime Numbers
  6. Java Program - Sieve of Eratosthenes to Find Prime Numbers
  7. Java Program - Sieve of Sundaram to Find Prime Numbers
  8. Greatest Common Divisor (GCD) of Two Numbers Java Program
  9. Least Common Multiple (LCM) of Two Numbers - Java Program
  10. Factorial Program in Java
  11. Fibonacci Series Program in Java
  12. Arrange Non-Negative Integers to Form Largest Number - Java Program
  13. How to Display Pyramid Patterns in Java - Part1
  14. How to Display Pyramid Patterns in Java - Part2
  15. Convert int to String in Java
  16. Convert float to String in Java
  17. Convert double to String in Java
  18. Convert float to int in Java
  19. Convert double to int in Java
  20. Convert Numbers to Words Java Program

Java - Array

  1. Find Duplicate Elements in an Array Java Program
  2. Remove Duplicate Elements From an Array in Java
  3. How to Remove Elements From an Array Java Program
  4. How to How to Find Common Elements Between Two Arrays Java Program
  5. Find Largest and Second Largest Number in Given Array Java Program
  6. Find Largest And Smallest Number in a Given Array Java Program
  7. Array Rotation Java Program
  8. Matrix Multiplication Java Program
  9. Matrix Addition Java Program
  10. Matrix Subtraction Java Program
  11. Find Maximum And Minimum Numbers in a Given Matrix Java Program
  12. Find The Maximum Element in Each Row of a Matrix Java Program
  13. Two Sum - Array Indices With Given Sum Java Program
  14. Two Sum - Elements in Array With Given Sum Java Program

Java Date&Time

  1. Format Date in Java Using SimpleDateFormat
  2. How to Convert Date to String in Java
  3. How to Convert String to Date in Java
  4. How to Convert Date And Time Between Different Time-Zones in Java
  5. How to Display Time in AM-PM Format in Java
  6. Display Time in 24 Hours Format in Java
  7. Difference Between Two Dates in Java
  8. Compare Dates in Java
  9. Create Date Object in Java With Date and Time Values
  10. Java Program to Get Current Date and Time

Java - Collections

  1. How to Iterate a HashMap of ArrayLists of String in Java
  2. How to Sort Elements in Different Order in Java TreeSet

Lambda Expression

  1. Java Lambda Expression Runnable Example
  2. Java Lambda Expression Comparator Example
  3. Java Lambda Expression Callable Example

Java Internals

  1. How to Compile Java Program at Runtime
  2. How to Run javap Programmatically From Java Program
  3. Running Dos/Windows Commands From Java Program
  4. How to Run a Shell Script From Java Program

Data Structures in Java

  1. Linked List Implementation Java Program
  2. Stack Implementation in Java Using Array
  3. Stack Implementation in Java Using Linked List
  4. Queue Implementation in Java Using Array
  5. Queue Implementation in Java Using Linked List
  6. Java Program to Detect And Remove Loop in a Linked List
  7. How to Reverse a Linked List in Java
  8. Sorted Linked List In Java
  9. Doubly Linked List Implementation Java Program
  10. Deque Implementation in Java Using Doubly Linked List
  11. How to Reverse a Doubly Linked List in Java
  12. Binary Tree Implementation in Java - Insertion, Traversal And Search
  13. Java Program to Delete a Node From Binary Search Tree (BST)
  14. Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program
  15. Binary Tree Traversal Using Breadth First Search Java Program
  16. Binary Tree Traversal Using Depth First Search Java Program
  17. Graph Adjacency Representation - Java Program
  18. Weighted Graph Adjacency Representation - Java Program

Java I/O

  1. Reading File in Java Using BufferedReader
  2. Reading File in Java Using Scanner
  3. Reading Delimited File in Java Using Scanner
  4. Reading File in Java Using Files.lines And Files.newBufferedReader
  5. How to Read File From The Last Line in Java
  6. How to Read Properties File in Java
  7. How to Read Input From Console in Java
  8. Read File Asynchronously Java Program
  9. Write to a File in Java
  10. Writing a File Asynchronously Java Program
  11. How to Append to a File in Java
  12. Read or List All Files in a Folder in Java
  13. Java Program to Delete File And Directory Recursively
  14. How to Find Last Modified Date of a File in Java
  15. How to Count Lines in a File in Java
  16. Java Program to Print Line Numbers With Lines in Java
  17. Java Program to Convert a File to Byte Array
  18. How to Read Excel File in Java Using Apache POI
  19. How to Write Excel File in Java Using Apache POI
  20. Creating Temporary File in Java

Compressing & Decompressing Files

  1. Zipping Files And Folders in Java
  2. Unzip File in Java
  3. How to Create Password Protected Zip File in Java
  4. Compress And Decompress File Using GZIP Format in Java
  5. Creating Tar File And GZipping Multiple Files in Java
  6. How to Untar a File in Java

Java Multi-Threading

  1. Print Odd-Even Numbers Using Threads And wait-notify Java Program
  2. Print Odd-Even Numbers Using Threads And Semaphore Java Program
  3. Producer-Consumer Java Program Using wait notify
  4. Producer-Consumer Java Program Using ArrayBlockingQueue
  5. Producer-Consumer Java Program Using volatile
  6. How to Run Threads in Sequence in Java
  7. Printing Numbers in Sequence Using Threads Java Program
  8. How to Create Deadlock in Java
  9. Setting And Getting Thread Name And Thread ID in Java
  10. Java Program to Create Your Own BlockingQueue

Java XML

  1. How to Create PDF From XML Using Apache FOP

PDF Generation in Java

  1. Creating PDF in Java Using iText
  2. How to Create PDF in Java Using OpenPDF
  3. Creating PDF in Java Using Apache PDFBox
  4. HTML to PDF in Java + Flying Saucer and OpenPDF
  5. Convert HTML to PDF in Java + Openhtmltopdf and PDFBox

Enum

  1. Comparing Enum to String in Java
  2. Converting String to Enum Type in Java
  3. Converting Enum to String in Java

Java Reflection

  1. Generating Getters And Setters Using Reflection in Java
  2. Invoking Getters And Setters Using Reflection in Java

JDBC Programs

  1. Connection Pooling Using Apache DBCP in Java
  2. Connection Pooling Using C3P0 in Java
  3. Java Program to Get All DB Schemas
  4. Java Program to Get All The Tables in a DB Schema

Sorting Algorithms in Java

  1. What is In-place Algorithm
  2. Bubble Sort Program in Java
  3. Selection Sort Program in Java
  4. Insertion Sort Program in Java
  5. Shell Sort Program in Java
  6. Merge Sort Program in Java
  7. Quick Sort Program in Java
  8. Heap Sort Program in Java
  9. Tree Sort in Java Using Binary Search Tree
  10. Counting Sort Program in Java
  11. Bucket Sort Program in Java
  12. Radix Sort Program in Java

Searching Algorithms in Java

  1. Linear Search (Sequential Search) Java Program
  2. Binary Search Program in Java
  3. Ternary Search Program in Java
  4. Interpolation Search Program in Java
  5. Exponential Search Program in Java

Java Program - Sieve of Eratosthenes to Find Prime Numbers

In this post we'll see how to write a program in Java to find prime numbers up to the given limit using Sieve of Eratosthenes algorithm.

Sieve of Eratosthenes algorithm

Sieve of Eratosthenes algorithm work by creating an array of n+1 size if the prime numbers are to be listed for range 1..n.

For each prime number mark all its multiple as non-prime in the table. That's what make this algorithm efficient, for example if 2 is a prime number then none of its multiple 4, 6, 8… is going to be a prime number. Same way if 3 is a prime number then none of its multiple 6, 9, 12, 15.. is going to be a prime number.

After the marking is done, which ever numbers are still unmarked are prime numbers.

For example, if we have to find prime numbers in the range 1-10 then we can visualize it as given here-

Sieve of Eratosthenes

For 2, mark all the multiples of 2 as not prime-

Java Program - Sieve of Eratosthenes

For 3, mark all the multiples of 3 as not prime-

Same way for next numbers 5 and 7. At the end you will be left with the numbers that are prime. Note, that 1 is also not considered as a prime number that will be taken care of in the program by starting the loop from 2.

Sieve of Eratosthenes Java program

import java.util.Arrays;
import java.util.Scanner;

public class EratosthenesSieve {
  private static void getPrimes(int n) {
    // table to keep track of prime or not
    boolean[] primeTable = new boolean[n+1];
    // intially mark all of the array element as true
    Arrays.fill(primeTable, true);
    for(int i = 2; i <= n; i++) {
      // still true means it is a prime number
      if(primeTable[i]) {
        // multiples of i should be marked as not prime
        for(int j = i * i; j <= n; j = j+i) {
          primeTable[j] = false;
        }
      }
    }
    // print all the prime numbers which'll be the 
    // the elements in the array still marked as true
    // printing can also be done in the above for loop itself
    // after the if condition block
    for(int i = 2; i <= n; i++) {
      if(primeTable[i]) {
        System.out.print(i + " ");
      }
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the number for range: ");
    int n = sc.nextInt();
    getPrimes(n);
    sc.close();
  }

}

Output

Enter the number for range: 
50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 

Time and space complexity of Sieve of Eratosthenes algorithm

Outer loop runs n times.

Inner loop runs n/i times for i = 2, 3, 5…. when i = 2, the internal loop will be executed n/2 times. For i = 3, it'll be executed n/3 times. For i = 5, it'll be executed n/5 times, and so on. This results in the time complexity of O(log(log n))

Thus, the overall time complexity is O(n X log(log n))

We need an array of length n+1 for marking the non-primes so the space complexity is O(n).

That's all for this topic Java Program - Sieve of Eratosthenes to Find Prime Numbers. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page


Related Topics

  1. Java Program to Check Prime Number
  2. Greatest Common Divisor (GCD) of Two Numbers Java Program
  3. Least Common Multiple (LCM) of Two Numbers - Java Program
  4. Convert float to String in Java

You may also like-

  1. Weighted Graph Adjacency Representation - Java Program
  2. Find Maximum And Minimum Numbers in a Given Matrix Java Program
  3. Two Sum - Elements in Array With Given Sum Java Program
  4. Manacher's Algorithm to Find The Longest Palindrome - Java Program
  5. Optional Class in Java With Examples
  6. finally Block in Java Exception Handling
  7. Spring Transaction Management Example - @Transactional Annotation and JDBC
  8. Angular HttpClient - Set Response Type as Text

Weighted Graph Adjacency Representation - Java Program

In the article Graph Adjacency Representation - Java Program, we saw how to represent an unweighted graph using adjacency list or adjacency matrix. In this post we'll see what is a weighted graph and how to represent a weighted graph using adjacency list or adjacency matrix in Java.

Weighted graph

In a weighted graph, numerical values called weights are assigned to edges. These weights may represent distance, cost, time etc. For example, if vertices in a graph represent cities, then weight of the edges may mean the distances between the cities, cost t travel between cities or time it takes to drive between cities.

Weighted Graph

Weighted graph representation using adjacency matrix

An adjacency matrix is a 2-D array in which weight of the edge is used as elements to indicate whether an edge is present between two vertices or not. For example, adjMat[i][j] stores the weight of the edge between i and j vertices.

If the edge is not present it is represented by value as infinity or zero for that cell in the matrix.

For the above image which represents an undirected weighted graph the adjacency matrix can be visualized as shown below. An undirected graph means that the edges don't have direction and you can traverse both ways. You can go from vertex A to vertex B or from vertex B to vertex A.

Weighted Undirected Graph Adjacency Matrix

Weighted Undirected Graph adjacency matrix Java Program

public class WtGraphAdjMatrix {
  private int vertices;
  private int[][] adjMatrix;

  WtGraphAdjMatrix(int vertices){
    this.vertices = vertices;
    adjMatrix = new int[vertices][vertices];
  }
  
  public void addEdge(int source, int destination, int weight) {
    if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
      System.out.println("Invalid edge addition");
      return;
    }
    adjMatrix[source][destination] = weight;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = weight;
  }
  
  public void printGraph() {
    for(int i = 0; i < adjMatrix.length; i++) {
      for(int j = 0; j < adjMatrix[0].length; j++) {
        System.out.print(adjMatrix[i][j] + "\t");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    WtGraphAdjMatrix graph = new WtGraphAdjMatrix(5);
    graph.addEdge(0, 1, 5); //A-B
    graph.addEdge(0, 2, 10); //A-C
    graph.addEdge(0, 4, 7); //A-E
    graph.addEdge(2, 3, 15); //C-D
    graph.addEdge(3, 4, 8); //D-E


    graph.printGraph();
  }
}

Output

0   5	  10	0	  7	
5	  0	  0	  0	  0	
10  0	  0	  15  0	
0	  0	  15	0	  8	
7	  0	  0	  8	  0

Weighted Directed Graph adjacency matrix Java Program

In a directed graph you can traverse in only one direction. The allowed direction is shown with an arrow at the end of the edge.

Weighted Directed Graph

Adjacency matrix for the above weighted directed graph can be visualized as-

Weighted Directed Graph Adjacency Matrix

Java code for the directed Graph adjacency matrix requires just commenting a single line in the above code for the undirected graph, the reverse link in the matrix.

public void addEdge(int source, int destination, int weight) {
  if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
    System.out.println("Invalid edge addition");
    return;
  }
  adjMatrix[source][destination] = weight;
  // For undirected graph reverse setting also required
  //adjMatrix[destination][source] = weight;
}

If you run the code after commenting the line, output is-

0   5	  10	0	  7	
0	  0	  0	  0	  0	
0	  0	  0	  15	0	
0	  0	  0	  0	  8	
0	  0	  0	  0	  0

Weighted Graph representation using adjacency list

Another way to represent a weighted graph is using an adjacency list which is an array of lists or a list of lists. Each vertex has an associated list storing all the adjacent vertices. In this associated list each element will have two values connected vertex and the weight between two vertices.

Adjacency list for the above weighted undirected graph can be visualized as-

Weighted Undirected Graph adjacency list Java Program

In the Java program Map and List collections are used to represent adjacency list. Each map key has an associated list to show the adjacent vertices. There is also a class named Edge that encapsulates the adjacent vertex and weight fields.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WtGraphAdjList {
  int vertices;
  Map<String, List<Edge>> adjList;
  static class Edge{
    String destination;
    int weight;
    Edge(String destination, int weight){
      this.destination = destination;
      this.weight = weight;
    }
  }
  
  WtGraphAdjList(int vertices){
    this.vertices = vertices;
    adjList = new HashMap<>();
  }
  void addEdge(String source, String destination, int weight) {

    adjList.computeIfAbsent(source, k->new ArrayList<>()).add(new Edge(destination, weight));
    // For undirected graph
    adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(new Edge(source, weight));
  }
  
  public void printGraph() {
    for(Map.Entry<String, List<Edge>> es : adjList.entrySet()) {
      System.out.print("Vertex " + es.getKey() + " connects to: ");
      List<Edge> list = es.getValue();
      for (Edge e : list) {
        System.out.print("[" + e.destination + " with weight " + e.weight + "] ");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    WtGraphAdjList graph = new WtGraphAdjList(5);
    graph.addEdge("A", "B", 5);
    graph.addEdge("A", "C", 10);
    graph.addEdge("A", "E", 7);
    graph.addEdge("C", "D", 15);
    graph.addEdge("D", "E", 8);
    
    graph.printGraph();
  }
}

Output

Vertex A connects to: [B with weight 5] [C with weight 10] [E with weight 7] 
Vertex B connects to: [A with weight 5] 
Vertex C connects to: [A with weight 10] [D with weight 15] 
Vertex D connects to: [C with weight 15] [E with weight 8] 
Vertex E connects to: [A with weight 7] [D with weight 8] 

Weighted Directed Graph adjacency list Java Program

In case of directed graph, you can traverse in only one direction.

Java code for the directed Graph adjacency matrix requires just commenting the line that creates a reverse link in the list.

void addEdge(String source, String destination, int weight) {
  adjList.computeIfAbsent(source, k->new ArrayList<>()).add(new Edge(destination, weight));
  // For undirected graph
  //adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(new Edge(source, weight));
}

With that change the output is-

Vertex A connects to: [B with weight 5] [C with weight 10] [E with weight 7] 
Vertex C connects to: [D with weight 15] 
Vertex D connects to: [E with weight 8] 

That's all for this topic Weighted Graph Adjacency Representation - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page


Related Topics

  1. Java Program to Detect And Remove Loop in a Linked List
  2. Binary Tree Traversal Using Depth First Search Java Program

You may also like-

  1. Deque Implementation in Java Using Doubly Linked List
  2. Arrange Non-Negative Integers to Form Largest Number - Java Program
  3. Radix Sort Program in Java
  4. Display Time in 24 Hours Format in Java
  5. Java Stream - sorted() With Examples
  6. Difference Between Abstract Class And Interface in Java
  7. Lazy Initialization in Spring Using lazy-init And @Lazy Annotation
  8. Angular Two-Way Data Binding With Examples

Friday, October 10, 2025

Graph Adjacency Representation - Java Program

In this post we'll see how to represent a graph using adjacency list and adjacency matrix. Here we'll see representation for the unweighted graph.

Graph is a data structure which is similar to tree and has nodes and edges. Nodes are generally called vertices when it comes to graph.

If you want to see how to represent a weighted graph using adjacency list and adjacency matrix, check this post- Weighted Graph Adjacency Representation - Java Program

What is adjacency

The vertices in a graph are said to be adjacent to one another if they are connected directly by a single edge.

Undirected Graph

The above graph has 5 vertices (A, B, C, D, E) and 5 edges. The circles represent the vertices and the lines connecting them are edges. In the above figure vertex A is adjacent to B and C but A is not adjacent to vertex D.

A binary tree has a fixed structure; each node has a maximum of two children. Graph doesn't have that kind of fixed structure, in a graph each vertex may be connected to an arbitrary number of other vertices. In the above vertex A is connected to B, C and E vertices.

Because of this kind of structure, to represent a graph two methods are generally used-

  1. Adjacency matrix
  2. Adjacency List

Graph representation using adjacency matrix

An adjacency matrix is a 2-D array in which 0 and 1 are used as elements to indicate whether an edge is present between two vertices or not.

  • An edge between two vertices is marked using 1
  • If there is no edge between two vertices then 0 is used

If a graph has n vertices, then adjacency matrix also has n rows and n columns (n X n array).

For the above image which represents an undirected graph the adjacency matrix can be visualized as shown below. An undirected graph means that the edges don't have direction and you can traverse both ways. You can go from vertex A to vertex B or from vertex B to vertex A.

Undirected Graph Adjacency Matrix

Adjacency matrix representation is easy to implement and efficient in terms of accessing any element, but it is less space efficient because you are storing information about all possible edges rather than just actual connections (adjacency list stores only actual connections).

Undirected Graph adjacency matrix Java Program

public class GraphAdjMatrix {
  private int vertices;
  private int[][] adjMatrix;

  GraphAdjMatrix(int vertices){
    this.vertices = vertices;
    // matrix having same row and columns as vertices
    adjMatrix = new int[vertices][vertices];
  }
  
  public void addEdge(int source, int destination) {
    if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
      System.out.println("Invalid edge addition");
      return;
    }
    adjMatrix[source][destination] = 1;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = 1;
  }
  
  public void printGraph() {
    for(int i = 0; i < adjMatrix.length; i++) {
      for(int j = 0; j < adjMatrix[0].length; j++) {
        System.out.print(adjMatrix[i][j] + "\t");
      }
      System.out.println();
    }
  }
  
  public static void main(String[] args) {
    GraphAdjMatrix graph = new GraphAdjMatrix(5);
    graph.addEdge(0, 1); //A-B
    graph.addEdge(0, 2); //A-C
    graph.addEdge(0, 4); //A-E
    graph.addEdge(2, 3); //C-D
    graph.addEdge(3, 4); //D-E

    graph.printGraph();

  }
}

Output

0	1	1	0	1	
1	0	0	0	0	
1	0	0	1	0	
0	0	1	0	1	
1	0	0	1	0

Directed Graph adjacency matrix Java Program

In a directed graph you can traverse in only one direction. The allowed direction is shown with an arrow at the end of the edge.

Directed Graph

Adjacency matrix for the above directed graph can be visualized as-

Directed Graph Adjacency Matrix

Java code for the directed Graph adjacency matrix requires just commenting a single line in the above code for the undirected graph, the reverse link in the matrix.

public void addEdge(int source, int destination) {
  if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
    System.out.println("Invalid edge addition");
    return;
  }
  adjMatrix[source][destination] = 1;
  // For undirected graph reverse setting also required
  //adjMatrix[destination][source] = 1;
}

With that the output is-

0	1	1	0	1	
0	0	0	0	0	
0	0	0	1	0	
0	0	0	0	1	
0	0	0	0	0

Graph representation using adjacency list

Another way to represent a graph is using an adjacency list which is an array of lists or a list of lists. Each vertex in a list shows all the adjacent vertices as another list, linked to this vertex.

Adjacency list for the above undirected graph can be visualized as-

Undirected Graph Adjacency List

Undirected Graph adjacency list Java Program

In the Java program Map and List collections are used to represent adjacency list. Each map key has an associated list to show the adjacent vertices.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class GraphAdjList {
  int vertices;
  Map<String, List<String>> adjList;
  
  GraphAdjList(int vertices){
    this.vertices = vertices;
    adjList = new HashMap<>();

  }
  
  public void addEdge(String source, String destination) {
    adjList.computeIfAbsent(source, k->new ArrayList<>()).add(destination);
    // For undirected graph
    adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(source);
  }
  
  public void printGraph() {
    for(Map.Entry<String, List<String>> es :adjList.entrySet()) {
      System.out.print("Vertex " + es.getKey() + " connects to: ");
      List<String> list = es.getValue();
      for (String s : list) {
        System.out.print("[" + s + "] ");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    GraphAdjList graph = new GraphAdjList(5);
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("A", "E");
    graph.addEdge("C", "D");
    graph.addEdge("D", "E");
    
    graph.printGraph();
  }
}

Output

Vertex A connects to: [B] [C] [E] 
Vertex B connects to: [A] 
Vertex C connects to: [A] [D] 
Vertex D connects to: [C] [E] 
Vertex E connects to: [A] [D] 

As you can see with adjacency list you store only the actual connections so it is more space efficient.

Directed Graph adjacency list Java Program

In case of directed graph, you can traverse in only one direction.

Adjacency list for the above directed graph can be visualized as-

Directed Graph Adjacency List

Java code for the directed Graph adjacency matrix requires just commenting the line that creates a reverse link in the list.

public void addEdge(String source, String destination) {
  adjList.computeIfAbsent(source, k->new ArrayList<>()).add(destination);
  // For undirected graph
  //adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(source);
}

With that change the output is-

Vertex A connects to: [B] [C] [E] 
Vertex C connects to: [D] 
Vertex D connects to: [E] 

That's all for this topic Graph Adjacency Representation - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Longest Prefix Suffix Java Program
  2. Z Algorithm For Pattern Search - Java Program
  3. How to Iterate a HashMap of ArrayLists of String in Java
  4. How to Sort Elements in Different Order in Java TreeSet
  5. Binary Tree Implementation in Java - Insertion, Traversal And Search

You may also like-

  1. Heap Sort Program in Java
  2. Interpolation Search Program in Java
  3. Matrix Multiplication Java Program
  4. Doubly Linked List Implementation Java Program
  5. Service in Angular With Examples
  6. How to Resolve Local Variable Defined in an Enclosing Scope Must be Final or Effectively Final Error
  7. static Method Overloading or Overriding in Java
  8. List in Python With Examples