Weighted Graph Java Program

In this post we'll see how to write a Java program to create a weighted graph.

What is a weighted graph

A weighted graph is a graph structure where numerical values called weights are assigned to edges. These weights may represent distance, cost, time etc.

Weighted graph may be directed (traversed one way only from source to destination) or undirected.

Weighted graph Java program

A weighted graph in Java can be implemented using either an adjacency matrix or an adjacency list.

If it is a sparse graph, meaning it has relatively few edges compared to the number of vertices, then adjacency list is preferred because it will take less space. It takes less memory because adjacency list only stores actual connections unlike adjacency matrices that allocate space for all possible edges.

If we take the below graph as example-

Then adjacency list can be visualized as-

And adjacency matrix can be visualized as-

Note that in both visualisations, graph is represented as undirected graph.

Weighted graph Java implementation using adjacency list

import java.util.ArrayList;
import java.util.List;

public class Graph {
  int vertices;
  List<List<Edge>> adjList;
  static class Edge{
    int destination;
    int weight;
    Edge(int destination, int weight){
      this.destination = destination;
      this.weight = weight;
    }
  }

  Graph(int vertices){
    this.vertices = vertices;
    adjList = new ArrayList<>();
    for(int i = 0; i < vertices; i++) {
      adjList.add(new ArrayList<>());
    }
  }

  public void addEdge(int source, int destination, int weight) {
    adjList.get(source).add(new Edge(destination, weight));
    // For undirected graph need both sides
    adjList.get(destination).add(new Edge(source, weight));
  }

  public void printGraph() {
    for(int i = 0; i < vertices; i++) {
      System.out.print("Vertex " + i + " connects to: ");
      for (Edge e : adjList.get(i)) {
        System.out.print("[" + e.destination + " with weight " + e.weight + "] ");
      }
      System.out.println();

    }
  }

  public static void main(String[] args) {
    Graph graph = new Graph(5);
    graph.addEdge(0, 1, 10);
    graph.addEdge(0, 4, 5);
    graph.addEdge(1, 2, 30);
    graph.addEdge(1, 3, 40);
    graph.addEdge(3, 4, 50);

    graph.printGraph();
  }
}

Output

Vertex 0 connects to: [1 with weight 10] [4 with weight 5] 
Vertex 1 connects to: [0 with weight 10] [2 with weight 30] [3 with weight 40] 
Vertex 2 connects to: [1 with weight 30] 
Vertex 3 connects to: [1 with weight 40] [4 with weight 50] 
Vertex 4 connects to: [0 with weight 5] [3 with weight 50] 

As you can see here adjacency list is declared as an ArrayList of ArrayList, which should be clear from the visual representation of the adjacency list shown above. There is a static inner class Edge with fields as destination and weight.

Weighted graph Java implementation using adjacency matrix

public class GraphMatrix {
  private int vertices;
  private int[][] adjMatrix;
  GraphMatrix(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) {
    GraphMatrix graph = new GraphMatrix(5);
    graph.addEdge(0, 1, 10);
    graph.addEdge(0, 4, 5);
    graph.addEdge(1, 2, 30);
    graph.addEdge(1, 3, 40);
    graph.addEdge(3, 4, 50);

    graph.printGraph();

  }
}

Output

0	10	0	0	5	
10	0	30	40	0	
0	30	0	0	0	
0	40	0	0	50	
5	0	0	50	0

That's all for the topic Weighted Graph Java Program. If something is missing or you have something to share about the topic please write a comment.

---

You may also like

• AVL Tree Java Program - Insertion, Traversal, Search
• Heap Sort Java Program
• Stable and Unstable Sorting Algorithms
• Java Primitive Data Types
• Java Reflection – Class Constructors
• Spring IoC Container Types – ApplicationContext and BeanFactory
• Distributed Cache in Hadoop
• What is Big Data

AVL Tree Java Program - Insertion, Traversal, Search

In this post we'll see how to write a AVL tree Java program. Operations covered in this post are-

• Inserting a node in AVL tree
• Searching a node in AVL tree
• AVL tree traversal

AVL Binary Tree

An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the left subtree and right subtree of any node differ by at most one. If any time that height difference goes beyond one, rebalancing is done so that height difference is not more than one.

Because of this self-balancing property, AVL tree will not get skewed like Binary Search Tree. AVL tree height is kept to a minimum so that searching, inserting and deleting nodes have time complexity of O(log n). It will never be O(n) which may be the time complexity of BST under certain scenarios.

For example, suppose you are inserting {10, 20, 30, 40} in a BST then the BST is skewed towards right.

Which means searching for 40 becomes an O(n) operation.

Same nodes with AVL tree.

As you can see, because of self-balancing, AVL tries to keep the height as minimum, in the above AVL tree you can see that the difference between left subtree height and right subtree height is 1 from root node.

How does self-balancing work

