Data Structures - lesson 6 | HackIndia Skills

Data Structures - lesson 6 | HackIndia Skills | HackIndia

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

Graphs without fear

One idea

When it is a graph

Pick the pattern

Common mistake

BFS shortest path

Write interview notes

Directed or undirected

Do this now

Quick check