What is Data Structure .

A Data structure is specialized format for organizing , processing , retrieving and storing data . it defines the relationship between data and the operations. that can be performed of the data common data structures include arrays , linked lists ,stacks , queues , tree and graph .

Benefits of data structures

1. Efficiency : Data structures allow for efficient data manipulation and retrieval . for example searching for an element in a balanced binary search tree is faster than searching in an unsorted array .
2. Reusability : will defined data structures can be reused across different programs and applications .
3. Abstraction : they provide a way to manage large amount of data by abstraction the details of data storage and manipulation .
4. Optimization : Data Structure help in optimizing the performance of algorithms by providing the most suitable way to store and access data .

2.What is a Graph Data Structure?

A Graph is a non‑linear data structure that represents relationships between pairs of objects.
It consists of:

• Vertices (Nodes) → represent entities
• Edges → represent connections/relationships between entities

Example:

• Cities (vertices) connected by roads (edges)
• Users (vertices) connected by friendships (edges) in social networks

Adjacency

Two vertices are said to be adjacent to one another if they are connected by a single edge .

Paths : A path is a sequence of edges.

Connected Graphs

A graph is said to be connected if there is at least one path from every vertex to every other vertex .

3. Types of Graphs

1. Based on Direction

• Directed Graph (Digraph) — A directed graph is a graph where each edge has a direction .
• Undirected Graph — edges have no direction.

2. Based on Weight

• Weighted Graph — edges carry weights (cost, distance)
• Unweighted Graph — no weight on edges

3. Based on Cycles

• Cyclic Graph
• Acyclic Graph (DAG – Directed Acyclic Graph)

4. Based on Connectivity

• Connected Graph
• Disconnected Graph

4.Purpose of Graph Data Structure

Graphs are used to represent real‑world relationships, networks, and systems. Their purposes include:

 1. Modelling Relationships

Graphs capture “how objects are related”, not just the objects themselves.

2. Network Representations

Used in:

• Social networks (Facebook, LinkedIn)
• Road maps (Google Maps)
• Network routing (Internet)

3. Optimization Problems

• Shortest path
• Minimum cost
• Maximum flow
• Scheduling (using DAG)

4. Recommendation Systems

Used for analyzing relationships:

• “People you may know”
• Product recommendations
• Content recommendation (YouTube, Netflix)

5.Graph Operations List

1. Create a Graph

Using:

• Adjacency Matrix
• Adjacency List
• Edge List
• HashMap of lists (most efficient)

🔸 2. Add Vertex

Add a new node to the graph.

🔸 3. Add Edge

Connect two nodes:

• Directed
• Undirected
• Weighted

🔸 4. Remove Vertex

Delete a node and all edges connected to it.

🔸 5. Remove Edge

Delete connection between nodes.

🔸 6. Traversal Operations

a) BFS (Breadth‑First Search)

• Uses Queue
• Level-wise traversal
• Finds shortest path in unweighted graph

b) DFS (Depth‑First Search)

• Uses Stack / Recursion
• Explores deep paths first

🔸 7. Shortest Path Algorithms

• Dijkstra’s Algorithm (weighted, no negative)
• Bellman‑Ford Algorithm
• Floyd–Warshall Algorithm

🔸 8. Minimum Spanning Tree (MST)

• Prim’s Algorithm
• Kruskal’s Algorithm

🔸 9. Cycle Detection

• Using DFS
• Union-Find (Disjoint Set)

🔸 10. Topological Sorting

For Directed Acyclic Graph (DAG).
Used in:

• Task scheduling
• Build systems

🔸 11. Connectivity Checks

• Strongly Connected Components (SCC)
• Weakly Connected Components

🔸 12. Graph Coloring

Used in:

• Compilers
• Register allocation
• Exam timetabling

6. Graph Implementation (Adjacency List)

1. What is an Adjacency List?

An Adjacency List represents a graph using a list of neighbors for each vertex. It uses HashMap/List or an array of lists.

Definition

• For each vertex, store all vertices that are directly connected to it.

