Graph Algorithms: Networks and Connections

The Problem: When There Is No Direct Train

Suppose you are in Delhi and you want to reach Bengaluru by train. If you search and find there is no single train that runs directly between the two cities, you now face a real planning problem: which chain of trains gets you there using the fewest changes? You could go Delhi to Bhopal, Bhopal to Hyderabad, Hyderabad to Bengaluru. Or maybe some other combination is shorter. If the network only had four or five cities, you could work this out by staring at a map. But India's rail network connects thousands of stations, and no human can scan that by eye and guarantee the answer is the best one.

This is exactly the kind of problem graph algorithms are built to solve. Before we can solve it though, we need a precise way to describe "a bunch of cities connected by routes" as something a computer can work with. That precise structure is called a graph, and by the end of this chapter you will have two systematic algorithms — one that finds the fewest-changes route, and one that explores a network as deeply as possible before backtracking.

What Exactly Is a Graph?

A graph is a collection of things, and the connections between some pairs of those things. That is the whole idea — everything else is vocabulary for describing it precisely.

• Each "thing" (a city, a person, a webpage, a router) is called a vertex or a node. The plural of vertex is vertices.
• Each connection between two vertices is called an edge.

A train route between Delhi and Bhopal is an edge connecting the vertices Delhi and Bhopal. A graph is simply the set of all vertices together with the set of all edges — nothing more.

Graphs come in a few important flavours, and mixing them up is where most beginners go wrong:

• Undirected vs directed. If a train route can be used in both directions — you can travel Delhi to Bhopal and Bhopal to Delhi on the same line — the edge is undirected. But an Instagram "follow" is different: if you follow a celebrity, it does not mean the celebrity follows you back. That relationship needs a directed edge, drawn as an arrow, pointing only from you to the celebrity. A one-way street is another directed edge in real life. In this chapter we will work with undirected graphs — every route can be travelled in either direction — because that is the simpler case to build your foundation on.
• Weighted vs unweighted. If every edge is treated as "equally costly" — we only care whether a route exists, not how long or expensive it is — the graph is unweighted. If each edge carries a number (a distance, a fare, a travel time), the graph is weighted. We will build our main network as unweighted first, because it lets us answer "fewest changes" cleanly, and later see why weighted graphs need a different kind of thinking.

One more piece of vocabulary you will use constantly: the degree of a vertex is the number of edges touching it — in our train example, the degree of a city is the number of other cities it has a direct train to.

Our Working Example: A Small Rail Network

To make every algorithm in this chapter concrete, we will use one small, fixed network of seven cities for the rest of the chapter, with these direct train routes (edges):

• Delhi – Bhopal
• Delhi – Jaipur
• Bhopal – Hyderabad
• Bhopal – Mumbai
• Jaipur – Mumbai
• Hyderabad – Bengaluru
• Mumbai – Pune

That is 7 vertices and 7 edges. Here is that network drawn out, with each city coloured by how many train-changes it takes to reach it starting from Delhi — the very question BFS answers, which we will compute properly in a moment.

Look closely at the shape of this network before we touch any algorithm. It has 7 vertices and 7 edges. A network that connects 7 cities using the fewest possible routes — a tree, with no redundant connections — would need exactly 6 edges. We have one extra edge, which means this network contains exactly one cycle: Delhi → Bhopal → Mumbai → Jaipur → Delhi. Every other part of the network branches out tree-like from that cycle. Also notice the network is connected — there is some sequence of trains between every pair of cities. Not every graph has this property; a graph can easily split into two or more separate "islands" with no route between them at all.

Reading the Network: Adjacency List and Adjacency Matrix

Before an algorithm can search a graph, the graph has to live inside the computer's memory in some form. There are two standard ways to store it, and you should be comfortable moving between both.

The first is an adjacency list: for every vertex, keep a list of its direct neighbours. In Python this is naturally a dictionary mapping each city to a list of cities it connects to:

