Learn Graphs – BFS, DFS & Applications

01

Introduction to Graphs

A Graph is a non-linear data structure consisting of a set of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles, multiple paths between nodes, and disconnected components — making them one of the most versatile structures in computer science.

Graphs come in several fundamental forms depending on how edges are defined:

→

Directed Graph

Edges have a specific direction from one vertex to another (A → B ≠ B → A).

↔

Undirected Graph

Edges have no direction; the connection between two nodes is bidirectional.

⚖

Weighted Graph

Edges carry a numerical weight or cost, e.g. distances in a road network.

○

Unweighted Graph

All edges are equal — traversal only considers connectivity, not cost.

🔄

Cyclic Graph

Contains at least one cycle — a path that starts and ends at the same vertex.

🌳

Acyclic Graph (DAG)

Directed graph with no cycles. Used in scheduling and dependency resolution.

Graph Representation

Adjacency Matrix: 2D array where matrix[i][j] = 1 if edge exists. O(V²) space.
Adjacency List: Each node stores a list of its neighbours. O(V + E) space — preferred for sparse graphs.
Edge List: Simple list of all edges as pairs (u, v). Easy to iterate.

Python — Adjacency List

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

Quick Check

What are the two main components of every graph data structure?

Answer: Vertices (Nodes) and Edges

Vertices represent entities (people, cities, web pages) and edges represent relationships or connections between them.

02

Graph Terminology

Before exploring algorithms, it's essential to speak the language of graphs. These terms appear throughout every graph problem and interview discussion.

Vertex Edge Degree Path Cycle Connected Weighted Acyclic

Key Definitions

Vertex (Node): The fundamental unit of a graph. Represents an entity.
Edge: A connection between two vertices. Can be directed or undirected.
Degree: Number of edges connected to a vertex. In directed graphs: in-degree (incoming) and out-degree (outgoing).
Path: A sequence of vertices where each pair is connected by an edge and no vertex is repeated.
Cycle: A path that starts and ends at the same vertex with no repeated edges.
Connected Graph: Every vertex is reachable from every other vertex.
Disconnected Graph: Some vertices have no path between them.
Spanning Tree: A subgraph that includes all vertices with the minimum number of edges (no cycles).
Neighbour: Two vertices connected by a direct edge are neighbours (adjacent).
Self-loop: An edge where a vertex connects to itself.

Vertex	Neighbours	Degree	Note
A	B, C, D	3	Hub node
B	A, D, E	3	Hub node
C	A, D	2	—
D	A, B, C	3	Hub node
E	B	1	Leaf node

Quick Check

In a directed graph, if vertex A has 3 incoming edges and 2 outgoing edges, what is its in-degree and out-degree?

Answer: In-degree = 3, Out-degree = 2

In a directed graph, in-degree counts edges pointing into the vertex, and out-degree counts edges going out from the vertex. They are tracked independently.

03

Breadth-First Search (BFS)

BFS explores a graph level by level — visiting all neighbours of a node before moving deeper. It uses a Queue (FIFO) to track nodes to visit next. BFS always finds the shortest path in an unweighted graph.

How BFS Works

Start at the source vertex. Mark it visited and enqueue it.
While the queue is not empty, dequeue a vertex and process it.
For each unvisited neighbour of the current vertex, mark it visited and enqueue it.
Repeat until the queue is empty.

01

Enqueue start node A. Visited = {A}. Queue = [A]

02

Dequeue A. Enqueue neighbours B, C. Visited = {A,B,C}. Queue = [B,C]

03

Dequeue B. Enqueue unvisited neighbour D, E. Queue = [C,D,E]

04

Continue until queue is empty. BFS order: A → B → C → D → E

Pseudocode — BFS

function BFS(graph, start):
    queue   = new Queue()
    visited = empty set

    queue.enqueue(start)
    visited.add(start)

    while queue is not empty:
        node = queue.dequeue()
        process(node)

        for each neighbour of node:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.enqueue(neighbour)

Python — BFS Implementation

from collections import deque

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

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return result

BFS Complexity

