What is a Graph?

A Graph is a data structure used to represent relationships between different entities.

It consists of:

• Vertices (Nodes) → Represent entities

• Edges → Represent connections between nodes

Example:

• Social networks

• Maps and routes

• Web pages linking to each other

• Dependency graphs

---

Types of Graphs

1️⃣ Directed Graph → Edges have direction
2️⃣ Undirected Graph → Edges have no direction
3️⃣ Weighted Graph → Edges have weights (cost/distance)
4️⃣ Unweighted Graph → No weights

---

Graph Representation in Python

Most common representation in DSA interviews:

Adjacency List (Most Preferred)

graph = {
    1: [2, 3],
    2: [4],
    3: [],
    4: []
}

This means:

• 1 is connected to 2 and 3

• 2 is connected to 4

Time-efficient and memory-efficient.

---

BFS (Breadth First Search)

BFS explores level by level.

It uses a Queue.

When to Use BFS?

• Shortest path in unweighted graph

• Level order traversal

• Finding minimum steps

---

BFS Code (Python)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Time Complexity → O(V + E)

---

Example Question (BFS)

Question: Find the shortest path from node 1 to all other nodes in an unweighted graph.

👉 Use BFS because it guarantees shortest path in unweighted graphs.

---

DFS (Depth First Search)

DFS explores as deep as possible before backtracking.

It uses:

• Recursion (stack)

• Or an explicit stack

---

DFS Code (Recursive)

def dfs(graph, node, visited):
    if node in visited:
        return

    visited.add(node)
    print(node)

    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

Call it like:

visited = set()
dfs(graph, 1, visited)

Time Complexity → O(V + E)

---

When to Use DFS?

• Detect cycles

• Backtracking problems

• Topological sort

• Checking connectivity

---

Example Question (DFS)

Question: Detect if a graph has a cycle.

👉 DFS is commonly used for cycle detection.

---

Dijkstra’s Algorithm

Used to find the shortest path in a weighted graph.

⚠️ Works only when weights are non-negative.

---

When to Use Dijkstra?

• Shortest path in weighted graph

• Network routing

• Map navigation systems

---

Example Graph (Weighted)

graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}

Each tuple: (neighbor, weight)

---

Dijkstra’s Algorithm Code (Python)

import heapq

def dijkstra(graph, start):
    min_heap = [(0, start)]  # (distance, node)
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    while min_heap:
        current_distance, current_node = heapq.heappop(min_heap)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(min_heap, (distance, neighbor))

    return distances

---

Time Complexity of Dijkstra

Using Min-Heap (Priority Queue):

👉 O((V + E) log V)

---

Example Question (Dijkstra)

Question: Given a weighted graph and a source node, find the shortest path to all other nodes.

👉 Use Dijkstra if:

• Weights are non-negative

• You need shortest path

---

Graphs are one of the most powerful and frequently asked topics in DSA interviews.
If you master BFS, DFS, and Dijkstra, you can solve a large percentage of graph problems confidently.