Relationship maps, organizational structures, dependency networks, and account hierarchies are often described as trees. That description becomes unsafe as soon as the data can contain a back edge, a shared descendant, an accidental self-link, or a relationship that is traversable in both directions. The structure is then a graph. A recursive method written under tree assumptions can revisit the same node indefinitely, exhaust the call stack on deep paths, or admit an unexpectedly wide neighborhood before an outer limit is checked.

This guide defines three correctness contracts for C# graph traversal: register discovered identities in a HashSet, use an explicit Queue for iterative breadth-first traversal, and enforce the maximum node count while each neighbor is being admitted. The search intent is informational and the funnel position is TOFU/MOFU. Useful engineering KPIs include duplicate-node rate, visited-node count, truncation count, response payload size, and traversal failure rate—not an unsupported claim that one algorithm is universally faster.

Why can a relationship graph not be treated as ordinary tree recursion?

If a node can point to an ancestor, itself, or a descendant shared by another path, traversal must be designed around explicit identity and termination rules. Otherwise, execution depth and output volume are controlled by imperfect data rather than by the application contract.

A tree promises one path from its root to each node and no edge that returns to an ancestor. Real relationship data frequently violates both assumptions. Two records can reference each other. Several parents can reach the same logical child. A migration can leave a self-reference. A query can combine incoming and outgoing relationships into one navigable structure. Under those conditions, a method that merely calls Visit(child) delegates its control flow to the quality of stored data.

A simple cycle, A -> B -> C -> A, is sufficient to keep an unguarded recursive traversal moving through the same path. The .NET documentation for StackOverflowException describes the failure produced when the execution stack is exhausted. An application should not use stack exhaustion as its cycle detector. The safe boundary is established before another node is scheduled, not after the process reaches a catastrophic depth.

A shared descendant is a quieter problem. Suppose left and right both point to shared. Without a visited set, shared can be emitted twice, evaluated twice, or serialized twice. The request may still complete, so a test that checks only “did it return?” misses the defect. Acceptance tests must verify that each logical identity appears at most once, even when duplicate edges or converging paths exist.

A traversal contract should therefore answer at least four questions before implementation begins. What constitutes node identity? At what moment is a node marked as discovered? Which explicit data structure owns pending work? How many nodes may be admitted? If those decisions are scattered across a controller, a recursive helper, and serialization cleanup, one missed path can reopen the cycle or expansion defect.

When should a node enter the visited set?

Register a node when it is first admitted to the queue, not after it is dequeued or fully processed. Admission-time marking prevents multiple parent edges from scheduling the same identity and makes “at most one queued work item per node” a testable invariant.

HashSet.Add returns true when the value was not already present and was added, and false when the set already contained it. That return value combines the membership decision and registration step: enqueue only when visited.Add(neighbor) succeeds. Calling Contains and then Add several lines later adds unnecessary branching. In a concurrent design, the two calls would also require an explicit synchronization strategy; they must not be assumed to form an atomic operation.

Identity must be selected deliberately. When nodes have stable, unique logical identifiers, a HashSet, HashSet, or dedicated key record is usually clearer than object-reference identity. A case-sensitive string identifier can use StringComparer.Ordinal. If the domain contract is case-insensitive, select the appropriate comparer explicitly rather than relying on the machine culture. Two different object instances that represent the same database row should not be visited twice merely because their references differ.

Reference identity can still be correct when the traversal operates on a fully assembled in-memory object graph and “the same instance” is the intended definition of the same node. That choice should be documented. Avoid building equality from mutable properties without careful review: if a field used by Equals or GetHashCode changes after insertion into a hash set, later membership behavior can become surprising.

The marking point controls memory growth as well as output duplication. With admission-time marking, each identity enters the queue no more than once. With processing-time marking, two parent nodes can enqueue the same child before either copy is processed. A later output filter might hide the duplicate, but the queue, allocations, and upstream work have already grown. Large graphs should prevent duplicate work rather than clean it up afterward.

Why must the node cap be enforced inside the neighbor loop?

An outer while condition is not a hard cap because one high-degree node can enqueue a large adjacency list in a single iteration. Check the accepted-node count before every new neighbor, and document whether the starting node consumes one unit of the limit.