Time: O(V + E) — each vertex and edge is processed once.
Space: O(V) — queue can hold at most V nodes.
Shortest Path: BFS guarantees shortest path in unweighted graphs.

Practice: BFS Data Structure

Which data structure is essential to implement BFS iteratively, and why?

Answer: Queue (FIFO — First In, First Out)

A queue ensures nodes are visited in the order they were discovered — level by level. This guarantees that all nodes at distance k are visited before any node at distance k+1, which is exactly what BFS needs to find shortest paths.

04

Depth-First Search (DFS)

DFS explores a graph by diving as deep as possible along a path before backtracking. It uses a Stack (or recursion) rather than a queue. DFS is ideal for detecting cycles, topological sorting, and solving mazes.

How DFS Works

Start at the source vertex. Mark it visited.
Recursively visit any unvisited neighbour, going as deep as possible.
When no unvisited neighbours remain, backtrack to the previous vertex.
Repeat until all vertices reachable from source are visited.

01

Visit A. Visited = {A}. Push to stack.

02

Visit first neighbour B. Push B. Go deeper.

03

From B, visit D. No unvisited neighbours. Backtrack to B.

04

From B, visit E. Backtrack to A. Visit C. DFS order: A → B → D → E → C

Pseudocode — DFS (Recursive)

function DFS(graph, node, visited):
    // mark and process current node
    mark node as visited
    process(node)

    for each neighbour of node:
        if neighbour not in visited:
            DFS(graph, neighbour, visited)

Python — DFS Recursive + Iterative

# Recursive DFS
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited)

# Iterative DFS using explicit stack
def dfs_iterative(graph, start):
    visited = set()
    stack   = [start]
    result  = []
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            stack.extend(reversed(graph[node]))
    return result

Property	BFS	DFS
Data Structure	`Queue (FIFO)`	`Stack / Recursion`
Traversal Order	Level by level	Path to dead-end, then backtrack
Shortest Path	✅ Yes (unweighted)	❌ Not guaranteed
Memory Use	Higher (wide graphs)	Lower (deep graphs)
Cycle Detection	Possible	Efficient
Use Case	Shortest path, social networks	Topological sort, maze solving

Practice: DFS vs BFS

You need to find whether a path exists between two nodes in a large graph. Which traversal would you choose, and why?

Answer: Either works, but DFS is often preferred for reachability.

DFS uses less memory (stack depth vs wide BFS queue) and quickly reaches distant nodes by going deep first. If you also need the shortest path, switch to BFS. For pure reachability, DFS is simpler.

05

Real-World Graph Applications

Graphs model virtually any network of relationships. From your GPS to your social media feed, graph algorithms power the technologies you use every day.

🗺️

Maps & Navigation

Google Maps uses Dijkstra's algorithm on a weighted graph of roads to find shortest routes.

👥

Social Networks

Facebook, LinkedIn — users are vertices; friendships/connections are edges. BFS finds friend-of-friend suggestions.

🌐

Web Crawlers

Search engines use BFS/DFS to traverse the web graph (pages = nodes, hyperlinks = edges).

✈️

Flight Planning

Airports are nodes; routes are weighted edges. Shortest path algorithms minimise flight time and fuel.

📦

Package Delivery

Logistics companies (FedEx, UPS) optimise delivery routes using graph traversal and minimum spanning trees.

🎬

Recommendations

Netflix and Spotify build collaborative filtering graphs to suggest content based on user behaviour patterns.

🔗

Computer Networks

Routers and switches form a graph. Routing protocols (OSPF, BGP) use shortest-path algorithms.

🧬

Bioinformatics

Protein interaction networks, gene regulatory networks, and phylogenetic trees are all modelled as graphs.

Quick Check

Which graph algorithm would you use to find the shortest driving route between two cities, and why?

Answer: Dijkstra's Algorithm (or A* for heuristic-guided search)

Roads are a weighted graph where edge weights represent distance or travel time. BFS finds shortest path only in unweighted graphs. Dijkstra's handles non-negative weights and is the standard choice for navigation systems.

06

Graph Examples & Traversal Traces

