Graphs Explained, Mazes, Maps and Social Networks

Lesson by Adnan, computer science lecturer  ·  aitrendblend editorial team  ·  Computer Science Education  ·  October 2026  ·  Reading time about 22 minutes

Graphs Explained
Mazes, Maps and Networks

Who this lesson is for and how to use it

This is the seventh lesson in our Computer Science Education series. The data structures lesson ended by promising graphs, and this lesson uses both structures students met there. Breadth first search runs on a queue and depth first search on a stack, so students will see those two simple rules turn into two very different ways of exploring. The internet lesson already showed one graph algorithm, Dijkstra’s method for routing packets, and this lesson fills in the ideas underneath it.

The material suits grades nine to twelve and first year college students. No coding is needed for the labs, and the Python code at the end builds every algorithm from scratch. The bridge puzzle in Lab 3 also works brilliantly on paper, which makes this lesson a good choice for classrooms with limited computers.

Learning objectives

After three periods, a student should be able to do the following five things without notes.

1. Define a graph using the words node, edge, degree and path, and give three real examples.
2. Represent a small graph as both an adjacency list and an adjacency matrix.
3. Explain how breadth first search and depth first search explore, and which data structure each uses.
4. Explain why breadth first search finds shortest paths in a maze or friendship network.
5. Use the odd degree rule to decide whether a walk can cross every edge exactly once.

What a graph is

In everyday language a graph is a chart with axes. In computer science it means something different. A graph is a collection of nodes, also called vertices, joined by edges. The nodes can be anything, cities, people, web pages, computers or squares on a game board. The edges show which pairs are connected, roads, friendships, links, cables or legal moves. The number of edges touching a node is its degree, and a sequence of edges leading from one node to another is a path.

Some graphs have edges that work both ways, like a friendship or a two way road. These are called undirected. Others have one way edges, like following someone on a social app or a one way street. These are called directed. Some edges carry a number, such as the length of a road or the delay on a cable, and the graph is then called weighted. The routing lab in our internet lesson used a weighted graph, which is why it needed Dijkstra’s algorithm. This lesson mostly uses unweighted graphs, where every step costs the same.

Storing a graph in a computer

A computer cannot see a drawing, so it stores a graph as data. The two classic ways are the adjacency list, which keeps, for each node, a list of its neighbours, and the adjacency matrix, a grid with a 1 wherever two nodes are joined and a 0 elsewhere. Lists use little memory when most nodes have only a few connections, which is true of nearly all real networks. Matrices make it instant to check whether two particular nodes are connected, but they need a cell for every possible pair. Click two nodes in the lab below to join or separate them and watch both representations update together.

Notice that every new edge flips two cells of the matrix, because a friendship between A and C is also a friendship between C and A. That symmetry is the fingerprint of an undirected graph. A directed graph, such as who follows whom, would change only one cell.

The puzzle that started it all

In the 1700s the city of Königsberg, now Kaliningrad in Russia, sat on a river with two islands, joined to the banks and to each other by seven bridges. Residents liked to ask whether anyone could take a walk that crossed every bridge exactly once. Nobody could, but nobody could prove it was impossible either. In 1736 the Swiss mathematician Leonhard Euler did, and in doing so he invented a new branch of mathematics.

Euler’s insight was to throw away everything that did not matter, the shapes of the land, the lengths of the bridges, the streets, and keep only which pieces of land were joined by which bridges. That stripped down picture is a graph. Try the walk yourself below, then reveal his argument.

Here is the argument, and it is simple enough for any student. Every time a walker enters a piece of land, they must also leave it, using one bridge in and one bridge out. So every piece of land in the middle of the walk uses up its bridges in pairs, which means it needs an even number of them. Only the starting land and the finishing land can have an odd number. In Königsberg the island had five bridges and the other three pieces of land had three each. Four odd pieces of land is two too many, so the walk is impossible, no matter how cleverly you try. Add an eighth bridge between the two banks and only two pieces of land stay odd, and suddenly the walk exists.

Searching a graph, breadth first and depth first

Most questions about graphs start with a search. Can I get from here to there? What is the shortest route? Who can I reach within three steps? There are two fundamental ways to explore, and the difference between them comes straight from the data structures lesson.

Breadth first search, usually shortened to BFS, keeps a queue of places to visit. It starts at the beginning, adds all its neighbours to the back of the queue, then takes the oldest item from the front and repeats. Because the queue is first in, first out, BFS finishes everything at distance one before anything at distance two, and so on, spreading outward in rings. Edward Moore described it in 1959 as a way to find the shortest path through a maze, and Konrad Zuse had sketched a similar method in 1945, though his work was not published until much later.

Depth first search, or DFS, keeps a stack instead. It always continues from the most recently discovered place, so it dives down one corridor as far as it can go before backing up to try another. A version of this idea for solving mazes by hand was described in the 1800s by the French engineer Charles Pierre Trémaux, who marked passages with chalk as he explored. DFS is excellent for questions like whether any route exists, but the route it finds first is often not the shortest.

