Tracking Visited Nodes — Track visited nodes to avoid cycles (conceptual) - Python

SECTION 1

Historical Context & Motivation

Long before computers existed, mathematicians wrestled with a deceptively simple puzzle: how do you explore every path in a network without getting stuck going in circles? In 1736, the Swiss mathematician Leonhard Euler tackled the famous Königsberg Bridge Problem, asking whether a person could walk across all seven bridges of the city exactly once. His solution laid the groundwork for graph theory — the mathematical study of nodes (points) and edges (connections). Euler's key insight was that you need a systematic way to track where you've already been.

As computer science emerged in the twentieth century, researchers realized that graphs appear everywhere — in road maps, social networks, web pages, and file systems. The algorithms that traverse these structures, such as Depth-First Search (DFS) and Breadth-First Search (BFS), all share a common need: they must remember which nodes have already been visited. Without this bookkeeping, a program can loop forever through a cycle — a path that leads back to a node it already touched.

1736 • Euler's Königsberg Bridges

Euler proves the Königsberg bridge walk is impossible, founding graph theory and highlighting the need to reason about visited paths.

1945 • First Graph Traversal Algorithms

Early computer scientists formalize DFS and BFS, both of which require a visited-tracking mechanism to terminate correctly.

1959 • Dijkstra's Shortest Path

Edsger Dijkstra publishes his shortest-path algorithm, which uses a visited set to guarantee each node is processed at most once.

1990s–Today • Web Crawlers & Social Graphs

Search engines like Google use visited-node tracking to crawl billions of web pages without revisiting the same URL endlessly.

The core question this lesson addresses is straightforward: How do we keep track of which nodes we've already explored so our program doesn't revisit them and loop forever? By the end of this lesson, you'll understand the conceptual pattern behind visited-node tracking and how Python's data structures make it efficient.

SECTION 2

Core Principles & Definitions

Before diving into code, let's establish the key vocabulary. A graph is a collection of nodes (also called vertices) connected by edges. When an edge connects node A to node B and also node B back to node A, the graph is undirected. When edges flow in only one direction, the graph is directed. A cycle occurs when you can follow edges from a node and eventually return to that same node. Cycles are what cause infinite loops in naïve traversals.

Node (Vertex)

A single point in a graph — a city on a map, a user in a social network, or an element in your data structure.

Edge

A connection between two nodes. Edges can be one-way (directed) or two-way (undirected).

Cycle

A path through edges that starts and ends at the same node, such as A → B → C → A. This is what we want to detect and avoid.

Visited Set

A data structure (typically a Python set) that records every node we have already processed. Before visiting a node, we check this set first.

Traversal

The process of systematically exploring every reachable node in a graph, such as DFS (going deep first) or BFS (going wide first).

✦

KEY TAKEAWAY

Think of tracking visited nodes like leaving breadcrumbs in a maze. As you walk through corridors (edges) and reach intersections (nodes), you drop a breadcrumb at each new intersection. If you arrive at an intersection that already has a breadcrumb, you know you've been there before — so you turn around instead of going in circles. In Python, your bag of breadcrumbs is a set(), and "dropping a breadcrumb" means calling visited.add(node).

SECTION 3

Visual Explanation — A Graph with a Cycle

The diagram below shows a small graph with five nodes labeled A through E. Notice that nodes A, B, and D form a cycle: you can travel A → B → D → A endlessly. The green checkmarks represent nodes that have been added to the visited set, while the red × marks the moment we detect we're about to revisit node A and stop.

The numbered arrows show the order of exploration. At step ⑤, node D tries to visit node A again, but A is already in the visited set (shown in green). The algorithm skips this edge, breaking the cycle and preventing an infinite loop.

Without the visited set, the traversal would follow the path A → B → D → A → B → D → A forever. The visited set acts as the program's memory, ensuring each node is processed at most once. This single concept — checking before visiting — is the foundation of every graph traversal algorithm you will encounter in computer science.

SECTION 4