graph = {
    "Delhi":     ["Bhopal", "Jaipur"],
    "Bhopal":    ["Delhi", "Hyderabad", "Mumbai"],
    "Jaipur":    ["Delhi", "Mumbai"],
    "Hyderabad": ["Bhopal", "Bengaluru"],
    "Mumbai":    ["Bhopal", "Jaipur", "Pune"],
    "Bengaluru": ["Hyderabad"],
    "Pune":      ["Mumbai"],
}

Each city appears in its neighbour's list too, because our routes are undirected — "Delhi connects to Bhopal" and "Bhopal connects to Delhi" describe the very same edge, so it is stored on both sides. This is the representation most real search algorithms use, because checking "who are city X's neighbours" takes one dictionary lookup, and most real-world graphs are sparse — each vertex connects to only a handful of others, not to everyone.

The second representation is an adjacency matrix: a grid with one row and one column per vertex, where a 1 means an edge exists between that row's city and that column's city, and 0 means it does not.

cities = ["Bengaluru", "Bhopal", "Delhi", "Hyderabad", "Jaipur", "Mumbai", "Pune"]

#              Blr Bpl Del Hyd Jai Mum Pun
matrix = [
    [0,  0,  0,  1,  0,  0,  0],   # Bengaluru
    [0,  0,  1,  1,  0,  1,  0],   # Bhopal
    [0,  1,  0,  0,  1,  0,  0],   # Delhi
    [1,  1,  0,  0,  0,  0,  0],   # Hyderabad
    [0,  0,  1,  0,  0,  1,  0],   # Jaipur
    [0,  1,  0,  0,  1,  0,  1],   # Mumbai
    [0,  0,  0,  0,  0,  1,  0],   # Pune
]

Two things to verify whenever you build a matrix like this: it should be symmetric for an undirected graph — row Bhopal, column Delhi is 1, and row Delhi, column Bhopal is also 1, because it is the same edge seen from both sides. And every row's 1s should equal that city's degree. We can check both the matrix and the handshake idea from earlier — that the sum of every vertex's degree equals twice the number of edges, since each edge is counted once from each end — directly in code:

degree = {city: sum(row) for city, row in zip(cities, matrix)}
print(degree)
# {'Bengaluru': 1, 'Bhopal': 3, 'Delhi': 2, 'Hyderabad': 2,
#  'Jaipur': 2, 'Mumbai': 3, 'Pune': 1}

print(sum(degree.values()), "should equal", 2 * 7)
# 14 should equal 14

That check passing is a genuinely useful habit: if you ever build a graph from real data and the degree sum comes out odd, you have a bug in how you are reading the edges — it is mathematically impossible for a correctly built undirected graph to have an odd degree sum, since every edge always contributes exactly 2 to the total.

Adjacency matrices are simple to reason about and make "is there a direct edge between X and Y" a single lookup, but they waste memory when the graph is sparse — our matrix has 49 cells but only 14 of them are 1. For a graph of, say, 8,000 railway stations where each station connects to only 3–4 others, a matrix would need 64 million cells to store roughly 30,000 real connections. That is why adjacency lists are almost always preferred for real networks, and why we will use the adjacency list from here on.

Paths and Cycles

A path is a sequence of vertices where each consecutive pair is connected by an edge, and no vertex repeats. Delhi → Bhopal → Hyderabad → Bengaluru is a path of length 3 (three edges, four cities) in our network — every consecutive pair really is a direct route, and no city appears twice.

A cycle is a path that comes back to where it started, using at least three distinct vertices along the way, with no other repeats. We already spotted ours: Delhi → Bhopal → Mumbai → Jaipur → Delhi. Every step is a real edge, every city except Delhi appears exactly once, and it returns to the start. This is the only cycle in our network, which is why we called it "tree-shaped plus one extra edge" earlier — that extra edge is precisely what creates the cycle.

