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. Terminology

• Graph : A graph G consists of two types of elements: vertices and edges.
• Vertices/Nodes : The entities in the graph are represented by nodes or vertices.
• Edge : A Relationship or a connection is shown using an edge
• Multiple edges : Multiple edges are two or more edges that join the same two vertices
• Undirected Graph : Graph in which each connection is bidirectional
• Directed Graph : A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connect an ordered pair of vertices
• Self-loop : : A self-loop is an edge whose endpoints are a single vertex .
• Simple Graph : A graph is called simple if it has no self-loops and no multiple edges.
• Multigraph : if Graph has multiple edges
• Adjacent Nodes : Vertices that are both endpoints of the same edge.
• Adjacent Edges : Adjacent edges are two distinct edges that share an end vertex.
• Connected Graph : Graph in which every pair of vertices are connected to each other via an edge or a series of edges.
• Disconnected Graph :If there exist two nodes in Graph such that no path in Graph has those nodes as endpoints.
• Connected component: A connected component is a subgraph of the maximum size, in which every pair of vertices are connected by a path.
• Edge Weight/ Edge Cost : The value associated with the edge
• Weighted Graph: A weighted graph is a graph in which each edge is given a numerical weight.
• Unweighted Graph : Graph in which edges are not having any weight.
• Degree Of a Node : The degree of a vertex v is the number of edges that connect to v.
• InDegree : The number of edges incident on a node is called in-degree of the vertex.
• Out-degree: The number of edges emanating from a node is called the out-degree of a vertex.
• Path : A path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.
• Cycles : A cycle is a path in the graph, which ends at the vertex from where it started.
• Cyclic Graph : If the graph is having any kind of cycle in it, then it’s called a Cyclic Graph.
• Acyclic Graph : if the graph is having no cycles at all, it’s called an Acyclic graph .
• DAG : Directed Acyclic Graph
• Tree : A connected graph with no cycles is a Tree(connected simple acyclic graph).

6. What is Depth-First Search

DFS stands for Depth-First Search. It’s an algorithm used to traverse or search through data structures like graphs and trees.

DFS explores as far as possible along one path before backtracking.

Start from vertex A ,Traverse each node of one branch (as deep as possible)  ,Move to the next branch .

Example: Recursive Implementation of Depth-First Search

package com.rkdigitalschool.msil.Graph;
import java.util.ArrayList;
import java.util.Iterator;
//Recursive Implementation 
public class Graph 
{
	//Adjacency list representation 
	private ArrayList<Integer>[] graph;
	private int V;
	private boolean visited[];
	
	//Graph creation 
	public Graph(int vertices) {
		// TODO Auto-generated constructor stub
		V=vertices;
		graph=new ArrayList[V];
		visited=new boolean[V];
		
		for (int i = 0; i < V; i++) {
			graph[i]=new ArrayList<Integer>();
			
		}
	}

	//Adding edge  
	void addEdge(int src, int dest) {
		graph[src].add(dest);
	}
	
	//DFS -recusive  
        void dfsTraversal(int vertex) {
    	   visited[vertex]=true;
    	   System.out.println(vertex + " ");
    	
    	   Iterator<Integer> i=graph[vertex].listIterator();
    	   while (i.hasNext()) {
			int adj=i.next();
			if(!visited[adj]) {
				dfsTraversal(adj);
			}
		}
    }
    
    public static void main(String[] args) {	
    	Graph g=new Graph(13);
    	g.addEdge(1, 2);
    	g.addEdge(1, 3);
    	g.addEdge(1, 5);
    	g.addEdge(2, 4);
    	g.addEdge(2, 10);
    	g.addEdge(2, 5);
    	g.addEdge(2, 7);
    	g.addEdge(3, 6);
    	g.addEdge(4, 7);
    	g.addEdge(5, 2);
    	g.addEdge(5, 8);
    	g.addEdge(8, 11);
    	g.addEdge(11,12);
    	
    	System.out.println("DFS traversal -recusrsive");
    	g.dfsTraversal(1);
    }
}

Example: Iterative Implementation of Depth-First Search

