Data Structures - lesson 6 | HackIndia Skills

Key point

One idea

A graph is just nodes plus edges. Most interview graph problems ask one of three things: can I reach it, what is the shortest unweighted path, or what order is valid.

When it is a graph

Use a graph when items connect to other items in no fixed parent-child shape. Think friends in a college app, cities connected by trains, courses with prerequisites, or UPI transactions between accounts.

If each item has at most one parent, it may be a tree. If each item can connect to many others both ways or one way, think graph.

Your to-do

Pick the pattern

Do each one yourself, then tap it to tick it off. The ticks are only a checklist for you: they are not marked or scored.

Use an adjacency list for most interview problems because it stores only real edges.
Use BFS when all edges have equal cost and you need the fewest steps.
Use DFS when you need to explore a full component, detect a cycle, or mark visited nodes.
Use topological sort when tasks have prerequisites and you need a valid order.
Use Dijkstra only when edges have different positive costs. Do not use it for simple unweighted shortest path.

0 of 5 done

Common mistake

Beginners often forget the visited set. Then code loops forever on cycles like A to B and B to A.

Another mistake is using an adjacency matrix for sparse graphs. A matrix is easy to see, but it costs n squared space. For interviews, adjacency lists are usually the safer default.

Example

BFS shortest path

This finds the fewest edges from a start node to a target node in an unweighted graph. Add a file like graphs/bfs_shortest_path.py to your repo.

Notice the queue and visited set. The distance increases by 1 each time you move across an edge.

from collections import deque

def shortest_path_edges(graph, start, target):
    if start == target:
        return 0

    q = deque([(start, 0)])
    visited = {start}

    while q:
        node, dist = q.popleft()

        for nei in graph.get(node, []):
            if nei in visited:
                continue
            if nei == target:
                return dist + 1
            visited.add(nei)
            q.append((nei, dist + 1))

    return -1


def test_shortest_path_edges():
    graph = {
        "hostel": ["canteen", "library"],
        "canteen": ["hostel", "lab"],
        "library": ["hostel", "lab"],
        "lab": ["canteen", "library", "gate"],
        "gate": ["lab"]
    }

    assert shortest_path_edges(graph, "hostel", "gate") == 3
    assert shortest_path_edges(graph, "hostel", "hostel") == 0
    assert shortest_path_edges(graph, "gate", "unknown") == -1

Tip

Write interview notes

For every graph file, add a short note beside the code. Keep it practical: representation, algorithm, time cost, space cost, and why you did not pick another option.

Example note: adjacency list because the graph is sparse. BFS because edges are unweighted and we need minimum number of hops. Time O(V + E). Space O(V).

Directed or undirected

Ask this early. A follow relation, course prerequisite, or payment flow is directed. A friendship, road with both-way travel, or cable connection is often undirected.

In code, directed means add one edge: a to b. Undirected means add both: a to b and b to a.