Why does this distinction matter for algorithms? Because any search that walks a graph has to actively avoid re-visiting vertices, or a cycle would trap it in an infinite loop — Delhi to Bhopal to Mumbai to Jaipur to Delhi to Bhopal to Mumbai… forever. Both algorithms in this chapter solve this the same way: by keeping a record of which vertices have already been visited, and refusing to step into one twice.

Breadth-First Search: Finding the Fewest Changes

Now we can properly answer the question we opened with: starting from Delhi, what is the minimum number of trains you must board to reach each other city? This is exactly what Breadth-First Search (BFS) computes.

The idea is to explore the network in expanding rings, like a drop of ink spreading through water. First look at every city one train away from Delhi. Then, without skipping ahead, look at every new city reachable one more train from those. Then the next ring, and so on — we only move to ring 2 once ring 1 is fully explored. This "explore the nearest unexplored things first" behaviour is enforced with a data structure called a queue, where items are added at the back and removed from the front (first in, first out) — the exact opposite of a stack of plates, where you take from the top.

Here is the full trace, starting from Delhi, using the adjacency list above (each city's neighbours are visited in the order they appear in that list):

1. Start: queue = [Delhi], visited = {Delhi}, hops = {Delhi: 0}.
2. Remove Delhi from the front. Look at its neighbours Bhopal and Jaipur — both new. Mark both visited, set their hop-count to 1, add both to the back of the queue. Queue is now [Bhopal, Jaipur].
3. Remove Bhopal. Its neighbours are Delhi (already visited — skip), Hyderabad (new — hops = 2), Mumbai (new — hops = 2). Queue is now [Jaipur, Hyderabad, Mumbai].
4. Remove Jaipur. Its neighbours are Delhi (visited — skip) and Mumbai. Mumbai was already marked visited in the previous step, so it is skipped here too — this is exactly why we mark a city visited the moment we discover it, not when we later process it, otherwise it could be added to the queue twice. Queue is now [Hyderabad, Mumbai].
5. Remove Hyderabad. Neighbours: Bhopal (visited), Bengaluru (new — hops = 3). Queue is now [Mumbai, Bengaluru].
6. Remove Mumbai. Neighbours: Bhopal (visited), Jaipur (visited), Pune (new — hops = 3). Queue is now [Bengaluru, Pune].
7. Remove Bengaluru. Its only neighbour, Hyderabad, is visited. Nothing new. Queue is now [Pune].
8. Remove Pune. Its only neighbour, Mumbai, is visited. Queue is now empty — BFS is complete.

The final hop-counts are exactly what the diagram above shows: Delhi 0, Bhopal 1, Jaipur 1, Hyderabad 2, Mumbai 2, Bengaluru 3, Pune 3. This is not a coincidence — it is a guarantee. In an unweighted graph, BFS always finds the shortest path (fewest edges) from the start to every other reachable vertex, because it is physically impossible for it to reach a vertex in ring 3 before it has finished discovering every vertex in rings 1 and 2.

Here is the same trace as working code:

from collections import deque

def bfs_hops(graph, start):
    visited = {start}
    hops = {start: 0}
    queue = deque([start])
    order = []
    while queue:
        city = queue.popleft()
        order.append(city)
        for neighbour in graph[city]:
            if neighbour not in visited:
                visited.add(neighbour)
                hops[neighbour] = hops[city] + 1
                queue.append(neighbour)
    return order, hops

order, hops = bfs_hops(graph, "Delhi")
print(order)
print(hops)

Running this prints:

['Delhi', 'Bhopal', 'Jaipur', 'Hyderabad', 'Mumbai', 'Bengaluru', 'Pune']
{'Delhi': 0, 'Bhopal': 1, 'Jaipur': 1, 'Hyderabad': 2, 'Mumbai': 2, 'Bengaluru': 3, 'Pune': 3}

The first line is the order cities were processed (removed from the front of the queue) — matching the trace step by step. The second line is the answer to our original question: to reach Bengaluru from Delhi you need at minimum 3 trains, and one valid route achieving that is Delhi → Bhopal → Hyderabad → Bengaluru.

Depth-First Search: Exploring As Deep As Possible First

Depth-First Search (DFS) asks a completely different question: rather than fanning out evenly in rings, what if you commit to one neighbour, then commit to its first unvisited neighbour, and keep plunging forward as deep as the graph allows — only turning back (backtracking) once you hit a dead end? This is how you would explore a maze by always taking the first available turn and only reversing when you are truly stuck. Where BFS uses a queue, DFS naturally uses a stack (last in, first out) — and the cleanest way to write it in code is with recursion, since each recursive call automatically stacks on top of the one before it.

Tracing DFS from Delhi, using the same adjacency list order:

1. Visit Delhi. Its first unvisited neighbour is Bhopal — go there.
2. Visit Bhopal. Its neighbours are Delhi (visited, skip), Hyderabad (unvisited) — go there.
3. Visit Hyderabad. Neighbours: Bhopal (visited, skip), Bengaluru (unvisited) — go there.
4. Visit Bengaluru. Its only neighbour, Hyderabad, is visited. Dead end — backtrack to Hyderabad, which also has nothing left — backtrack to Bhopal.
5. Back at Bhopal, the next unvisited neighbour is Mumbai — go there.
6. Visit Mumbai. Neighbours: Bhopal (visited), Jaipur (unvisited) — go there.
7. Visit Jaipur. Neighbours: Delhi (visited), Mumbai (visited). Dead end — backtrack to Mumbai.
8. Back at Mumbai, the next unvisited neighbour is Pune — go there.
9. Visit Pune. Its only neighbour, Mumbai, is visited. Dead end — backtrack all the way to Mumbai, then Bhopal, then Delhi.
10. Back at Delhi, the only remaining neighbour, Jaipur, is already visited. Nothing left — DFS is complete.

Full visiting order: Delhi, Bhopal, Hyderabad, Bengaluru, Mumbai, Jaipur, Pune. Notice how different this is from BFS's order — DFS raced straight out to the far edge of the network (Bengaluru, three hops away) before it ever looked at Jaipur, which is only one hop from Delhi. That is the whole personality difference between the two algorithms: BFS is cautious and expands evenly outward; DFS is committed and plunges to the depths before it backs up.

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(start)
    order.append(start)
    for neighbour in graph[start]:
        if neighbour not in visited:
            dfs(graph, neighbour, visited, order)
    return order

print(dfs(graph, "Delhi"))
# ['Delhi', 'Bhopal', 'Hyderabad', 'Bengaluru', 'Mumbai', 'Jaipur', 'Pune']

DFS is the natural choice whenever you don't care about the shortest route and only need to know whether a path exists at all, or whether the whole graph is connected, or need to detect a cycle — all of which it can do in a single pass without ever needing a queue.

A Common Mistake: "BFS Always Finds the Cheapest Route"

Here is a misunderstanding that trips up nearly every student meeting these algorithms for the first time: assuming BFS finds the cheapest path in every graph, including weighted ones. It does not. BFS finds the path with the fewest edges. That is only the same thing as "cheapest" when every edge costs exactly the same, which is precisely the unweighted-graph assumption we relied on throughout this chapter.

Watch what happens the moment edges get different weights. Imagine a small, entirely hypothetical example for this exercise: a courier company has three possible legs between city A and city C, with these prices — A to C directly costs ₹500, while A to B costs ₹100 and B to C costs ₹100.

• Fewest edges: A → C directly. That is 1 edge, and BFS would report this as "shortest."
• Cheapest total: A → B → C. That is 2 edges but only ₹200 total, beating the 1-edge route's ₹500.

BFS, which only counts edges and has no idea that weights even exist, would confidently hand you the more expensive route and call it optimal. For weighted graphs you need a different algorithm — the best-known one is Dijkstra's algorithm, which is BFS's close cousin: it also expands outward from the start, but instead of a plain queue it always expands whichever undiscovered vertex has the lowest total cost so far. You will meet it formally in a later chapter; for now, the important habit is this: before you reach for BFS to find a "shortest path," always ask whether every edge in your graph genuinely costs the same. If it does not, BFS will give you a wrong, overconfident answer rather than an error — which is exactly what makes this mistake dangerous.

Check Your Understanding

Q1. Using the network from this chapter, what is the degree of Bhopal, and which cities is it directly connected to?

Q2. A logistics company wants to move a package from Delhi to Hyderabad. These are hypothetical route charges made up purely for this exercise (not real-world fares): a direct Delhi–Hyderabad flight route costs ₹1,400; the Delhi–Bhopal leg costs ₹500; the Bhopal–Hyderabad leg costs ₹700. Using the idea from the "common mistake" section, is it cheaper to route the package through Bhopal or send it direct — and by how much?

Q3. Using the BFS hop-counts computed earlier in this chapter (Delhi 0, Bhopal/Jaipur 1, Hyderabad/Mumbai 2, Bengaluru/Pune 3), what is the minimum number of trains needed to travel from Delhi to Pune? Name one valid sequence of cities that achieves it.

Q4. Trace DFS starting from Pune instead of Delhi, using the same adjacency list ordering used throughout this chapter. Write out the complete visiting order.

Q5. A classmate says: "BFS always finds the shortest path, so I never need any other pathfinding algorithm." Explain, using the courier example from Q2's idea, exactly when this statement is true and when it breaks down.

Answers

A1. Degree 3. Bhopal is directly connected to Delhi, Hyderabad, and Mumbai.

A2. Via Bhopal: ₹500 + ₹700 = ₹1,200. Direct: ₹1,400. Routing through Bhopal is cheaper by ₹200, even though it uses two edges instead of one — exactly the situation where "fewest edges" and "cheapest" disagree.

A3. 3 trains. One valid sequence: Delhi → Bhopal → Mumbai → Pune (Delhi → Jaipur → Mumbai → Pune also works).

A4. Pune, Mumbai, Bhopal, Delhi, Jaipur, Hyderabad, Bengaluru. (From Pune, the only neighbour is Mumbai; from Mumbai, the first unvisited neighbour alphabetically is Bhopal, not Jaipur or Pune; from Bhopal, Delhi comes before Hyderabad; Delhi then reaches Jaipur; backtracking all the way to Bhopal finally opens up Hyderabad, which leads to Bengaluru.)

A5. The statement is true only when every edge in the graph has equal weight (or the graph is unweighted) — then "fewest edges" and "cheapest" are the same thing, and BFS's guarantee holds exactly. It breaks down the moment edges have different weights, as in the courier example, where the 1-edge direct route (₹1,400) is more expensive than the 2-edge route through Bhopal (₹1,200). In a weighted graph you need an algorithm that accounts for the weights, such as Dijkstra's algorithm, not plain BFS.

Summary

A graph is nothing more than a set of vertices and a set of edges connecting some pairs of them — but that simple structure models an enormous range of real problems, from train networks to social-media follow relationships to road maps. Edges can be undirected or directed, and unweighted or weighted, and these distinctions change which algorithm is the right tool. A graph is stored either as an adjacency list (efficient, and the standard choice for sparse real-world graphs) or an adjacency matrix (simple, with instant edge lookups, but wasteful for sparse graphs); the handshake fact — every vertex's degrees sum to exactly twice the edge count — is a fast sanity check on either representation. Paths visit no vertex twice; cycles are paths that loop back to their start. Breadth-First Search explores outward ring by ring using a queue and is guaranteed to find the route with the fewest edges — which equals the cheapest route only when every edge costs the same. Depth-First Search commits to one direction and plunges as deep as possible using a stack (or recursion) before backtracking, and is the natural tool for questions like "does a path exist at all" or "is this graph connected," rather than "what is the shortest route." Knowing which of the two — or which weighted variant, like Dijkstra's algorithm — a problem actually calls for is the real skill this chapter is building toward.