package com.rkdigitalschool.msil.Graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Stack;
//Graph iterative implementation
public class GraphIterative {
	//Adjacency list representation 
	private ArrayList<Integer>[] graph;
	private int V;
	private boolean visited[];
	//Graph creation 
	public GraphIterative(int vertices) {
		// TODO Auto-generated constructor stub
		V=vertices;
		graph=new ArrayList[V];
		visited=new boolean[V];

		for (int i = 0; i < V; i++) {
			graph[i]=new ArrayList<Integer>();

		}
	}

	//Adding edge  
	void addEdge(int src, int dest) {
		graph[src].add(dest);
	}

	//DFS - iterative   
	void dfsTraversaliterative(int s) {

		Arrays.fill(visited, false);
		Stack<Integer> stack=new Stack<>();
		stack.push(s);
		while (!stack.isEmpty()) 
		{
                 s=stack.pop();
                 if(!visited[s]) {
                	System.out.println(s+"");
                	visited[s]=true;
                    }
		}
		Iterator<Integer> itr=graph[s].iterator();
		while (itr.hasNext()) {
			int v=itr.next();
			if(!visited[v]) {
				stack.push(v);
			}
		}
	}

	public static void main(String[] args) {

		GraphIterative g=new GraphIterative(13);

		g.addEdge(1, 2);
		g.addEdge(1, 3);
		g.addEdge(1, 5);
		g.addEdge(2, 4);
		g.addEdge(2, 10);
		g.addEdge(2, 5);
		g.addEdge(2, 7);
		g.addEdge(3, 6);
		g.addEdge(4, 7);
		g.addEdge(5, 2);
		g.addEdge(5, 8);
		g.addEdge(8, 11);
		g.addEdge(11,12);

		System.out.println("DFS traversal -recusrsive");
		g.dfsTraversaliterative(1);
	}
}

7.Breath first search

BFS (Breadth-First Search) is a fundamental algorithm used to traverse or search through a graph (or a tree). It explores nodes level by level, starting from a given source node.

BFS visits all the neighbours of a node first, before moving to the next level of neighbours.

How BFS Works

1. Start from a source node.
2. Mark it as visited.
3. Put it into a queue (FIFO – First In First Out).
4. Repeat until the queue is empty:
   • Remove a node from the front of the queue.
   • Visit all its unvisited neighbors.
   • Mark them visited and add them to the queue.

Example : Breadth first Search implementation

package com.rkdigitalschool.msil.Graph;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
public class Graphs {
	private ArrayList<Integer>[] graph;
	private int v;
	private boolean visited[];

	public Graphs(int vertices) {
		// TODO Auto-generated constructor stub
		v=vertices;
		graph=new ArrayList[v];
		visited=new boolean[v];

		for (int i = 0; i < v; i++) {
			graph[i]=new ArrayList<Integer>();
		}
	}
	//Adding edge 
	void addEdge(int src, int dest) {
		graph[src].add(dest);
	}

	//BFS traversal 
	void bfsTraversal(int s) {

		LinkedList<Integer> queue=new LinkedList<>();
		queue.add(s);
		visited[s]=true;

		while (queue.size()!=0) {
			int current= queue.poll();

			Iterator<Integer> itr=graph[current].listIterator();
			while (itr.hasNext()) {
				int next = itr.next();

				if(!visited[next]) {
					visited[next]=true;
					queue.add(next);
				}
			}
			System.out.print(current + " ");
		}
	}
	public static void main(String[] args) {
		Graphs g=new Graphs(13);

		g.addEdge(1, 2);
		g.addEdge(1, 3);
		g.addEdge(1, 5);
		g.addEdge(2, 4);
		g.addEdge(2, 10);
		g.addEdge(2, 5);
		g.addEdge(2, 7);
		g.addEdge(3, 6);
		g.addEdge(4, 7);
		g.addEdge(5, 2);
		g.addEdge(5, 8);
		g.addEdge(8, 11);
		g.addEdge(11,12);
		
		
		System.out.println("@@@@@@@@@@@@@@@@@2");
		g.bfsTraversal(1);
		
	}
}

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();
    }
}