🕸️ Graph

Introduction

Graphs are incredibly powerful data structures that allow us to model complex relationships between entities. From social networks and recommendation engines to routing maps and dependency resolution, graphs are everywhere.

📌 What Is a Graph?

A graph is a non-linear data structure that consists of:

• Vertices (nodes): The fundamental units or points.

• Edges: Connections between pairs of vertices.

Graphs can be:

• Directed vs. Undirected
  → Directed edges have direction (e.g., A → B), whereas undirected edges don't (A — B).

• Weighted vs. Unweighted
  → Weighted graphs have costs or weights associated with edges.

• Cyclic vs. Acyclic
  → Cyclic graphs contain cycles, while acyclic ones do not.

• Connected vs. Disconnected
  → A connected graph has a path between every pair of vertices.

🧮 Representing a Graph in Code

1. Adjacency Matrix (2D Array)

int[][] graph = {
    {0, 1, 0},
    {1, 0, 1},
    {0, 1, 0}
};

• Time to check edge existence: O(1)

• Space: O(V²)

2. Adjacency List (Array of Lists)

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

graph.get(0).add(1);
graph.get(1).add(2);

• Time to traverse: O(V + E)

• Space: O(V + E)

🔁 Common Graph Traversal Techniques

1. Breadth-First Search (BFS)

• Explores neighbors level by level using a queue.

Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.add(start);
visited[start] = true;

while (!queue.isEmpty()) {
    int node = queue.poll();
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            queue.add(neighbor);
        }
    }
}

2. Depth-First Search (DFS)

• Goes deep along each path using recursion or a stack.

void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) dfs(neighbor, visited, graph);
    }
}

⚙️ Common Operations & Time Complexities

🧠 Real-World Analogy

Think of a graph as a city map:

• Intersections = Vertices

• Roads = Edges

• One-way streets = Directed Edges

• Tolls = Weights

This is how navigation systems, airline networks, and web crawlers operate!

🧵 Memory Layout

🔸 Adjacency Matrix

• Suitable for dense graphs (many connections).

• Requires a 2D matrix of size V×V.

• Simpler to implement but memory-heavy.

🔹 Adjacency List

• Suitable for sparse graphs (few connections).

• Efficient memory usage.

• Uses lists for each node to store neighbors.

📘 LeetCode Practice Problems

🎯 Tips for Interview Prep

• Understand when to use BFS vs. DFS.

• Practice topological sorting (for DAGs).

• Be clear on how to detect cycles in both directed and undirected graphs.

• Learn Union-Find for connected components.

• Try drawing out graphs during problem-solving to better visualize paths and states.

🔚 Wrapping Up

Graphs unlock a powerful way to represent and navigate complex relationships and structures. Once you understand how to traverse and build them efficiently, a whole new category of problems becomes solvable.

🧱 Stay tuned for the next post on Union-Find – A Disjoint Set Structure for Connectivity Problems.

🙌 Enjoying the Series?

This blog is part of my DSA series — “Level Up Your Programming with Nitin”, where I break down core data structures and algorithms with clear explanations, real-world analogies, Java code snippets, and curated LeetCode problems.

You can explore the entire series anytime here:
🔗 DS Interview Prep Series

If you find it helpful, feel free to share with peers, bookmark it for revision, or leave a ❤️ to support the effort.

🔗 Follow my blog on Hashnode: ns717.hashnode.dev
💼 Connect with me on LinkedIn: Nitin Singh

Thanks for reading, and happy coding! 💻🌳