In an AVL tree, the heights of the left subtree and right subtree of any node differ by at most one. Whenever insertion and deletion operations are performed on the tree, balance factor is calculated for the nodes to check if height difference is going beyond the permissible limit for any node. If yes, then rebalancing is done.

The height of a subtree is the number of edges between the root node of that subtree and the leaf node farthest down in that subtree.

Equation for Balance factor for any node n can be given as-

Balance Factor(n) = height of left subtree(n) - height of right subtree(n)

For a tree to be considered balanced, for every node balance factor should be in the range

-1 <= balance factor <= 1

Which can be explained as-

• BF = 0 means binary tree is perfectly balanced at that node
• BF = +1 means left-heavy at that node but permissible
• BF = -1 means right-heavy at that node but permissible
• BF < -1 or BF > +1 means binary tree is imbalanced and rotation is required to balance it.

Since height is constantly calculated while constructing AVL tree, in order to save time height for each node is stored with the node.

class Node{
  int data;
  int height;
  Node left;
  Node right;
  Node(int data){
    this.data = data;
    this.height = 1;
  }
  public void displayData(){
    System.out.print(data + " ");
  }
}

Rotation cases

Following are the scenarios for the AVL tree to become imbalance and each of these scenarios requires different rotation operation.

1. Left-Left scenario- When balance factor of Node n is more than 1 and its left child node is also left heavy that is LL scenario. In that case a right rotation is needed to make it balanced. For example, consider the following tree. Here node 30 has BF of 2 (left height is 2 and right height is 0).
   
   So, it has to be right rotated around that node (node with data as 30) so that its left child becomes the parent node and any right child of that left child becomes the left child of that node.
   
   If the node around which right rotation is done is called node and we have to write that same thing in programming logic, it'll be as given below.

   Node temp1 = node.left;
   Node temp2 = temp1.right;
   // from where rotation started (origin node) should become right child
   temp1.right = node;
   // Right child of the left child of origin node should become left child
   // of origin node
   node.left = temp2;
   

2. Right-Right scenario- When balance factor of Node n is less than -1 and its right child node is also right heavy that is RR scenario. In that case a left rotation is needed to make it balanced. For example, consider the following tree. Here node 10 has BF of -2 (left height is 0 and right height is 2).
   
   So, it has to be left rotated around that node (node with data as 10) so that its right child becomes the parent node and any left child of that right child becomes the right child of that original root node.
   
   If the node around which left rotation is done is called node and we have to write that same thing in programming logic, it'll be as given below.

   Node temp1 = node.right;
   Node temp2 = temp1.left;
   // from where rotation started (origin node) should become left child
   temp1.left = node;
   // left child of the right child of origin node should become right child
   // of origin node
   node.right = temp2;
   

3. Left-Right Scenario- This scenario occurs when parent node is imbalanced as its balance factor is more than +1 (left side imbalance) but it's left child is right heavy. This results in a zig-zag kind of structure which can't be balanced just by right rotation. For example, consider the following tree.
   
   Right rotation around 30 will make it a wrong structure as 10 as root node and 20 as its left child violates the BST structure (20 is greater than 10 so it should be on right side).
   What you need is left rotation around 10 making 20 the parent of 10.
   
   That makes it a LL scenario needing a right rotation around 30 to finally balance it.
   
4. Right-Left Scenario- This scenario occurs when parent node is imbalanced as its balance factor is less than -1 (right side imbalance) but its right child is left heavy. This results in a zig-zag kind of structure which can't be balanced just by left rotation. For example, consider the following tree.
   
   Single left rotation around 10 won't make it right. What you need is right rotation around 30 making 20 the parent of 30.
   
   That makes it a RR scenario needing a left rotation around 10 to finally balance it.
   

AVL Tree Traversal

When you traverse an AVL tree you visit each node in a specified order. Orderings which are used for traversal are-

• Inorder traversal
• Preorder traversal
• Postorder traversal

Note that traversals of AVL trees are same as binary search trees.

AVL tree Inorder traversal in Java

Logic for Inorder traversal of AVL tree is as follows-

Recursively traverse the left subtree
Visit the root node
Recursively traverse the right subtree

// For traversing in order
public void inOrder(Node node){
  if(node != null){
    inOrder(node.left);
    node.displayData();
    inOrder(node.right);
  }
}

AVL tree Preoder traversal in Java

Logic for preorder traversal of AVL tree is as follows-

Visit the root node
Recursively traverse the left subtree.
Recursively traverse the right subtree

// Preorder traversal
public void preOrder(Node node){
  if(node != null){
    node.displayData();
    preOrder(node.left);           
    preOrder(node.right);
  }
}

AVL tree Postoder traversal in Java

Logic for postoder traversal of AVL tree is as follows-

Recursively traverse the left subtree.
Recursively traverse the right subtree
Visit the root node

// Postorder traversal
public void postOrder(Node node){
  if(node != null){
    postOrder(node.left);
    postOrder(node.right);
    node.displayData();          
  }
}

