This article is a personal engineering essay on graph algorithms applied to on-chain arbitrage detection. It is for informational and educational purposes only and does not constitute investment, legal, or financial advice, nor a recommendation to engage in arbitrage, MEV extraction, or any specific trading strategy on any blockchain. Tokens, pools, DEXes, and protocols are named only as technical illustrations; their inclusion is not an endorsement. The publisher holds no positions in and has received no compensation from any project named herein.

Cycle Detection Algorithms — DFS vs BFS

I have a graph. Tokens are nodes. Pools are edges. Profitable arbitrage paths are cycles in this graph — loops that start at SOL, pass through other tokens, and return to SOL with more value than they started with. The theory maps cleanly to DeFi reality. The math maps beautifully. Negative-weight cycles in a log-transformed graph. Bellman-Ford. Textbook computer science applied to DeFi.

Now I need to actually find these cycles. And that's where things get ugly.

Because "find all cycles in a graph" sounds like a homework problem from an undergraduate algorithms class. The kind of thing you solve on a whiteboard in twenty minutes, impress the professor, and move on. But when the graph has hundreds of nodes, thousands of edges, and the answer needs to arrive in milliseconds — not minutes — the homework problem becomes an engineering nightmare.

I'm staring at two classic approaches: Depth-First Search and Breadth-First Search. Both are fundamental graph traversal algorithms. Both can detect cycles. But they behave very differently when the question isn't just "does a cycle exist?" but "enumerate every cycle up to length 4 in a graph with thousands of edges, evaluate each one, and do it faster than the other guy."

GPS Navigation: Two Ways to Find a Route

Think about how GPS navigation works. You type in a destination — say, you're in downtown Chicago and you want to get to O'Hare Airport. Your GPS needs to find a route through a network of streets, highways, and interchanges.

There are two fundamentally different strategies the GPS could use.

Strategy One: Pick a road and follow it. Start driving north on Michigan Avenue. At the first intersection, take a left. Follow that street until it dead-ends. Back up, try the next turn. Follow that road until it either reaches O'Hare or dead-ends. Back up again. Try the next option. This is essentially what happens in your head when you're exploring an unfamiliar city without a map — you pick a direction, commit to it, and only change course when you hit a wall.

Strategy Two: Expand outward from where you are. First, look at every intersection one block away from your starting point. Then look at every intersection two blocks away. Then three. Like ripples spreading from a stone dropped in water, you explore the network in concentric circles, getting progressively farther from your origin until one of those ripples touches O'Hare.

Strategy One is Depth-First Search (DFS). Strategy Two is Breadth-First Search (BFS).

For finding the shortest route to O'Hare, Strategy Two (BFS) is the clear winner. It guarantees you find the shortest path first, because it explores all paths of length N before any path of length N+1. GPS navigation systems are built on this principle (well, on Dijkstra's algorithm, which is a weighted cousin of BFS).

But I'm not looking for the shortest path to a destination. I'm looking for loops. Cycles. Routes that bring me back to where I started. And for that problem, the two strategies perform very differently.

DFS: The Natural Cycle Hunter

DFS is recursive at its heart. It works like this:

1. Start at a node (SOL).
2. Pick one of its neighbors (say, USDC — meaning there's a pool that swaps SOL for USDC).
3. From USDC, pick one of its neighbors (say, BONK).
4. From BONK, pick one of its neighbors.
5. If that neighbor is SOL — the node I started from — I've found a cycle. Record it.
6. If not, keep going deeper. Unless I've hit my maximum depth (3 or 4 hops), in which case, backtrack.
7. When I backtrack, try the next untried neighbor at the current node.
8. Repeat until all paths have been explored.

The key mechanism is the visited stack. As I traverse the graph, I maintain a record of which nodes are currently on my path. When I'm exploring the path SOL → USDC → BONK, my visited stack contains {SOL, USDC, BONK}. If I now encounter an edge from BONK that leads back to SOL, I check my visited stack, see that SOL is already on it, and know I've found a cycle. This check — "does this edge point back to a node already in my current traversal path?" — is called detecting a back edge. And back edges are literally the definition of a cycle in a directed graph.

This is why DFS is the natural algorithm for cycle detection. The visited stack is doing the work for me. Every time I descend one level deeper, I add the new node to the stack. Every time I backtrack, I remove it. A back edge to any node currently on the stack means a cycle exists through that node.

It's like exploring a corn maze. You walk in, take a left, take a right, take another left. You're trailing a string behind you — that's your visited stack. If you ever look down and see the string at your feet, you've found a loop. You backtrack, try a different path, trail the string again. Eventually you've explored every possible path through the maze and found every loop in it.

For my arbitrage problem, I configure DFS with a maximum depth — typically 3 or 4, corresponding to 3-hop and 4-hop cycles. I don't want cycles longer than that because the swap fees would eat any profit. So the algorithm is depth-limited DFS: explore every path starting from SOL, up to 4 hops deep, and record every path that returns to SOL.

The algorithmic structure looks conceptually like this:

function findCycles(currentNode, startNode, depth, visited, path):
    if depth == 0:
        return  // hit max depth, backtrack
    
    for each neighbor of currentNode:
        if neighbor == startNode and path.length >= 2:
            record cycle(path + neighbor)  // found a cycle!
        
        if neighbor not in visited:
            visited.add(neighbor)
            path.append(neighbor)
            findCycles(neighbor, startNode, depth - 1, visited, path)
            path.removeLast()
            visited.remove(neighbor)

Start the recursion with findCycles(SOL, SOL, 4, {SOL}, [SOL]) and it will systematically discover every cycle of length 2, 3, or 4 that passes through SOL.

BFS: Expanding Ripples

BFS takes the opposite approach. Instead of diving deep down one path, it expands outward level by level.

Starting from SOL:

• Level 1: Find all tokens directly reachable from SOL. (USDC, USDT, BONK, WIF, JUP, etc. — everything connected by a pool.)
• Level 2: For each token found in Level 1, find all of their neighbors. Now I have all tokens reachable in exactly 2 hops from SOL.
• Level 3: Expand again. All tokens reachable in exactly 3 hops.
• Level 4: One more expansion.

At each level, if any of the newly discovered neighbors is SOL itself, I've found a cycle of that length.

BFS uses a queue instead of a stack. It processes nodes in the order they were discovered — first in, first out. This guarantees that it explores all paths of length N before any path of length N+1, which is why it's optimal for shortest-path problems.

But for cycle enumeration, BFS has a problem. A big one.

Think about subway systems. The New York City subway map is a graph — stations are nodes, track segments are edges. If you want to find the shortest route from Penn Station to JFK, BFS is perfect. It expands outward station by station, and the first time it reaches JFK, that route is guaranteed to be the shortest.

But now imagine a different question: "Find every possible loop that starts and ends at Penn Station and uses at most 4 transfers." That's my cycle detection problem. And BFS is terrible at it.

Why? Because BFS explores breadth first. At each level, it considers every possible node at that distance. To find cycles, it would need to track not just "which nodes are reachable at distance N" but "every distinct path that reaches each node at distance N." Because two different paths arriving at the same node represent two different potential cycles.

If SOL connects to 20 tokens, and each of those connects to 15 more tokens, by level 2 I'm tracking up to 300 paths. By level 3, it's 300 times the average branching factor. By level 4, the number of paths being tracked has exploded. BFS's memory usage grows exponentially with depth because it has to hold the entire frontier — every active path at the current level — in memory simultaneously.

DFS, by contrast, only holds one path in memory at a time. It dives deep, checks for a cycle, backtracks, and dives again. Its memory usage is proportional to the maximum depth, not to the branching factor. For a graph with hundreds of tokens and thousands of pools, this difference is decisive.

It's the difference between two approaches to filling out a March Madness bracket. BFS is like trying to simultaneously track every possible outcome across all 63 games — 2^63 possible brackets. You'd need more paper than exists on Earth. DFS is like filling out one complete bracket, checking if it's interesting, then erasing the last pick and trying a different one. You only need one sheet of paper. You just erase and rewrite a lot.

The Bellman-Ford Angle

There's a third approach worth mentioning, because it came up in my research: the Bellman-Ford algorithm. This is the algorithm specifically designed for detecting negative-weight cycles in a graph — which, is exactly what profitable arbitrage cycles are when edge weights are negative log exchange rates.

Bellman-Ford works by repeatedly relaxing all edges. It iterates through every edge in the graph V-1 times (where V is the number of nodes). After V-1 iterations, all shortest paths are found. Then it does one more iteration: if any edge can still be relaxed, a negative-weight cycle exists.

This is elegant for detection — answering the binary question "does a profitable cycle exist anywhere in the graph?" But it doesn't directly enumerate cycles. It tells me "yes, there's a profitable loop somewhere," not "here are all the profitable loops, with their exact paths and expected profits." To actually extract the cycle, I'd need additional work on top of Bellman-Ford.

More importantly, Bellman-Ford has a time complexity of O(V * E) — the number of nodes times the number of edges. For a graph with hundreds of tokens and thousands of pools, that's manageable for a single run. But I need to re-evaluate constantly, and I don't just need one cycle — I need all of them. Using Bellman-Ford to find one cycle, removing it, running Bellman-Ford again to find the next, and so on, is far less efficient than a single DFS pass that enumerates everything in one shot.

So Bellman-Ford sits in my toolkit as a useful theoretical foundation and a potential quick-check ("is there any profitable cycle right now?"), but for the core enumeration problem, DFS wins.

The Combinatorial Explosion

Here's where the real pain begins.

I decide on depth-limited DFS. Great. I configure it for 3-hop and 4-hop cycles starting from SOL. I run it against my graph of tokens and pools.

And the numbers come back. Tens of thousands of cycles.

Let me trace through why the numbers get so large.

For a 3-hop cycle, I need three tokens forming a loop: SOL → A → B → SOL. The tokens A and B can be anything in my token universe — USDC, USDT, BONK, WIF, JUP, and so on. If I have N candidate tokens (excluding SOL), there are roughly N * (N-1) possible 3-hop token paths. For even 50 candidate tokens, that's about 2,450 token paths.

But wait — each hop doesn't just have one pool. The SOL→USDC hop might have a Raydium pool, an Orca pool, a Meteora pool, and a Phoenix pool. The USDC→BONK hop might have two or three pools. For each token path, the number of pool combinations is the product of the number of pools at each hop.

So if each hop averages 3 pools, a single token path generates 3 * 3 * 3 = 27 pool combinations. For a 4-hop cycle with 3 pools per hop, it's 3^4 = 81 combinations per token path.

And for 4-hop cycles, the token paths are N * (N-1) * (N-2) — roughly 117,600 for 50 tokens. Multiply by 81 pool combinations each and you're looking at over 9.5 million evaluations. For 100 tokens, you're in the hundreds of millions.

This is the combinatorial explosion. The number of possible cycles grows polynomially with tokens and exponentially with the number of pools per hop. With hundreds of tokens and thousands of pools across the Solana DEX landscape, brute-force enumeration of every possible pool combination is computationally intractable — not because any single evaluation is slow, but because there are simply too many of them.

It's like trying to plan your Amazon shopping by comparing every possible combination of products across every possible seller, including shipping costs, delivery times, and bundle discounts. For a cart with 10 items, each available from 5 sellers, you'd need to evaluate 5^10 — roughly 10 million — combinations. Nobody does this. You use heuristics. You pick "best seller" for each item independently and call it close enough.

The same insight applies to cycle detection. I can't evaluate every possible pool combination for every possible cycle. I need to be smarter.

The Token-Path Approach

Here's the key insight that changes everything.

Instead of enumerating pool combinations, I enumerate token paths first.

A token path is just the sequence of tokens: SOL → USDC → BONK → SOL. It doesn't specify which pool to use at each hop. It just defines the route through token-space.

Once I have a token path, picking the best pool at each hop is a much simpler problem. For the SOL→USDC hop, I check all available pools for that pair and pick the one offering the best exchange rate right now. For the USDC→BONK hop, same thing. For BONK→SOL, same thing. Each hop is an independent optimization.

This is the difference between solving a chess problem and solving a checkers problem.

In chess — the combinatorial approach — you try to think ten moves ahead, considering every possible response by your opponent at each step. The tree of possibilities branches exponentially. Grandmasters can only evaluate a fraction of it, relying on pattern recognition and heuristics to prune the tree.

In checkers — the token-path approach — the rules are simpler. There are fewer pieces, fewer possible moves, and the game tree is orders of magnitude smaller. You can often see the best path without needing to evaluate every branch.

By fixing the token path first, I've converted a chess problem into a checkers problem. Instead of evaluating N^4 pool combinations for a 4-hop cycle (chess), I evaluate N^3 token paths, and for each one, I independently select the best pool at each of the 4 hops (checkers).

Let me put numbers on this. Say I have 50 candidate tokens and an average of 3 pools per hop.

Pool-combination approach (4-hop): 50 * 49 * 48 * 3^4 = approximately 9.5 million evaluations.

Token-path approach (4-hop): 50 * 49 * 48 = 117,600 token paths. For each path, I evaluate 3 + 3 + 3 + 3 = 12 pool comparisons (picking the best at each hop). Total: about 1.4 million comparisons, but each comparison is trivially simple — "which of these 3 pools gives the best rate for this specific pair?"

The token-path approach doesn't just reduce the number of evaluations. It changes the structure of the problem. Instead of one massive optimization over a combinatorial space, it becomes a sequence of small, independent optimizations. And independent optimizations are easy. They parallelize naturally. They cache well. They're fast.

Why the Reduction Works

The reason this works — and this took me a while to convince myself of — is that the best pool at each hop is independent of the pools chosen at other hops.

If the Raydium SOL/USDC pool gives a better rate than the Orca SOL/USDC pool right now, it gives a better rate regardless of whether I'm going to use Raydium or Meteora for the next hop. The pools are independent pricing engines. They don't know about each other. Choosing the best pool at hop 1 doesn't affect the available rates at hop 2.

This is exactly like choosing highway exits on a road trip. If Exit 47 has cheaper gas than Exit 52, you fill up at Exit 47 regardless of where you plan to eat lunch. The gas price at Exit 47 doesn't change based on your restaurant plans. Each decision is independent.

There's a subtlety here that I want to flag, because it matters in practice: this independence assumption breaks down if I'm trading large enough amounts to significantly move pool prices. If I swap 100 SOL through a small pool, the price impact might change the reserves enough that the "best" pool for a subsequent hop (on a different pair) is affected — because maybe that subsequent pool shares a token with the first pool, and some other arbitrageur reacts to my first swap by adjusting the second pool. But for reasonable trade sizes and within a single atomic transaction, the independence holds. The pools don't update until my transaction finalizes, and within a single transaction, each pool sees only my swap against its current reserves.

Pre-Compute vs. Real-Time Selection

This token-path approach reveals a deeper philosophical choice in system design: pre-compute everything versus decide at execution time.

The pre-compute approach says: before you even start looking for opportunities, enumerate every possible pool combination for every cycle, store them all in a list, and evaluate them one by one whenever data changes. This is the Amazon warehouse model — stock every possible product variant, and when an order comes in, just grab it off the shelf. Efficient at execution time, but enormous setup cost and wasted space for variants that never sell.

The real-time selection approach says: enumerate only token paths (the high-level routes), and when you need to evaluate a cycle, pick the best pools at that moment based on current data. This is the Just-In-Time manufacturing model — don't stock finished products, stock components, and assemble on demand based on what's actually needed.

For arbitrage, real-time selection wins decisively, for three reasons.

First, pool rates change constantly. The "best" pool for the SOL→USDC hop right now might not be the best pool 500 milliseconds from now. If I pre-computed the pool combination, I'd be executing based on stale data. By selecting pools at evaluation time, I always use the freshest rates.

Second, new pools appear and old pools drain. The Solana DEX landscape isn't static. New liquidity pools are created regularly. Existing pools gain or lose liquidity. A pre-computed list of pool combinations becomes outdated as the graph topology changes. With the token-path approach, I just need to update my list of available pools per token pair — the token paths themselves are much more stable.

Third, it naturally handles the "which metric to optimize" question. At each hop, "best pool" might mean different things — lowest fee, best rate, highest liquidity (for lower price impact), or some composite score. By making pool selection a runtime decision, I can easily swap in different selection criteria without re-enumerating all cycles.

Flexibility beats perfection. A system that makes good decisions with current data will always outperform a system that made optimal decisions with yesterday's data.

Implementing the Two-Phase Approach

So the detection system takes shape as two distinct phases.

Phase 1: Cycle Discovery. Run depth-limited DFS on the token graph (not the pool graph). This is a one-time operation — or rather, an infrequent operation that runs whenever the token universe changes (new token listed, old token removed). The output is a list of token paths: SOL → USDC → BONK → SOL, SOL → USDT → WIF → SOL, SOL → USDC → WIF → BONK → SOL, and so on. Tens of thousands of them.

This is the phase where DFS shines. The token graph is much smaller than the pool graph — maybe a hundred nodes instead of thousands of edges — and DFS with a depth limit of 4 runs fast. The visited stack keeps memory usage minimal. Backtracking is efficient. The entire enumeration completes in a fraction of a second.

Phase 2: Cycle Evaluation. For each token path from Phase 1, select the best pool at each hop based on current reserves and rates, then compute the end-to-end cycle output using exact AMM math. If output minus costs is positive, flag the cycle as a candidate for execution.

This phase runs continuously — or rather, it runs every time the underlying pool data updates. A new block arrives, pool reserves change, and the evaluation sweeps through all token paths with fresh data. Each evaluation is fast because pool selection is independent at each hop. The whole sweep can complete in milliseconds.

The beauty of this separation is that Phase 1 and Phase 2 operate on completely different timescales. Phase 1 runs rarely — maybe once a minute, or when new pools are discovered. Phase 2 runs constantly — potentially hundreds of times per second. By pre-computing the token paths (the slow part) and doing pool selection in real time (the fast part), I get the best of both worlds.

It's like how Amazon's warehouse routing works. The warehouse layout — where the shelves are, which aisles connect to which — changes infrequently. That's the graph structure, updated maybe once a day. But the picking route — which shelf to visit first for a specific order — is computed in real time for every order based on what's currently in stock and where. Same graph, different timescales for different decisions.

What BFS Gets Right (And Why I Still Don't Use It)

I want to be fair to BFS, because it does have genuine strengths that I considered before choosing DFS.

BFS guarantees finding the shortest cycle first. If I only cared about 3-hop cycles and wanted to make sure I found all of them before wasting time on longer paths, BFS would naturally give me that ordering. DFS might find a 4-hop cycle before finding a 3-hop cycle, depending on the order it explores neighbors.

BFS is also better at finding all nodes within a given distance. If the question were "which tokens are reachable from SOL in exactly 3 hops?", BFS answers this perfectly — its level-by-level expansion is designed for exactly this question.

But these advantages don't matter for my problem. I don't need cycles in shortest-first order. I need all cycles up to a depth limit, and I need them fast. DFS's lower memory footprint and natural backtracking make it the clear winner.

There's also a hybrid approach I've seen discussed: use BFS to build a "distance map" from SOL (which tokens are reachable at each hop count), then use DFS only on paths that the BFS map confirms can close back to SOL. This prunes dead-end DFS paths early — if I'm at hop 3 and the current token has no 1-hop path back to SOL (according to the BFS map), I can skip it immediately without exploring further. It's a nice optimization, but the overhead of running BFS first often isn't worth it when the depth limit is small (3-4 hops) and the DFS already runs fast on the token graph.

The Practical Takeaway

Here's where I stand after working through all of this.

The detection pipeline is a two-layer system. The first layer — cycle discovery — uses depth-limited DFS on the token graph to enumerate all possible token paths up to length 4. This produces tens of thousands of candidate cycles. It runs infrequently and completes fast.

The second layer — cycle evaluation — takes those token paths and, for each one, selects the best pool at each hop based on live data, then runs full AMM math to compute profitability. This runs continuously, sweeping through all candidates with every data update.

The key insight that makes this tractable is the separation of concerns: token paths are structural (they change slowly) while pool selection is tactical (it changes constantly). By decoupling these two decisions, I avoid the combinatorial explosion that would make brute-force enumeration impossible.

DFS wins over BFS for cycle enumeration because it uses less memory, naturally tracks cycles via its visited stack, and handles backtracking gracefully. BFS wins for shortest-path problems, but that's not my problem. Bellman-Ford is elegant for detecting the existence of profitable cycles, but it doesn't enumerate them efficiently.

And the real insight — the one that took me longer than it should have to reach — is that you don't need to pre-compute every possible pool combination to find the best one. You just need to know the routes (token paths) and make the best tactical choice at each step using current data. It's the same principle that makes a good quarterback different from a good chess computer. The chess computer tries to evaluate every possible sequence of moves. The quarterback reads the defense, picks the best receiver right now, and throws. The quarterback doesn't evaluate every possible pass combination against every possible defensive alignment. He picks the route, reads the coverage, and makes a decision in real time.

That's what my detection system does. The token paths are the playbook — drawn up ahead of time, practiced, ready to go. The pool selection is the read — made in the moment, based on what the defense is showing right now. And like a quarterback, speed matters more than perfection. A good decision made in 10 milliseconds beats a perfect decision made in 500 milliseconds, because by the time the perfect decision arrives, the window has closed and the opportunity is gone.

The graph is built. The algorithm is chosen. The architecture is clear. Now I need to make it fast enough to compete.