A common loop is while (queue.Count > 0 && result.Count is first-in, first-out, so the example produces predictable breadth-first output when each adjacency array has stable order. That does not mean results taken from an unordered dictionary, an SQL query without ORDER BY, or several distributed sources will remain stable. If consumers require deterministic order, define and apply an ordering key before admission, then account for that sorting cost.

How should iterative BFS, recursive DFS, and output models be chosen?

For unknown-depth or cyclic graphs, prefer an explicit queue or stack so pending work, cancellation points, and limits are observable. Recursion remains reasonable only when depth is reliably bounded, and it still requires identity-based cycle protection.

Breadth-first search is useful for level-by-level exploration, minimum-edge paths, and user interfaces that progressively expand nearby nodes. Depth-first search is useful when a complete path should be explored before backtracking. Both can be iterative: BFS uses Queue, while DFS uses Stack. The choice should follow the output contract and resource model rather than whichever version uses fewer lines.

Changing recursion to a queue does not solve every data problem. The application still needs a rule for a missing start node, blank or unknown neighbor identifiers, null adjacency collections, and data that changes during traversal. A reliable implementation usually traverses an immutable snapshot or uses a clearly defined synchronization and consistency boundary. An explicit work queue improves control flow; it does not automatically create a consistent data snapshot.

Cycle-safe traversal is also different from cycle-safe serialization. The algorithm may emit each node once, yet the returned objects can still retain bidirectional navigation properties. A JSON serializer can encounter those references even though the traversal itself terminated. Public API models should normally project the result into a node table plus an edge table, or into a deliberately one-directional DTO, instead of exposing an ORM entity graph unchanged.

Performance claims require similar restraint. Hash-based membership is an appropriate default for identity lookup, but actual cost depends on the comparer, key allocation, graph density, and source latency. This article does not publish a timing benchmark or reuse project-specific row counts from the source note. A production maxNodes value should be derived from payload budgets, serialization cost, frontend capacity, and product requirements.

Verification and Reproduction: test cycles, limits, and shared descendants on .NET

The following sandbox uses a pinned .NET SDK and synthetic in-memory graphs to verify finite cycle traversal, an exact inner-loop cap, and deduplication of shared nodes. It does not connect to a database, cache, website, account, or production service.

Prerequisites are .NET SDK 10.0.400 and Microsoft.NETCore.App 10.0.11. Create a new directory named GraphTraversalLab, then add the pinned SDK and project files below so the test cannot silently roll to another version. The scheduler environment executed all three individual modes and the combined mode; every command exited with code zero.

  1. Create an empty directory and save global.json plus GraphTraversalLab.csproj. Run dotnet --version; stop if it is not exactly 10.0.400.
  2. Save the complete Program.cs below. The program creates only small dictionaries, queues, sets, and lists in memory and performs no external writes.
  3. Run the cycle, limit, identity, and all commands. A nonzero exit, missing PASS line, duplicate node, or result larger than five nodes is a failure.

global.json:

{"sdk":{"version":"10.0.400","rollForward":"disable"}}

GraphTraversalLab.csproj:


  
    Exe
    net10.0
    enable
    enable
    10.0.11
    Disable

Program.cs:

using System.Runtime.InteropServices;

static void Require(bool condition, string message)
{
    if (!condition)
    {
        throw new InvalidOperationException(message);
    }
}

static IReadOnlyList TraverseBounded(
    IReadOnlyDictionary graph,
    string start,
    int maxNodes)
{
    ArgumentOutOfRangeException.ThrowIfLessThan(maxNodes, 1);

    var visited = new HashSet(StringComparer.Ordinal);
    var queue = new Queue();
    var result = new List(maxNodes);

    visited.Add(start);
    queue.Enqueue(start);

    while (queue.Count > 0 && result.Count = maxNodes)
            {
                break;
            }

            if (visited.Add(neighbor))
            {
                queue.Enqueue(neighbor);
            }
        }
    }

    return result;
}

Console.WriteLine($"Runtime: {RuntimeInformation.FrameworkDescription}");
var mode = args.Length == 1 ? args[0] : "all";
Require(new[] { "all", "cycle", "limit", "identity" }.Contains(mode), "Unknown mode");
var checks = 0;

