Adjacency List Implementation in C++.

In the previous posts, we covered the basics of graph data structure and how we use an adjacency matrix for its representation. Here we are going to learn how to represent graph data structure using Adjacency List.

Adjacency List.

An adjacency list is a way of representing a graph as an array of linked lists, where each vertex has a linked list of its adjacent vertices. In this representation, we create an array of sizes V (V is the number of vertices). Each index of the array will carry a different list which will contain the list of vertices connected to that particular index.

Adjacency List for an Undirected Graph.

In an undirected graph, each edge is bidirectional, meaning that if there's an edge from vertex u to vertex v, there's also an edge from v to u. Therefore, in the adjacency list representation of an undirected graph, we add both u to the adjacency list of v and v to the adjacency list of u.

Example: 

Adjacency List for Undirected Graph

C++ code Implementation of Adjacency List for the above-undirected graph:

//C++ Code for Printing Adjacency List of Undirected Graph
#include <iostream>
#include <vector>
using namespace std;

//Add edges to undirected graph
void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

//printing the adjacency list
void printGraph(vector<int> adj[], int V) {
    for (int v = 0; v < V; ++v) {
        cout << "Adjacency list of vertex " << v << "->";
        for (auto u : adj[v])
            cout << u << " ";
        cout << endl;
    }
}

int main() {
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 2, 3);
    printGraph(adj, V);
    return 0;
}

Output:

Adjacency list of vertex 0->1 2
Adjacency list of vertex 1->0 2 3
Adjacency list of vertex 2->0 1 3
Adjacency list of vertex 3->1 2

Adjacency List for a Directed Graph.

In a directed graph, each edge is unidirectional, meaning that there's an edge from vertex u to vertex v, but not necessarily from v to u. Therefore, in the adjacency list representation of a directed graph, we only add v to the adjacency list of u.

Example:

Adjacency List for Directed Graph

C++ code Implementation of Adjacency List for the above-directed graph:

//C++ Code for Printing Adjacency List of Directed Graph
#include <iostream>
#include <vector>
using namespace std;

//Add edges to directed graph
void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
}

//printing the adjacency list
void printGraph(vector<int> adj[], int V) {
    for (int v = 0; v < V; ++v) {
        cout << "Adjacency list of vertex " << v << "->";
        for (auto u : adj[v])
            cout << u << " ";
        cout << endl;
    }
}

int main() {
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 1);
    printGraph(adj, V);
    return 0;
}

Output:

Adjacency list of vertex 0->1 2
Adjacency list of vertex 1->2
Adjacency list of vertex 2->3
Adjacency list of vertex 3->1

The Adjacency list is an efficient way to represent the graph when the graph is less dense but when the graph is dense we use the Adjacency matrix to represent a graph.

Adjacency Matrix Implementation in C++

We have covered Graph data structure in our previous post and in there, we have learned that graphs can be represented in two different ways, one is Adjacency Matrix and another is Adjacency List. In this post, we are going to learn about the Adjacency Matrix and its implementation for different types of graphs.

Adjacency Matrix.

An adjacency matrix is a way of representing a graph as a matrix of size n x n filled with 0s and 1s, where n is the number of vertices in the graph. The entry in the ith row and jth column of the matrix indicates whether there is an edge from vertex i to vertex j. 

Adjacency Matrix implementation is different for directed and undirected graphs. Let's learn the implementation one by one.

Adjacency Matrix for Undirected Graph.

For a simple undirected graph, the matrix is symmetric around its diagonal, since the edges are bidirectional. It means if there is an edge between vertex A to vertex B then there must be an edge from vertex B to vertex A. 

Note: The diagonal entries in the matrix are always 0 in an undirected graph since there are no self-loops. Also, the matrix is symmetric about its diagonal, so the entry in row i and column j is the same as the entry in row j and column i. (alert-passed)

Example:

Adjacency Matrix for Undirected Graph

Below is the C++ code implementation for the Adjacency matrix of an undirected graph.

//C++ code for printing adjacency matrix of undirected graph
#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int adj_matrix[MAX_SIZE][MAX_SIZE];

int main() {
    // n: number of vertices, m: number of edges
    int n, m;
    cout<<"Enter number of vertices: ";
    cin >> n;
    cout<<"Enter number of edges: ";
    cin >> m;
    
    // initialize adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            adj_matrix[i][j] = 0;
        }
    }
    
    cout<< "Add edges to the graph:\n";
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is undirected
        adj_matrix[u][v] = 1;
        adj_matrix[v][u] = 1;
    }
    
    // print adjacency matrix
    cout << "Adjacency matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