public class AVLTree {
  // first node
  Node root;
  AVLTree(){
    root = null;
  }
  // Class for defining each node in the tree
  static class Node{
    int data;
    int height;
    Node left;
    Node right;
    Node(int data){
      this.data = data;
      // New node has height 1 because it has no children
      // height of any node is calculated as
      //height = 1 + max(height of left child, height of right child)
      this.height = 1;
    }
    public void displayData(){
      System.out.print(data + " ");
    }
  }
  
  public void insert(int data){
    root = insert(root, data);
     
  }
  
  public Node insert(Node node, int data) {
    if(node == null) {
      return new Node(data);
    }
    if(data < node.data) {
      node.left = insert(node.left, data);
    }else if(data > node.data) {
      node.right = insert(node.right, data);
    }else {
      return node;
    }
    
    //update height of each node traversed
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    int balance = getBalance(node);
    
    // left left
    if(balance > 1 && data < node.left.data)
      return rightRotate(node);
      
    //right right
    if(balance < -1 && data > node.right.data)
      return leftRotate(node);
    //left right
    if(balance > 1 && data > node.left.data) {
      node.left = leftRotate(node.left);
      return rightRotate(node);
    }
    //right left
    if(balance < -1 && data < node.right.data) {
      node.right = rightRotate(node.right);
      return leftRotate(node);
    }
    return node;
  }
  
  // method to get height of node
  int getHeight(Node node) {
    return node == null ? 0 : node.height;
  }
  
  // method to get balance factor of node
  int getBalance(Node node) {
    return node == null ? 0 : (getHeight(node.left) - getHeight(node.right));
  }
  
  Node rightRotate(Node node) {
    System.out.println("Rotate right on node " + node.data);
    Node temp1 = node.left;
    Node temp2 = temp1.right;
    // from where rotation started (origin node) should become right child
    temp1.right = node;
    // Right child of the left child of origin node should become left child
    // of origin node
    node.left = temp2;

    // update heights
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    temp1.height = 1 + Math.max(getHeight(temp1.left), getHeight(temp1.right));
    return temp1;
     
  }
  
  Node leftRotate(Node node) {
    System.out.println("Rotate left on node " + node.data);
    Node temp1 = node.right;
    Node temp2 = temp1.left;
    // from where rotation started (origin node) should become left child
    temp1.left = node;
    // left child of the right child of origin node should become right child
    // of origin node
    node.right = temp2;

    // update heights
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    temp1.height = 1 + Math.max(getHeight(temp1.left), getHeight(temp1.right));
    return temp1;
     
  }
  
  // Search node in binary search tree
  public Node find(int searchedValue){
    Node current = root;
    while(current.data != searchedValue){
      if(searchedValue < current.data)
        // Move to the left if searched value is less
        current = current.left;
      else
        // Move to the right if searched value is >=
        current = current.right;
      if(current == null){
        return null;
      }
    }
    return current;
  }
  
  // For traversing in order
  public void inOrder(Node node){
    if(node != null){
      inOrder(node.left);
      node.displayData();
      inOrder(node.right);
    }
  }
  
  // Preorder traversal
  public void preOrder(Node node){
    if(node != null){
      node.displayData();
      preOrder(node.left);           
      preOrder(node.right);
    }
  }
    
  // Postorder traversal
  public void postOrder(Node node){
    if(node != null){
      postOrder(node.left);
      postOrder(node.right);
      node.displayData();          
    }
  }
    
  public static void main(String[] args) {
    AVLTree avlTree = new AVLTree();
    int[] data = {10, 15, 20, 30, 40, 25};

    for(int d : data) {
      avlTree.insert(d);
    }
    
    System.out.println("Inorder traversal of binary tree");
    avlTree.inOrder(avlTree.root);
    System.out.println();
    
    System.out.println("Post order traversal of binary tree");
    avlTree.postOrder(avlTree.root);
    System.out.println();
    
    System.out.println("Pre order traversal of binary tree");
    avlTree.preOrder(avlTree.root);
    System.out.println();
    
    Node node = avlTree.find(21);
    System.out.println((node == null)? "Node not found" : String.valueOf(node.data));      
  }
}

Output

Rotate left on node 10
Rotate left on node 20
Rotate right on node 30
Rotate left on node 15
Inorder traversal of binary tree
10 15 20 25 30 40 
Post order traversal of binary tree
10 15 25 40 30 20 
Pre order traversal of binary tree
20 15 10 30 25 40 
Node not found

Constructed AVL tree would look something like this-

That's all for the topic AVL Tree Java Program - Insertion, Traversal, Search. If something is missing or you have something to share about the topic please write a comment.

---

You may also like

• Generic Bubble Sort Java Program
• Heap Sort Java Program
• Stable and Unstable Sorting Algorithms
• Java Primitive Data Types
• Java Reflection – Class Constructors
• Spring IoC Container Types – ApplicationContext and BeanFactory
• Distributed Cache in Hadoop
• What is Big Data