The diagrams below show the same 4-node graph traversed by BFS and DFS, making the difference in exploration order immediately visible.

Traversal Traces on the Square Graph (starting from A)

BFS Order: A → B → C → D — visits both A's neighbours (B, C) before going deeper to D.
DFS Order: A → B → D → C — dives deep through B → D first, then backtracks to reach C.

Practice: Trace the Path

In the square graph (A-B-C-D), what is the BFS order if you start from node B? Assume neighbours are visited in alphabetical order.

Answer: B → A → D → C

Starting at B, BFS enqueues its neighbours A and D first (level 1). Then processes A — its unvisited neighbour is C (level 2). D has no new unvisited neighbours. Final order: B → A → D → C.

07

Practice Exercises

Work through the following problems to solidify your understanding of graphs.

Exercise 1: Define a Graph

In your own words, define a graph and explain the difference between a directed and undirected graph. Give one real-world example of each.

Answer:

A graph is a data structure of vertices (entities) and edges (relationships). Directed: edges have direction, like Twitter follows (A follows B ≠ B follows A). Undirected: edges are bidirectional, like Facebook friendship (if A is friends with B, B is friends with A).

Exercise 2: Identify a Cycle

Given the graph A—B—C—A, does this graph contain a cycle? What is the cycle?

Answer: Yes — cycle is A → B → C → A

A cycle exists because there is a path that starts at A, traverses through B and C, and returns to A without repeating any edge. This makes the graph cyclic.

Exercise 3: BFS vs DFS Choice

Scenario: You want to find the shortest number of hops between two users in a social network. Should you use BFS or DFS? Justify your answer.

Answer: BFS

BFS explores level by level — every node at distance k is found before any node at distance k+1. The first time BFS reaches the target node, it has found the fewest-hop path. DFS does not guarantee this as it dives deep down one branch first.

Exercise 4: Adjacency List

Build an adjacency list for the graph: A—B, A—C, B—D, C—D, D—E. Then perform a BFS starting from A and list the visit order.

Adjacency List:

A: [B, C] | B: [A, D] | C: [A, D] | D: [B, C, E] | E: [D]

BFS from A: Enqueue A → dequeue A, enqueue B,C → dequeue B, enqueue D → dequeue C (D already queued) → dequeue D, enqueue E → dequeue E.

Order: A → B → C → D → E

Exercise 5: Application Design

You're designing a flight booking system. Airports are nodes and direct flight routes are edges with weights representing flight duration. Which algorithm would find the quickest route from City X to City Y? What if you wanted to include stopovers?

Answer: Dijkstra's Algorithm

This is a weighted shortest-path problem. Dijkstra's efficiently finds minimum-weight paths in graphs with non-negative edge weights. For stopovers, the same algorithm applies — it naturally considers multi-hop routes through intermediate airports when they produce a lower total weight.

Exercise 6: Time Complexity

A graph has V = 1000 vertices and E = 4000 edges. What is the time complexity of running BFS on it?

Answer: O(V + E) = O(1000 + 4000) = O(5000) = O(V + E)

BFS visits every vertex once and processes every edge once. With 1000 vertices and 4000 edges, it performs approximately 5000 operations — making it very efficient even at this scale.

08

Quiz & Knowledge Check

Test your understanding of Graph Data Structures. Choose the best answer for each question, then submit.

Algo Infinity Verse

Master Graph Data Structures Nodes · Edges · BFS · DFS · Real-World Applications

Introduction to Graphs

Directed Graph

Undirected Graph

Weighted Graph

Unweighted Graph

Cyclic Graph

Acyclic Graph (DAG)

Graph Representation

Graph Terminology

Key Definitions

Breadth-First Search (BFS)

How BFS Works

BFS Complexity

Depth-First Search (DFS)

How DFS Works

Real-World Graph Applications

Maps & Navigation

Social Networks

Web Crawlers

Flight Planning

Package Delivery

Recommendations

Computer Networks

Bioinformatics

Graph Examples & Traversal Traces

Traversal Traces on the Square Graph (starting from A)

Practice Exercises

Quiz & Knowledge Check