Watch the two patterns. BFS floods outward evenly, like water poured on the floor, and the first time it touches the goal it has found the shortest possible route. DFS snakes off in one direction, hugs walls and doubles back, and its route can be dramatically longer. Draw a wall with a single gap and run both again. Games use descendants of BFS, such as the A star algorithm, to move characters around obstacles, and map apps use Dijkstra’s algorithm, which is BFS generalized to roads of different lengths.

A queue makes you explore fairly, ring by ring. A stack makes you explore boldly, one corridor at a time. Same graph, same data, two completely different journeys.From this lesson, period two

Social networks, friends of friends

A social network is a graph where people are nodes and friendships are edges. Running BFS from one person reveals rings of distance. Distance one is their friends. Distance two is friends of friends, and the ones who are not already friends are exactly the people a social app is likely to suggest. Real systems add many signals, such as how many mutual friends you share, but the distance two idea sits at the centre. Click any person below to see their rings.

In 1967 the social psychologist Stanley Milgram asked people in the American Midwest to pass a letter toward a stranger in Boston using only personal acquaintances. The letters that arrived took around six steps on average, which gave the world the phrase six degrees of separation. Much larger studies on online networks since then have found even shorter typical distances. Networks like these are called small worlds, because although they are enormous, almost everyone is only a few steps from everyone else, and BFS can measure it.

Graphs everywhere

Once students learn to see graphs, they find them everywhere. The internet is a graph of routers joined by cables, as our internet lesson showed. The World Wide Web is a directed graph of pages joined by links, and in 1998 Google’s founders Larry Page and Sergey Brin ranked pages by analysing that graph, reasoning that a page linked from many important pages is probably important itself. Electricity grids, airline routes, molecules in chemistry and dependencies between school subjects can all be modelled as graphs.

Graphs also appear inside modern AI. Graph neural networks pass information along edges so that each node learns from its neighbours, an approach researchers use for molecules, road traffic and medical images. Students curious about where this leads can explore our graph neural networks section, and our article on detecting GPS spoofing with a network of reference stations shows a real research problem solved by treating sensors as nodes in a graph.

Misconceptions students bring to class

• A graph is a chart with axes. In computer science a graph means nodes and edges. Drawing position does not matter, only the connections.
• BFS and DFS find the same route. Both find a route if one exists, but only BFS guarantees the shortest one when every step costs the same.
• Shortest means fewest steps in every case. On a weighted graph, such as roads of different lengths, fewest steps and shortest distance can differ, which is why Dijkstra’s algorithm exists.
• The Königsberg walk just needs a clever route. Euler proved no route exists. Trying harder cannot beat a counting argument.
• Social apps read minds. Most friend suggestions come from graph structure, especially friends of friends and mutual connections.

Where this lesson simplifies the truth

The maze lab uses a grid where every move costs one step and only four directions are allowed. Real maps have roads of different lengths, so map apps use weighted algorithms such as Dijkstra and A star, which add a sense of direction toward the goal. The friend network is tiny and undirected, while real social graphs have billions of nodes, one way follows and many edge types, and they use far more signals than distance alone to recommend people.

The Königsberg lab follows the classic simplified map and treats the two islands as Euler did. Euler’s full result covers any graph and also explains when a walk can end where it started. None of these refinements change the core ideas students meet here.

Bringing it all together

The main achievement of this lesson is a new way of seeing. Students now recognize that maps, mazes, friendships, web links and networks of computers share one underlying shape, things joined by connections, and that a small set of algorithms answers questions about all of them. They have stored a graph two ways, walked it ring by ring with a queue and corridor by corridor with a stack, and used a counting argument to prove a famous puzzle impossible.

The conceptual shift is from solving one problem at a time to recognizing a familiar structure underneath many problems. Euler did not just solve a puzzle about bridges. He showed that the right abstraction makes hard questions easy, a lesson that applies far beyond graphs.

The ideas connect to the whole series. Routing on the internet is a shortest path problem. Algorithms and data structures from the previous two lessons are the tools that make graph search fast. Even the neural networks from our AI lesson are graphs of artificial neurons, and graph neural networks apply the same thinking to data that is itself a network.

The lesson has honest limits. It leaves out weighted shortest paths in detail, directed graph algorithms, spanning trees and graph colouring, each of which deserves its own lesson. Teachers with stronger classes can extend period three by asking students to implement BFS on the friend network in Python, and teachers without computers can teach almost everything here with a map drawn on the board, string between desks and the human BFS activity.

A natural next lesson is programming itself, putting these ideas into a first complete project. For now, the students who wondered how a map app finds a route can explain it, and they know a three hundred year old proof that some walks simply cannot be done.

Companion Python code for the classroom