Enter number of vertices: 4
Enter number of edges: 5
Add edges to the graph:
0 1
0 2
1 2
1 3
2 3
Adjacency matrix:
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Adjacency Matrix for Directed Graph.

For a directed graph, the matrix is not necessarily symmetric, since the edges are not bidirectional. 

Example:

Adjacency Matrix for Directed Graph

Below is the C++ code implementation for the Adjacency matrix of a directed graph.

//C++ code for printing adjacency matrix of directed graph
#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int adj_matrix[MAX_SIZE][MAX_SIZE];

int main() {
    // n: number of vertices, m: number of edges
    int n, m;
    cout<<"Enter number of vertices: ";
    cin >> n;
    cout<<"Enter number of edges: ";
    cin >> m;
    
    // initialize adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            adj_matrix[i][j] = 0;
        }
    }
    
    cout<< "Add edges to the graph:\n";
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is directed
        adj_matrix[u][v] = 1;
    }
    
    // print adjacency matrix
    cout << "Adjacency matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

Enter number of vertices: 4
Enter number of edges: 5
Add edges to the graph:
0 1
0 2
1 2
2 3
3 1
Adjacency matrix:
0 1 1 0
0 0 1 0
0 0 0 1
0 1 0 0

Adjacency Matrix is a simple and efficient way to represent a dense graph but we have another method of representation like the Adjacency list when the graph is not dense. 

Difference Between Graph and Tree Data Structure.

Graph and Tree are completely two different data structures and we should handle both differently. Many times we do not know the basic difference between them and here in this post, we are going to discuss some of the important differences between graph and tree data structure.

Graph Data Structure.

A graph is a data structure that is used to represent a collection of interconnected objects, called vertices or nodes, and the connections between them, called edges.

Example:

Tree Data Structure.

A tree is a specific type of graph that is connected and acyclic with a hierarchical structure.

Example:

Difference Between Graph and Tree.

Tree Data Structure	Graph Data Structure
A tree is a special type of graph in which any two nodes are connected by exactly one path.	A graph, on the other hand, can have multiple paths between two nodes.
Trees have a rooted structure with a single node called the root, from which all other nodes are accessible by a unique path.	Graphs do not have a rooted structure.
Trees do not have any cycles.	Graphs can have cycles.
In a tree, every node can have at most one parent and multiple children.	In a graph, nodes can have multiple parents and children.
Trees are commonly used for hierarchical data structures such as file systems, family trees, and organization charts.	Graphs are used for modeling complex relationships and networks such as social networks, transportation systems, and computer networks.
We used In-order, Pre-order, or Post-order traversals to traverse the tree.	We used BFS (Breadth-First-Search) and DFS (Depth-First-Search) to traverse the graph.

Conclusion.

A tree is a specific type of graph with a hierarchical structure, no cycles, and a single root node. Graphs, on the other hand, are more general and can have cycles, multiple roots, and complex relationships between nodes.

Types of Graphs in Data Structure.

Graphs are non-linear data structures used to represent interconnected objects called vertices and nodes. A vertex represents a single entity in the graph, such as a person in a social network. An edge represents a connection between two vertices, such as a friendship between two people. We covered graph data structure in our previous post.

Here is the list of some common types of graphs:

1. Undirected Graph.

A graph in which edges have no direction associated with them is called an undirected graph. Example: A network of roads connecting various cities in a country.

2. Directed Graph.

A graph in which edges have a direction associated with them is called a directed graph or digraph. Example: A social network where people follow each other on Twitter.

3. Weighted Graph.

A graph in which edges have weights or costs associated with them is called a weighted graph. Example: A graph representing a road network where the weight of each edge could represent the distance between two cities.

4. Complete Graph.

A graph in which every pair of vertices is connected by an edge is called a complete graph. Example: A graph representing a round-robin tournament where every participant plays against another participant exactly once.

5. Cyclic Graph.

A graph in which all vertices are connected in a cycle is called a cyclic graph. Example: A graph representing a circular arrangement of objects.

6. Bipartite Graph.

A bipartite graph is a graph in which vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Example: We have Set X = {A, B, C} and Set Y = {1, 2, 3, 4} and in the graph, the vertices of Set X are only connected with vertices of Set Y and visa-versa.

7. Tree.

A connected acyclic graph is called a tree. Example: A family tree representing relationships between members of a family.

