Graph

The Backbone of Networks and Relationships

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

Graph Operations – Adjacency List vs Adjacency Matrix

1. Add Vertex

• Adjacency List: O(1)

• Adjacency Matrix: O(V²)

2. Add Edge

• Adjacency List: O(1)

• Adjacency Matrix: O(1)

3. Check if Edge Exists

• Adjacency List: O(V)

• Adjacency Matrix: O(1)

4. Traverse All Vertices / Edges

• Adjacency List: O(V + E)

• Adjacency Matrix: O(V²)

---

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

💡Trade-off: Choose based on the graph’s density and the operations you need.

---

📘 LeetCode Practice Problems

1. Clone Graph – Medium – LeetCode#133

2. Course Schedule – Medium – LeetCode#207

3. Number of Islands – Medium – LeetCode#200

4. Graph Valid Tree – Medium – LeetCode#261

5. Reconstruct Itinerary – Hard – LeetCode#332

6. Word Ladder – Hard – LeetCode#127

7. Network Delay Time – Medium – LeetCode#743

8. Find Eventual Safe States – Medium – LeetCode#802

---

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

Happy coding! 🚀

Nitin
Hashnode | Substack | LinkedIn | GIT | Youtube | Instagram