How It Works — The Visited-Set Pattern

The visited-set pattern follows a simple three-step loop that repeats for every node encountered during traversal. Understanding this loop is more important than memorizing any specific algorithm, because the same pattern appears in DFS, BFS, Dijkstra's algorithm, and many more.

The Three-Step Loop

Check: Before processing a node, ask "Is this node already in my visited set?" In Python: if node in visited. If yes, skip it entirely.
Mark: If the node is new, immediately add it to the visited set: visited.add(node). This prevents any future encounter from revisiting it.
Explore: Process the node (print it, store data, etc.) and then look at all its neighbors. For each neighbor, go back to the Check step.

LOOKUP TIME COMPLEXITY

Time per lookup in a set: O(1) average

Python's set uses a hash table internally. This means checking if node in visited takes constant time on average, regardless of how many nodes are already in the set. This is why we use a set instead of a list.

OVERALL SPACE COMPLEXITY

Space for visited set: O(V), where V = number of vertices

In the worst case, every node in the graph gets added to the visited set. If the graph has V vertices, the set requires memory proportional to V.

💡

Why a Set and Not a List?

You could use a Python list and call if node in my_list, but list lookup is O(n) — it checks every element one by one. For a graph with 10,000 nodes, a list could perform up to 10,000 comparisons per check. A set does the same job in roughly one operation. For large graphs, this difference matters enormously.

SECTION 5

Visited Tracking in DFS vs. BFS

The visited-set pattern stays the same whether you use DFS or BFS — only the order in which nodes are explored changes. In Depth-First Search, you dive as deep as possible along one branch before backtracking, typically implemented with a stack or recursion. In Breadth-First Search, you explore all neighbors at the current depth before moving deeper, using a queue. In both cases, the visited set prevents revisiting nodes.

Both DFS (left, amber) and BFS (right, cyan) visit every node exactly once. The circled numbers show the visit order. DFS goes deep into B's subtree before visiting C, while BFS visits both of A's children (B and C) before going deeper. Both algorithms use the same visited-set check to avoid revisiting nodes.

Feature	DFS	BFS
Data structure used	Stack (or recursion)	Queue
Exploration strategy	Go deep, then backtrack	Go wide, layer by layer
Uses visited set?	Yes	Yes
When to mark visited	When popping from stack (or entering recursion)	When adding to the queue (before processing)

DFS vs. BFS — both rely on visited tracking

SECTION 6

Worked Example — DFS with a Visited Set in Python

Let's trace through a complete Python example. We have a graph represented as an adjacency dictionary — each key is a node, and its value is a list of neighboring nodes. The graph contains a cycle: 0 → 1 → 3 → 0. Our goal is to visit every node exactly once using DFS.

DFS Traversal Avoiding Cycles

1
Step 1 — Define the Graph

We represent the graph as a Python dictionary. Each key maps to its neighbors:graph = { 0: [1, 2], 1: [0, 3], 2: [0], 3: [1, 4], 4: [3] }Notice that node 1 lists node 0 as a neighbor and vice versa. This creates a cycle.

Graph has 5 nodes and includes the cycle 0 → 1 → 0.
2
Step 2 — Initialize the Visited Set and Start DFS

We create an empty set and define our DFS function:visited = set() def dfs(node): if node in visited: # CHECK return visited.add(node) # MARK print(node) # EXPLORE for neighbor in graph[node]: dfs(neighbor)The function follows the Check → Mark → Explore pattern we described earlier.

The function will recursively visit neighbors, skipping any already in visited.
3
Step 3 — Trace the Execution Starting at Node 0

We call dfs(0). Here's what happens at each recursive call: • dfs(0): 0 not in visited → add 0, print 0. Visit neighbors [1, 2]. • dfs(1): 1 not in visited → add 1, print 1. Visit neighbors [0, 3]. • dfs(0): 0 IS in visited → return immediately (cycle avoided!). • dfs(3): 3 not in visited → add 3, print 3. Visit neighbors [1, 4]. • dfs(1): 1 IS in visited → return immediately. • dfs(4): 4 not in visited → add 4, print 4. Neighbors [3] → already visited. • Back to dfs(0)'s second neighbor: dfs(2): 2 not in visited → add 2, print 2.

