Lesson 1 � Beginner

Graph: Representation aur Types

Graph ek non-linear data structure hai jismein nodes (vertices) aur unhe connect karne wale edges hote hain. Trees sirf hierarchical hote hain, par graphs kisi bhi relationship ko model kar sakte hain � social networks, maps, networks sab.

Graph kya hota hai?

Graph ek collection hai vertices (V) aur edges (E) ka. Har edge do vertices ko connect karta hai. Formally: G = (V, E)

Socho tumhare paas 4 cities hain � A, B, C, D. Agar A se B road hai, B se C road hai, toh yeh ek graph hai. Cities vertices hain, roads edges hain.

 A --- B
 | |
 C D

Directed vs Undirected, Weighted vs Unweighted

Graphs ki 4 main types hain:

• Undirected Graph: Edges bidirectional hain. A ✓ B ka matlab A se B ja sakte ho aur B se A bhi. Jaise Facebook friendship.
• Directed Graph (Digraph): Edges unidirectional hain. A ✓ B ka matlab sirf A se B ja sakte ho. Jaise Twitter follow � tum follow kar sakte ho, zaruri nahi ki woh tumhe follow kare.
• Weighted Graph: Har edge ka ek weight (cost/distance) hota hai. Jaise road map mein har road ka distance alag hai.
• Unweighted Graph: Sab edges equal hain, koi weight nahi. Bas connectivity matter karti hai.

Adjacency List vs Adjacency Matrix

Graph ko code mein represent karne ke 2 tarike hain:

Adjacency List: Har vertex ke paas ek list hai jo uske neighbors store karti hai. Space efficient � O(V + E).

graph = {
 'A': ['B', 'C'],
 'B': ['A', 'D'],
 'C': ['A'],
 'D': ['B']
}

Adjacency Matrix: 2D matrix jismein matrix[i][j] = 1 agar edge hai, 0 agar nahi. Fast lookup � O(1), par space zyada � O(V�).

 A B C D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 0 ]
D [ 0, 1, 0, 0 ]

Kab kya use karein?

• Adjacency List: Sparse graphs ke liye (edges kam hain). Zyada tar real-world graphs sparse hote hain.
• Adjacency Matrix: Dense graphs ke liye (edges bahut hain) ya jab quick edge lookup chahiye.
• Competitive programming mein adjacency list zyada use hoti hai kyunki most graphs sparse hote hain.

Degree of a Vertex

• Undirected mein: Degree = kitne edges vertex se attach hain. A ki degree = 2 (B aur C se connected).
• Directed mein: In-degree = kitne edges vertex par aa rahe hain. Out-degree = kitne edges vertex se ja rahe hain.

Try it: code khud likho

Edges: A?B, A?C, B?D, C?D, D?A

Common mistakes

• Directed graph mein dono taraf edge add kar dena � galat hai, sirf ek direction mein add karo.
• Adjacency list mein node initialize karna bhool jaana � pehle check karo ki key exist karti hai ya nahi.
• Weighted graph mein sirf neighbor store karna aur weight bhool jaana � tuple use karo: (neighbor, weight).
• Graph traversal mein visited track karna bhool jaana � infinite loop mein phas jaoge.