Graphs

🎯 Objective: Learn the fundamental concept of a Graph data structure and implement it in Java.

📝 Table of Contents

1. Introduction to Graphs
2. Types of Graphs
3. Graph Representation
4. Java Implementation
5. Summary

1️⃣ Introduction to Graphs

Graphs are one of the most versatile data structures used in computer science. A graph consists of nodes, often called vertices, and edges that connect pairs of vertices. Unlike arrays or linked lists, graphs can represent complex relationships between elements.

Why use Graphs?

• Model Network Topologies
• Solve Routing Problems
• Social Network Analysis
• Represent Hierarchies
• … and much more!

2️⃣ Types of Graphs

1. Undirected Graph: Edges do not have a direction.
2. Directed Graph: Edges have a direction.
3. Weighted Graph: Edges have weights or costs associated with them.

3️⃣ Graph Representation

There are two popular ways to represent a graph:

1. Adjacency Matrix: A 2D array where the cell [i][j] is true if there is an edge from vertex i to vertex j.
2. Adjacency List: An array of lists. The index represents the vertex, and each element in the list represents the vertices that the index vertex is connected to.

4️⃣ Java Implementation

Adjacency List Implementation:

import java.util.LinkedList;

public class Graph {
    int vertices;
    LinkedList<Integer>[] adjacencyList;

    // Constructor
    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    // Add Edge
    public void addEdge(int src, int dest) {
        // For undirected graph
        adjacencyList[src].add(dest);
        adjacencyList[dest].add(src);
    }

    // Display the graph
    public void displayGraph() {
        for (int i = 0; i < vertices; i++) {
            System.out.print("Vertex " + i + " is connected to: ");
            for (int j = 0; j < adjacencyList[i].size(); j++) {
                System.out.print(adjacencyList[i].get(j) + " ");
            }
            System.out.println();
        }
    }

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

        graph.displayGraph();
    }
}

Output:

Vertex 0 is connected to: 1 4
Vertex 1 is connected to: 0 3
Vertex 2 is connected to: 3 4
Vertex 3 is connected to: 1 2
Vertex 4 is connected to: 0 2

5️⃣ Summary

Graphs are incredibly flexible and widely used in various fields of computer science. In this post, we’ve covered the basics and provided a simple Java implementation. Happy learning!