Output: 0, 1, 3, 4, 2 — every node printed exactly once.
4
Step 4 — Verify the Visited Set

After DFS completes:print(visited) # {0, 1, 2, 3, 4} All five nodes are in the set. The cycle 0 → 1 → 0 was encountered but did not cause an infinite loop because the visited check returned early.

visited = {0, 1, 2, 3, 4} — traversal complete, no infinite loops.

SECTION 7

Strengths & Limitations of Visited Tracking

Tracking visited nodes is fundamental and nearly universal, but it does have tradeoffs. Understanding when it works well and when modifications are needed will help you make smart design decisions.

Strengths	Limitations
Prevents infinite loops caused by cycles — the most common bug in graph traversal.	Uses O(V) extra memory, which can be significant for very large graphs with millions of nodes.
Guarantees each node is processed at most once, making the algorithm efficient.	Once a node is marked visited, you cannot revisit it — this can be a problem if you need to find all possible paths.
Works identically for DFS, BFS, and many other graph algorithms.	For some problems (like finding shortest paths with weights), you need more nuanced tracking than a simple visited boolean.
Python sets provide O(1) average-time lookups, so the overhead is minimal.	Nodes must be hashable to be stored in a set. Complex objects may need a custom __hash__ method.

Visited set strengths vs. limitations

⚠

WHEN TO MODIFY THE PATTERN

The basic visited set is perfect for the question "Can I reach node X from node Y?" But if you need to find all paths between two nodes, you'll need to un-visit nodes during backtracking — a technique called backtracking with visited removal. Think of it like picking up your breadcrumbs as you retrace your steps so you can explore alternate routes.

SECTION 8

Connection to Advanced Graph Concepts

The visited-set pattern you've learned in this lesson is a stepping stone to more sophisticated techniques. As problems grow more complex, the simple boolean "visited or not" evolves into richer state tracking. The table below shows how this concept scales.

Basic Concept	Advanced Version	What Changes
Visited set (True/False)	Three-color marking (White/Gray/Black)	Instead of just visited/unvisited, nodes are WHITE (undiscovered), GRAY (in progress), or BLACK (fully explored). This helps detect back-edges for cycle detection in directed graphs.
Simple DFS/BFS	Dijkstra's / A* Search	Instead of just tracking if a node is visited, the algorithm also tracks the shortest known distance to each node.
Single visited set	Topological Sort	Uses visited tracking to process nodes in dependency order — critical for task scheduling and build systems.
Skip if visited	Dynamic Programming on Graphs (Memoization)	Instead of just marking visited, the algorithm caches computed results for each node to avoid redundant work.

From basic visited tracking to advanced graph algorithms

Every entry in the "Advanced Version" column still relies on the same fundamental idea: remember what you've already processed so you don't do it again. As you continue your computer science journey, you'll see this pattern appear in courses on algorithms, artificial intelligence, and even database query optimization. Mastering the basic visited set now gives you a solid mental model for all of these.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why a graph traversal without a visited set could run forever. What specific graph structure causes this problem?

Show answer

Without a visited set, a traversal has no memory of which nodes it has already processed. If the graph contains a cycle — a path that loops back to a previously encountered node — the algorithm will follow that loop endlessly. For example, in a graph where A connects to B and B connects back to A, the traversal would alternate A → B → A → B → A forever. The visited set solves this by recording each node when it is first encountered, so the algorithm can check "have I been here before?" and skip nodes accordingly.

Question 2: BASIC CALCULATION

Given the graph graph = {1: [2, 3], 2: [1], 3: [1, 4], 4: [3]}, trace through a DFS starting at node 1. Write the contents of the visited set after each recursive call and list the final print order.

Show answer

