Chapter 29: DSA Graphs

DSA Graphs – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing examples step by step, explaining every concept slowly and clearly, giving many real-world analogies, showing different representations, and most importantly telling you why graphs are one of the most important and most frequently asked topics in interviews and real software engineering.

What is a Graph?

A Graph is a non-linear data structure consisting of vertices (also called nodes) and edges (connections between nodes).

In simple words:

A graph is a collection of points (vertices) connected by lines (edges).

Unlike trees (which are hierarchical and have no cycles), graphs can have any kind of connection — they are much more general.

Real-life examples of Graphs (very important to build intuition)

Basic Graph Terminology (must remember these)

Types of Graphs (very frequently asked)

How Graphs are Represented in Code (very important)

There are two main ways to represent graphs:

1. Adjacency Matrix (2D array)

• matrix[i][j] = 1 → there is an edge from i to j (or undirected)
• For weighted: store weight instead of 1
• Space: O(V²) where V = number of vertices

Advantages:

• Checking edge existence → O(1)
• Good for dense graphs

Disadvantages:

• Wastes space if graph is sparse

2. Adjacency List (most common in interviews)

• Each vertex → list of its neighbors
• Space: O(V + E) — much better for sparse graphs
• Adding edge → O(1)
• Checking edge → O(degree)

In Python — dictionary of lists (or sets for faster lookup)

In C++ — vector<vector<int>> adj;

In Java — List<List<Integer>> adj;

Most interviews prefer adjacency list because it is more memory efficient.

Basic Graph Traversals (very important)

There are two main ways to visit all nodes in a graph:

1. Depth-First Search (DFS) → Go as deep as possible before backtracking → Uses stack (recursive or explicit)
2. Breadth-First Search (BFS) → Visit level by level → Uses queue

Both can be used to:

• Find if path exists
• Find shortest path (in unweighted graph → BFS)
• Detect cycle
• Find connected components

Very Simple Example – Social Network Graph

Vertices: Alice, Bob, Charlie, David, Eve

Edges (undirected friendship):

• Alice ↔ Bob
• Alice ↔ Charlie
• Bob ↔ David
• Charlie ↔ David
• David ↔ Eve

Adjacency list:

DFS from Alice (possible order): Alice → Bob → David → Charlie → Eve

BFS from Alice (level order): Alice → (Bob, Charlie) → (David) → Eve

Summary – Graphs in one line each

• Collection of vertices connected by edges
• Can be directed / undirected, weighted / unweighted, cyclic / acyclic
• Most common representations: Adjacency List (preferred), Adjacency Matrix
• Two main traversals: DFS (stack/recursion), BFS (queue)
• Basis for shortest path, cycle detection, connected components, topological sort, etc.
• One of the most important topics in interviews — almost every company asks graph problems
• Most famous algorithms: BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal, Prim, Topological Sort

Would you like to continue with any specific graph topic next?

Very common next steps:

• Graph representation – adjacency list vs matrix with examples
• DFS vs BFS – when to use which + code + dry run
• Cycle detection in directed & undirected graph
• Shortest path – BFS (unweighted), Dijkstra (weighted)
• Topological Sort (very frequent in interviews)
• Connected Components / Islands problem pattern

Just tell me which direction you want to go — I’ll explain it in the same detailed, step-by-step, human-teacher style with clear examples and visuals! 😊