8. Planar Graph.

A graph that can be drawn on a plane without any edges crossing is called a planar graph. Example: A graph representing a geographical map of a city.

9. Sparse Graph.

A graph with few edges compared to the maximum number of edges possible is called a sparse graph. Example: A graph representing a social network where most people are only connected to a few others.

10. Dense Graph.

A graph with many edges compared to the maximum number of edges possible is called a dense graph. Example: A graph representing a road network where most cities are connected to several others.

Graph Data Structure in C++.

A graph is a data structure that is used to represent a collection of interconnected objects, called vertices or nodes, and the connections between them, called edges. 

• Vertex (or Node): A vertex represents a single entity in the graph, such as a person in a social network or a city in a transportation network.
• Edge: An edge represents a connection between two vertices, such as a friendship between two people or a road between two cities.

Let's understand graphs through an example, Social networks are a collection of individuals or entities, connected by various relationships or interactions, such as friendships, followings, and likes. 

A social network can be represented using a graph, where each individual or entity is represented as a node, and each relationship or interaction is represented as an edge.

Graph Important Terminology.

• Directed Graph: A directed graph is a graph in which each edge has a direction associated with it, indicating the flow or direction of the connection between the vertices.

• Undirected Graph: An undirected graph is a graph in which each edge does not have a direction associated with it, indicating that the connection between the vertices is bidirectional.

• Weighted Graph: A weighted graph is a graph in which each edge has a weight or cost associated with it, indicating the strength or importance of the connection between the vertices.

• Degree: The degree of a vertex is the number of edges connected to it. In a directed graph, the degree is further divided into in-degree and out-degree, which represent the number of incoming and outgoing edges, respectively.

• Path: A path in a graph is a sequence of vertices and edges that connects two vertices. The length of a path is the number of edges in the path.

• Cycle: A cycle is a path in a graph that starts and ends at the same vertex.

• Connected Graph: A connected graph is a graph in which there is a path between every pair of vertices.

• Spanning Tree: A spanning tree is a subset of the edges in a graph that connects all vertices without forming a cycle.

Graph Representation.

There are two common ways to represent a graph data structure: the adjacency list and the adjacency matrix.

Adjacency Matrix.

In the adjacency matrix representation, we use a two-dimensional array for size VxV to represent the edges between vertices. The value at matrix[i][j] represents the weight or existence of the edge between vertices i and j. 

C++ Code to Print the Adjacent Matrix of the above graph.

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int adj_matrix[MAX_SIZE][MAX_SIZE];

int main() {
    int n, m; // n: number of vertices, m: number of edges
    cin >> n >> m;
    
    // initialize adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            adj_matrix[i][j] = 0;
        }
    }
    
    // add edges to the graph
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is undirected
        adj_matrix[u][v] = 1;
        adj_matrix[v][u] = 1;
    }
    
    // print adjacency matrix
    cout << "Adjacency matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

5 6
0 1
0 2
0 4
1 4
1 2
2 3
Adjacency matrix:
0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 0
1 1 0 0 0

Adjacency List.

In the adjacency list representation, we store each vertex and its neighbors in a dictionary or hash map. The keys of the dictionary represent the vertices, and the values represent the neighboring vertices as a list or set. 

C++ Code to Print the Adjacent List of the above graph.

#include <iostream>
#include <vector>
using namespace std;

const int MAX_SIZE = 100;
vector<int> adj_list[MAX_SIZE];