1.Graph.java

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList;
    private boolean isDirected;

    // Constructor
    public Graph(boolean isDirected) {
        this.adjList = new HashMap<>();
        this.isDirected = isDirected;
    }

    // Add a vertex
    public void addVertex(int v) {
        adjList.putIfAbsent(v, new ArrayList<>());
    }

    // Add an edge
    public void addEdge(int src, int dest) {
        addVertex(src);
        addVertex(dest);

        adjList.get(src).add(dest);

        if (!isDirected) {
            adjList.get(dest).add(src);
        }
    }

    // Remove edge
    public void removeEdge(int src, int dest) {
        List<Integer> list = adjList.get(src);
        if (list != null) list.remove((Integer) dest);

        if (!isDirected) {
            List<Integer> list2 = adjList.get(dest);
            if (list2 != null) list2.remove((Integer) src);
        }
    }

    // Remove vertex
    public void removeVertex(int v) {
        adjList.remove(v);

        // Remove v from all adjacency lists
        for (List<Integer> neighbors : adjList.values()) {
            neighbors.remove((Integer) v);
        }
    }

    // BFS Traversal
    public void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

        for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    // DFS Traversal
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start, visited);
    }

    private void dfsHelper(int node, Set<Integer> visited) {
        visited.add(node);
        System.out.print(node + " ");

        for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited);
            }
        }
    }

    // Print Graph
    public void printGraph() {
        for (int v : adjList.keySet()) {
            System.out.println(v + " -> " + adjList.get(v));
        }
    }
}

2. Test the Graph

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(false);  // false = undirected graph

        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.addEdge(3, 5);

        System.out.println("Graph:");
        g.printGraph();

        System.out.println("\nBFS starting from 1:");
        g.bfs(1);

        System.out.println("\nDFS starting from 1:");
        g.dfs(1);
    }
}

Output Example

Graph:
1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 5]
4 -> [2]
5 -> [3]
	
BFS starting from 1:
1 2 3 4 5 

DFS starting from 1:
1 2 4 3 5

7. How to Create Matrix Graph Using Adjacency in java

What is an Adjacency Matrix?

An Adjacency Matrix is a 2D array (matrix) used to represent a graph. If a graph has V vertices, the matrix size is V × V. and Adjacent matrix good for Small and dense graph .

Definition

• matrix[i][j] = 1 → edge exists between vertex i and j
• matrix[i][j] = 0 → no edge exists

Example (Undirected Graph)

Graph:
1 — 2
1 — 3
2 — 4

Adjacency Matrix:

	1	2	3	4
1	0	1	1	0
2	1	0	0	1
3	1	0	0	0
4	0	1	0	0

1.Graph.java

Java Implementation : 
public class Graph 
{
    private int[][] adjacencyMatrix;
    private int numVertices;
    private boolean isDirected;
    private boolean isWeighted;

    public Graph(int numVertices, boolean isDirected, boolean isWeighted) {
        this.numVertices = numVertices;
        this.isDirected = isDirected;
        this.isWeighted = isWeighted;
        adjacencyMatrix = new int[numVertices][numVertices]; // default values = 0
    }

    // Add edge
    public void addEdge(int src, int dest, int weight) {
        if (isWeighted) {
            adjacencyMatrix[src][dest] = weight;
        } else {
            adjacencyMatrix[src][dest] = 1;
        }

        if (!isDirected) {
            adjacencyMatrix[dest][src] = weight;
        }
    }

    // Remove edge
    public void removeEdge(int src, int dest) {
        adjacencyMatrix[src][dest] = 0;

        if (!isDirected) {
            adjacencyMatrix[dest][src] = 0;
        }
    }

    // Print matrix
    public void printGraph() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

2. Main.java

public class Main {
    public static void main(String[] args) {
        
        // 5 vertices, directed, weighted
        Graph graph = new Graph(5, true, true);

        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 3, 5);
        graph.addEdge(1, 2, 2);
        graph.addEdge(3, 4, 15);

        graph.printGraph();
    }
}