Starting at node 1: visited = {1}, print 1. Visit neighbor 2: visited = {1, 2}, print 2. Neighbor of 2 is [1], but 1 is already visited — skip. Backtrack to node 1's next neighbor, 3: visited = {1, 2, 3}, print 3. Neighbor of 3 is [1, 4]; 1 is visited — skip. Visit 4: visited = {1, 2, 3, 4}, print 4. Neighbor of 4 is [3], already visited — skip. Final print order: 1, 2, 3, 4. The final visited set is {1, 2, 3, 4}. No node was printed more than once thanks to the visited check.

Question 3: INTERMEDIATE

A student writes the following BFS code but forgets to add the visited check. Explain what happens when this code runs on a graph with a cycle, and fix the bug:


from collections import deque
def bfs(graph, start):
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            queue.append(neighbor)

Show answer

Without a visited set, every neighbor gets added to the queue each time its parent is processed. If nodes A and B are connected to each other, A adds B to the queue, then B adds A to the queue, then A adds B again — the queue grows without bound and the program runs forever (or until it crashes from memory exhaustion). The fix is to add a visited set and check it before enqueuing:


def bfs(graph, start):
    queue = deque([start])
    visited = {start}         # Mark start as visited
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:   # CHECK
                visited.add(neighbor)     # MARK
                queue.append(neighbor)

Notice that in BFS, we mark nodes as visited when we add them to the queue (not when we dequeue them) to prevent duplicates from entering the queue.

Question 4: APPLIED

Imagine you're building a web crawler that starts at a homepage and follows every hyperlink it finds. The web has cycles (page A links to page B, which links back to page A). Design a high-level algorithm using a visited set that crawls at most 1000 unique pages. What data structure would you use for the visited set and why?

Show answer

You would use BFS with a visited set of URLs (strings). Since URLs are immutable strings, they are hashable and work perfectly as set elements. The algorithm: (1) Initialize a queue with the homepage URL and a visited set containing it. (2) While the queue is not empty and len(visited) < 1000: dequeue a URL, download the page, extract all hyperlinks, and for each link not in visited, add it to both visited and the queue. (3) Stop when the queue is empty or 1000 pages have been visited. A Python set is ideal because checking url in visited is O(1) on average, whereas a list would require O(n) time per lookup — impractical when tracking thousands of URLs.

Question 5: CRITICAL THINKING

Consider a scenario where you need to find ALL possible paths from node A to node E in a graph (not just one path). Explain why the standard visited-set approach fails for this problem and propose a modification. How does this modified approach still prevent infinite loops while allowing nodes to be revisited across different paths?

Show answer

The standard visited set permanently marks a node, preventing it from appearing in more than one path. If node C is on path A→B→C→E, it gets marked visited. Later, when the algorithm tries to explore path A→D→C→E, it skips C because it's already visited — missing a valid path. The modification is backtracking: instead of permanently marking nodes, you add a node to visited when you enter it and remove it when you backtrack. This way, a node is only "visited" for the duration of the current path being explored. Infinite loops are still prevented because within any single path, each node appears at most once (the visited set blocks re-entry). The code change is simple: after the recursive DFS call on a neighbor returns, call visited.remove(node). This technique trades efficiency for completeness — it explores exponentially more paths but guarantees all valid routes are found.

SUMMARY

Lesson Summary

Summary

Graph traversal algorithms like DFS and BFS rely on a visited set to avoid infinite loops caused by cycles in graphs. The pattern is elegant in its simplicity: before processing any node, check if it's already been visited; if not, mark it by adding it to the set, then explore its neighbors. Python's set data structure is ideal for this because it provides O(1) average-time lookups, making the check operation extremely fast even for large graphs.

This pattern extends far beyond basic traversal. It forms the foundation for Dijkstra's shortest path algorithm, topological sorting, web crawlers, and many more advanced techniques. Remember: the visited set is like leaving breadcrumbs in a maze — it's your program's memory of where it's been, and it's what keeps a simple exploration from becoming an endless journey.