int main() {
    int n, m; // n: number of vertices, m: number of edges
    cin >> n >> m;
    
    // add edges to the graph
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is undirected
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    
    // print adjacency list
    cout << "Adjacency list:\n";
    for (int i = 0; i < n; ++i) {
        cout << i << " -> ";
        for (int j = 0; j < adj_list[i].size(); ++j) {
            cout << adj_list[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

5 6
0 1
0 2
0 4
1 2
1 4
2 3
Adjacency list:
0 -> 1 2 4
1 -> 0 2 4
2 -> 0 1 3
3 -> 2
4 -> 0 1

Advantage of Adjacency Matrix and Adjacency List.

The adjacency list is more memory-efficient for sparse graphs (where the number of edges is much less than the number of vertices) and allows for faster iteration over the neighbors of a vertex.(alert-passed)

The adjacency matrix is more efficient for dense graphs (where the number of edges is close to the number of vertices) and allows for constant-time access to the weight or existence of an edge between any two vertices.(alert-passed)

Check Leap Year in Java.

In this article, we are going learn how to check if the given year is a leap year or not using Java Programming and we will use Java if-else condition to solve this problem.

Leap Year are those Year in which we have 366 days whereas a normal Year contains 365 days. In leap year, the month Feburary contain 29 days. (alert-success)

Algorithm for Leap Year.

Below algorithm used to check if a year is a leap year or not:

• Take an input year from the user.
• If the year is evenly divisible by 4, go to step 3. Otherwise, go to step 6.
• If the year is evenly divisible by 100, go to step 4. Otherwise, go to step 5.
• If the year is evenly divisible by 400, go to step 5. Otherwise, go to step 6.
• The year is a leap year (it has 366 days).
• The year is not a leap year (it has 365 days).

Java Code Implementation to Find Leap Year.

import java.util.Scanner;

public class LeapYear {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int year;
        
        // Prompt user to enter a year
        System.out.print("Enter a year: ");
        year = input.nextInt();
        
        // Check if the entered year is a leap year
        if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
            System.out.println(year + " is a leap year");
        }
        else {
            System.out.println(year + " is not a leap year");
        }
    }
}

Output 1:

Enter a year: 2020
2020 is a leap year

Output 1:

Enter a year: 2022
2020 is not a leap year

In the above code, a year is a leap year if it is divisible by 4 but not divisible by 100, or if it is divisible by 400. This algorithm is based on the rules of the Gregorian calendar, which is the calendar system used in most of the world today.

Find Largest Among Three Numbers in Java.

In this article, we are going to learn Java programs to find the greatest number among three integer numbers. There are multiple ways to solve this program and we will each of them one by one.

Approach 1: Find the Greatest using if-else statement.

In this approach, we will use if-else statements to compare the three numbers and find the greatest among them.

Java Example Code:

import java.util.Scanner;

public class GreatestOfThreeNumbers {

   public static void main(String[] args) {

      int num1, num2, num3;
      Scanner input = new Scanner(System.in);

      System.out.println("Enter three numbers:");
      num1 = input.nextInt();
      num2 = input.nextInt();
      num3 = input.nextInt();

      if (num1 > num2 && num1 > num3) {
         System.out.println(num1 + " is the greatest.");
      }
      else if (num2 > num1 && num2 > num3) {
         System.out.println(num2 + " is the greatest.");
      }
      else {
         System.out.println(num3 + " is the greatest.");
      }
   }
}

Output:

Enter three numbers:
12
23
11
23 is the greatest.

Here, we are taking input of three numbers from the user using the Scanner class. Then, we are using if-else statements to compare the numbers and print the greatest among them.

Approach 2: Using Math.max() method.

In this approach, we will use the Math.max() method to find the greatest among the three numbers.

Java Example Code:

import java.util.Scanner;

public class GreatestOfThreeNumbers {

   public static void main(String[] args) {

      int num1, num2, num3;
      Scanner input = new Scanner(System.in);

      System.out.println("Enter three numbers:");
      num1 = input.nextInt();
      num2 = input.nextInt();
      num3 = input.nextInt();

      int greatest = Math.max(num1, Math.max(num2, num3));
      System.out.println(greatest + " is the greatest.");
   }
}

Output:

Enter three numbers:
10
23
15
23 is the greatest.

Here, we are using the Math.max() method to find the greatest among the three numbers. We are taking input of three numbers from the user using the Scanner class and then passing them as arguments to the Math.max() method. The Math.max() method returns the greatest of the two numbers passed as arguments, so we are calling it twice to compare all three numbers.

Approach 3: Using Array and Loops.

In this approach, we will use arrays and loops to find the greatest among the three numbers.

Java Example Code:

//Java code for finding greatest number
import java.util.Scanner;

public class GreatestOfThreeNumbers {

   public static void main(String[] args) {

      int[] nums = new int[3];
      Scanner input = new Scanner(System.in);

      System.out.println("Enter three numbers:");
      for (int i = 0; i < 3; i++) {
         nums[i] = input.nextInt();
      }

      int greatest = nums[0];
      for (int i = 1; i < 3; i++) {
         if (nums[i] > greatest) {
            greatest = nums[i];
         }
      }
      System.out.println(greatest + " is the greatest.");
   }
}

Output:

Enter three numbers:
19
29
15
29 is the greatest.

Here, we are using an array to store the three numbers entered by the user. We are taking input of three numbers from the user using the Scanner class and then using a loop to store them in the array. Then, we are using another loop to compare the numbers in the array and find the greatest among them.