Graph guide

[temptation4]

A graph is a non-linear data structure used to represent relationships between different objects.
Each object is called a vertex (node)
The connection between two nodes is called an edge

👉 In simple words:
Graph = Nodes + Connections

Circles → Vertices (Nodes)
Lines → Edges (Connections)

🔁 Graph Traversal

🌳 Breadth-First Search (BFS)

boolean[] visited = new boolean[V];
Queue<Integer> q = new LinkedList<>();

q.offer(start);
visited[start] = true;

while (!q.isEmpty()) {
    int node = q.poll();

    for (int nei : adj.get(node)) {
        if (!visited[nei]) {
            visited[nei] = true;
            q.offer(nei);
        }
    }
}

👉 Explores nodes level by level
👉 Uses Queue (FIFO)
👉 Best for shortest path (unweighted graph)

---

🌳 Depth-First Search (DFS)

void dfs(int node, boolean[] visited) {
    visited[node] = true;

    for (int nei : adj.get(node)) {
        if (!visited[nei]) {
            dfs(nei, visited);
        }
    }
}

👉 Goes deep first, then backtracks
👉 Uses Stack / Recursion
👉 Useful for cycle detection, path finding

🧱 Graph Building (Step-by-Step)

Below image shows how a graph is built step-by-step using edges.

🔹 Step 1: Start with single node
Only node 1 exists
No connections

Add node 2 → connect to 1
Add node 3 → connect to 1
Add node 4 → connect to 3
Add node 5 → connect to 2
Add node 6 → connect to 1

💻 Java Code for creating Graph

import java.util.*;

public class Graph {

    private int V;
    private List<List<Integer>> adj;

    // Constructor
    public Graph(int V) {
        this.V = V;
        adj = new ArrayList<>();

        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    // Add edge (undirected)
    public void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    // Print graph (Adjacency List)
    public void printGraph() {
        for (int i = 1; i < V; i++) {
            System.out.print(i + " -> ");
            for (int nbr : adj.get(i)) {
                System.out.print(nbr + " ");
            }
            System.out.println();
        }
    }

    // MAIN METHOD
    public static void main(String[] args) {

        Graph g = new Graph(7); // nodes 1 to 6

        // STEP 1: Build tree-like structure
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(3, 4);
        g.addEdge(2, 5);
        g.addEdge(1, 6);

        // STEP 2: Add extra edges (make graph complex)
        g.addEdge(2, 3);
        g.addEdge(1, 4);
        g.addEdge(4, 5);
        g.addEdge(5, 6);
        g.addEdge(3, 6);

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

---

👤 Example

A = Person
B = Person
Edge = Friendship

---

🔗 Real-Life Examples of Graphs

👉 Real-world graphs represent:

• Social networks
• Maps & navigation
• Computer networks
• Flight routes

---

📌 Types of Graphs

1. Directed vs Undirected Graph

🔹 Undirected Graph
Edges have no direction → A — B

🔹 Directed Graph
Edges have direction → A → B

---

2. Weighted vs Unweighted Graph

🔹 Weighted → edges have cost (distance/time)
🔹 Unweighted → all edges equal

---

3. Cyclic vs Acyclic Graph

🔹 Cyclic → contains loop
🔹 Acyclic → no loop

---

📊 Graph Representation (VERY IMPORTANT)

1. Adjacency Matrix

👉 2D array representation
👉 1 → edge exists
👉 0 → no edge

---

2. Adjacency List (Most Used)

👉 Stores neighbors of each node
👉 More memory efficient than matrix

---

⚡ Quick Summary

• Graph = Nodes + Edges
• BFS → Level-wise traversal
• DFS → Depth-first traversal
• Adjacency List → Most efficient representation

---

🎯 Why Graphs Matter

Graphs are heavily used in:

• System design
• Routing algorithms
• Social media platforms
• Real-time applications

---

👨‍💻 Author

Neelu Sahai