The program below implements the main ideas in plain Python. It stores a friendship graph as an adjacency list, runs breadth first search to find distances, shortest chains and friend suggestions, runs depth first search for comparison, solves a small text maze with BFS, and checks Euler’s odd degree rule for the bridges of Königsberg with and without an extra bridge.

# Graphs, companion code for the aitrendblend lesson
# Runs on any Python 3 installation. No extra libraries needed.
from collections import deque

# Part 1. A graph stored as an adjacency list
FRIENDS = {
    "Ayesha": ["Bilal", "Sara", "Hamza"],
    "Bilal": ["Ayesha", "Omar"],
    "Sara": ["Ayesha", "Hina", "Zara"],
    "Hamza": ["Ayesha", "Zara"],
    "Omar": ["Bilal", "Noor"],
    "Hina": ["Sara"],
    "Zara": ["Sara", "Hamza", "Imran"],
    "Noor": ["Omar"],
    "Imran": ["Zara"],
}


def degree(graph, v):
    return len(graph[v])


# Part 2. Breadth first search, exploring in rings
def bfs_levels(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()               # a queue gives the ring by ring order
        for w in graph[v]:
            if w not in dist:
                dist[w] = dist[v] + 1
                queue.append(w)
    return dist


def shortest_path(graph, start, goal):
    prev = {start: None}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        if v == goal:
            break
        for w in graph[v]:
            if w not in prev:
                prev[w] = v
                queue.append(w)
    path, v = [], goal
    while v is not None:
        path.append(v)
        v = prev.get(v)
    return path[::-1] if path[-1] == start else []


def friend_suggestions(graph, person):
    """Friends of friends who are not already friends, the classic suggestion rule."""
    d = bfs_levels(graph, person)
    return sorted(p for p, k in d.items() if k == 2)


# Part 3. Depth first search, going deep before going wide
def dfs_order(graph, start):
    seen, order, stack = set(), [], [start]
    while stack:
        v = stack.pop()                   # a stack gives the deep first order
        if v in seen:
            continue
        seen.add(v)
        order.append(v)
        stack.extend(reversed(graph[v]))
    return order


# Part 4. Solving a maze with BFS on a grid
MAZE = [
    "S..#....",
    ".#.#.##.",
    ".#...#..",
    ".####.#.",
    "......#E",
]


def solve_maze(maze):
    rows, cols = len(maze), len(maze[0])
    find = lambda ch: next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == ch)
    start, end = find("S"), find("E")
    prev, queue = {start: None}, deque([start])
    while queue:
        r, c = queue.popleft()
        if (r, c) == end:
            break
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] != "#" and (nr, nc) not in prev:
                prev[(nr, nc)] = (r, c)
                queue.append((nr, nc))
    steps, cell = 0, end
    while prev[cell] is not None:
        cell, steps = prev[cell], steps + 1
    return steps, len(prev)


# Part 5. Euler and the bridges of Königsberg
BRIDGES = [("North", "Island"), ("North", "Island"), ("South", "Island"), ("South", "Island"),
           ("North", "East"), ("South", "East"), ("Island", "East")]


def euler_walk_possible(edges):
    deg = {}
    for a, b in edges:
        deg[a] = deg.get(a, 0) + 1
        deg[b] = deg.get(b, 0) + 1
    odd = [v for v, d in deg.items() if d % 2]
    return len(odd) in (0, 2), deg


# Smoke test
if __name__ == "__main__":
    print("Ayesha has", degree(FRIENDS, "Ayesha"), "friends")
    levels = bfs_levels(FRIENDS, "Ayesha")
    print("Distances from Ayesha:", levels)
    print("Shortest chain Ayesha to Noor:", " > ".join(shortest_path(FRIENDS, "Ayesha", "Noor")))
    print("Friend suggestions for Ayesha:", friend_suggestions(FRIENDS, "Ayesha"))
    print("DFS order from Ayesha:", dfs_order(FRIENDS, "Ayesha"))

    steps, explored = solve_maze(MAZE)
    print(f"\nMaze solved in {steps} moves after exploring {explored} cells")

    ok, deg = euler_walk_possible(BRIDGES)
    print("\nKönigsberg degrees:", deg, "| walk possible:", ok)
    ok2, _ = euler_walk_possible(BRIDGES + [("North", "South")])
    print("With one extra bridge:", ok2)

    assert levels["Noor"] == 3 and friend_suggestions(FRIENDS, "Ayesha") == ["Hina", "Omar", "Zara"]
    assert not ok and ok2
    assert steps == 15
    print("\nAll checks passed.")

When you run it, Noor should be three steps from Ayesha, the friend suggestions for Ayesha should be Hina, Omar and Zara, the maze should be solved in 15 moves, Königsberg should come out impossible until the extra bridge is added, and the final line should report that all checks passed. A good extension task is to add a function that counts how many people are within two steps of each person and find the best connected person in the network.

Check your understanding

Six questions cover the whole lesson. Choose an answer for each and press Check answers to see which were right, with a short explanation for each.

Frequently asked questions

Related reading on aitrendblend