Graphs BFS DFS Dijkstra & Shortest Path Algorithms

Introduction

Graphs are one of the most powerful and widely used data structures in computer science. Whether you are building a navigation system like Google Maps, analyzing social networks, or optimizing delivery routes in cities like Lahore or Karachi, graphs play a central role.

In simple terms, a graph data structure consists of nodes (vertices) connected by edges. These edges can be directed or undirected, and they can also carry weights (like distances or costs).

In this tutorial, you will learn:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Dijkstra Algorithm
• Shortest Path Algorithms

For Pakistani students preparing for coding interviews, university exams, or platforms like LeetCode and Codeforces, mastering these topics is essential. These algorithms are frequently asked in interviews and are foundational for advanced topics like AI, networking, and databases.

Prerequisites

Before starting this tutorial, you should be comfortable with:

• Basic programming (preferably Python or C++)
• Understanding of arrays and lists
• Basic recursion (for DFS)
• Queues and stacks
• Time and space complexity (Big-O notation)

If you're new, consider reviewing:

• Arrays vs Linked Lists
• Stacks and Queues
• Recursion basics

Core Concepts & Explanation

Graph Representation (Adjacency List vs Matrix)

A graph can be represented in two main ways:

1. Adjacency List

• Each node stores a list of its neighbors
• Efficient for sparse graphs

Example:

1 → [2, 3]
2 → [1, 4]
3 → [1]
4 → [2]

2. Adjacency Matrix

• A 2D array where matrix[i][j] = 1 if edge exists

Example:

    1 2 3 4
1 [ 0 1 1 0 ]
2 [ 1 0 0 1 ]
3 [ 1 0 0 0 ]
4 [ 0 1 0 0 ]

Breadth-First Search (BFS)

BFS explores a graph level by level, starting from a source node.

• Uses a queue
• Finds shortest path in unweighted graphs

Example:
Ahmad wants to find the shortest path between two friends in a social network.

Steps:

1. Start at source
2. Visit all neighbors
3. Move to next level

Depth-First Search (DFS)

DFS explores as deep as possible before backtracking.

• Uses a stack (or recursion)
• Useful for cycle detection, pathfinding

Example:
Fatima explores all paths in a maze until she reaches the end.

Dijkstra Algorithm

Used to find the shortest path in weighted graphs.

• Uses a priority queue
• Greedy approach

Example:
Ali wants to travel from Islamabad to Lahore with minimum fuel cost.

Practical Code Examples

Example 1: BFS Traversal in Python

from collections import deque

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

    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" ")

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

Line-by-line Explanation:

• deque → Efficient queue implementation
• visited → Keeps track of visited nodes
• queue = deque([start]) → Start from initial node
• while queue: → Loop until queue is empty
• popleft() → Remove front element (FIFO)
• for neighbor in graph[node]: → Visit neighbors
• if neighbor not in visited: → Avoid cycles

Example 2: Real-World Application (Shortest Route in Karachi)

import heapq

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

    pq = [(0, start)]

    while pq:
        current_distance, node = heapq.heappop(pq)

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

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

    return distances

Line-by-line Explanation:

• heapq → Implements priority queue
• distances → Stores shortest distances
• float('inf') → Initialize with infinity
• pq = [(0, start)] → Start node distance = 0
• heappop() → Get smallest distance node
• for neighbor, weight → Traverse edges
• distance = current_distance + weight → Relaxation step
• if distance < distances[neighbor] → Update shortest path

Common Mistakes & How to Avoid Them

Mistake 1: Not Tracking Visited Nodes

Problem:
Infinite loops in cyclic graphs

Wrong Code:

for neighbor in graph[node]:
    queue.append(neighbor)

Fix:

if neighbor not in visited:
    visited.add(neighbor)
    queue.append(neighbor)

Mistake 2: Using BFS Instead of Dijkstra

Problem:
BFS doesn’t work correctly on weighted graphs

Fix:
Use Dijkstra when weights are involved

Practice Exercises

Exercise 1: Find Shortest Path (Unweighted Graph)

Problem:
Given a graph, find shortest path from node A to B.

Solution:
Use BFS

def shortest_path(graph, start, end):
    from collections import deque
    queue = deque([(start, [start])])
    visited = set()

    while queue:
        node, path = queue.popleft()

        if node == end:
            return path

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

Exercise 2: Minimum Travel Cost in Pakistan

Problem:
Find cheapest route between cities (Lahore → Islamabad)

Solution:
Use Dijkstra

graph = {
    'Lahore': [('Faisalabad', 500), ('Multan', 800)],
    'Faisalabad': [('Islamabad', 600)],
    'Multan': [('Islamabad', 300)],
    'Islamabad': []
}

print(dijkstra(graph, 'Lahore'))

Frequently Asked Questions

What is a graph data structure?

A graph is a collection of nodes connected by edges. It is used to represent relationships such as roads, networks, and social connections.

How do I choose between BFS and DFS?

Use BFS for shortest paths in unweighted graphs. Use DFS when exploring all paths or solving problems like cycle detection.

What is the time complexity of Dijkstra algorithm?

The time complexity is O((V + E) log V) when using a priority queue.

Can BFS work for weighted graphs?

No, BFS only works correctly for unweighted graphs. For weighted graphs, use Dijkstra.

How do I practice graph problems effectively?

Start with basic traversal (BFS/DFS), then move to shortest path problems, and practice on platforms like LeetCode and HackerRank regularly.

Summary & Key Takeaways

• Graphs model real-world problems like maps and networks
• BFS is best for shortest paths in unweighted graphs
• DFS is useful for deep exploration and recursion problems
• Dijkstra finds shortest paths in weighted graphs
• Always track visited nodes to avoid infinite loops
• Choose the right algorithm based on problem type

Next Steps & Related Tutorials

To strengthen your DSA skills, explore these tutorials on theiqra.edu.pk:

• Learn Binary Trees for hierarchical data structures
• Master Dynamic Programming for optimization problems
• Understand Stacks and Queues for BFS/DFS foundations
• Study Greedy Algorithms for efficient decision making

These topics will help you build a strong foundation for coding interviews and real-world software development in Pakistan’s growing tech industry 🚀