if (mode is "all" or "cycle")
{
    var cycle = new Dictionary(StringComparer.Ordinal)
    {
        ["A"] = ["B"],
        ["B"] = ["C"],
        ["C"] = ["A"]
    };

    var result = TraverseBounded(cycle, "A", 10);
    Require(result.SequenceEqual(new[] { "A", "B", "C" }), "Cycle traversal was not finite or ordered");
    Require(result.Distinct(StringComparer.Ordinal).Count() == result.Count, "Cycle emitted duplicates");
    Console.WriteLine("PASS cycle: A,B,C visited once and traversal terminated");
    checks++;
}

if (mode is "all" or "limit")
{
    var star = new Dictionary(StringComparer.Ordinal)
    {
        ["root"] = Enumerable.Range(1, 20).Select(number => $"n{number:D2}").ToArray()
    };

    var result = TraverseBounded(star, "root", 5);
    Require(result.SequenceEqual(new[] { "root", "n01", "n02", "n03", "n04" }), "Inner-loop limit failed");
    Require(result.Count == 5, "Traversal exceeded the exact node limit");
    Console.WriteLine("PASS limit: a wide adjacency list stopped at exactly 5 nodes");
    checks++;
}

if (mode is "all" or "identity")
{
    var graph = new Dictionary(StringComparer.Ordinal)
    {
        ["root"] = ["left", "right", "left"],
        ["left"] = ["shared"],
        ["right"] = ["shared"],
        ["shared"] = []
    };

    var result = TraverseBounded(graph, "root", 10);
    Require(result.SequenceEqual(new[] { "root", "left", "right", "shared" }), "Stable identity or BFS order failed");
    Require(result.Count(item => item == "shared") == 1, "Shared node emitted more than once");
    Console.WriteLine("PASS identity: duplicate edges and shared descendants emitted one node each");
    checks++;
}

Console.WriteLine($"PASS total checks: {checks}");

Run these commands:

dotnet run --configuration Release -- cycle
dotnet run --configuration Release -- limit
dotnet run --configuration Release -- identity
dotnet run --configuration Release -- all

The scheduler captured this real output from the all mode:

Runtime: .NET 10.0.11
PASS cycle: A,B,C visited once and traversal terminated
PASS limit: a wide adjacency list stopped at exactly 5 nodes
PASS identity: duplicate edges and shared descendants emitted one node each
PASS total checks: 3

The laboratory intentionally does not execute infinite recursion or force a real stack overflow. Proving the guard does not require crashing the process first. The cycle mode must return exactly A,B,C; the limit mode must return the root and the first four neighbors; the identity mode must emit shared exactly once. Keeping the checks separate makes a regression attributable to identity, capacity, or ordering rather than to an ambiguous combined assertion.

The same commands provide the three verification checklist methods. For the cycle claim, run dotnet run --configuration Release -- cycle and require exit zero plus the cycle PASS line. For the cap claim, run the limit mode and require exactly five ordered nodes. For shared identity, run the identity mode and require one shared node even though two parents and one duplicate edge reach it.

Official references, review checklist, and conclusion

Safe graph traversal is not complete after adding a visited variable. Identity, marking time, pending-work ownership, exact capacity, truncation policy, ordering, cancellation, and output shape must become explicit contracts and be verified with cyclic and wide fixtures.

The official HTTPS references were successfully opened and checked. Microsoft’s HashSet.Add API supports using the Boolean return value to determine whether a value was newly admitted. Microsoft’s Queue API documents the first-in, first-out collection semantics used by breadth-first traversal. Microsoft’s StackOverflowException API documents the failure associated with exhausting the execution stack. The verified URLs are:

Before merging or publishing a traversal implementation, review the following points. Does every node have a stable identity? Is it registered when admitted to pending work? Does the starting node consume capacity? Is the limit checked before each neighbor is accepted? Is truncation visible to the caller? Is adjacency order deterministic where required? Can cancellation stop both traversal and its data source? Does the DTO remove bidirectional reference cycles? Do tests include a cycle, wide hub, duplicate edge, and shared descendant?

The source note was read in full. This article carries forward only the general concepts of cycle prevention, per-neighbor capacity enforcement, and large-graph containment. It excludes project names, real identifiers, network addresses, row counts, timing figures, and personal achievement claims. Its intent is distinct from the existing Parallel.For article about indexed result ownership, the shared-cache article about object mutation isolation, and the infinite-list article about DOM sentinel diagnostics. This pair answers how server-side relationship traversal remains finite, unique, and explicitly bounded.