# Graph in DSA 

## 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)

```python
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?

*   <mark class="bg-yellow-200 dark:bg-yellow-500/30">Shortest path</mark> in unweighted graph
    
*   Level order traversal
    
*   Finding minimum steps
    

* * *

## BFS Code (Python)

```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)

```python
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:

```python
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)

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

Each tuple: `(neighbor, weight)`

* * *

## Dijkstra’s Algorithm Code (Python)

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