The problem really is, your graph image is not exactly one to one with your example #edges data. In your graph image, node 2 is unique. In the #edges table, node 2 exists twice because it is a child of node 0 and node 1. So this actually implicitly ends up breaking your graph into a tree instead, with node 2 duplicated.

1. Is there a more efficient way to traverse the graph in the above example using recursive CTEs?

Is the current implementation unacceptably inefficient? Just because it's traversing duplicate nodes doesn't necessarily mean the process to get there was inefficient. What does the execution plan show happened under the hood? What does the TIME and IO STATISTICS say in regards to runtime computation? I've generally found recursive CTEs to be rather performant even when iterating over decently sized collections of data.

If you want to visit each node only once, then you can workaround the redundancy issue by keeping track of nodes that were already visited, on each iteration of the recursion. One way to do that is by building a string of already visited nodes with a separator and doing a wildcard contains search, like such:

WITH descendents(node)
AS(
    SELECT 0 as node, CONVERT(VARCHAR(MAX), '0') AS NodesVisited
    UNION ALL
    SELECT head as node, CONCAT(prior.NodesVisited, '|', head) AS NodesVisited
    FROM descendents as prior
    JOIN #edges ON prior.node = tail
    WHERE prior.NodesVisited NOT LIKE CONCAT('%|', #edges.head, '|%')
)
...

But this methodology can be inefficient in itself because there is overhead to doing the wildcard contains search in the WHERE clause on each iteration. This coupled with the NOT LIKE clause also makes the predicate non-sargable which effectively means it can't take use of an index to efficiently serve that predicate. Depending on the size of the #edges data, that could also impact the performance negatively.

A slightly alternative option (assuming you're on SQL Server 2016 or newer) is to build the string of visited nodes, then use CROSS APPLY with the built-in STRING_SPLIT() function to join to the collection of visited nodes as a dataset, as opposed to using a wildcard contains search. This too can be resource intensive though (from the repeated calls to the STRING_SPLIT() function).

At the end of the day, you're going to want to look at the execution plan and runtime statistics, as previously mentioned, to determine how performant each implementation is, and compare them.

• stored procedure that implements recursion programmatically
• hierarchyid
• SQL Graph

2. Of the above alternatives, what are the tradeoffs?

The stored procedure route will likely be less efficient than your recursive CTE implementation. It's more of a procedural code approach as opposed to a relational one. I've converted recursive stored procedures that took over 1 hour to compute down to under 1 second by implementing them as recursive CTEs.

The hierarchyid data type I have no experience with, but I would guess you would still need to implement a recursive-based solution to get the end results you're after, either way. I don't believe this data type is commonly used.

Using the SQL Graph feature would be interesting. I only have minimal experience using that as well. But again, I think it's a much less utilized feature of SQL Server, and so there's probably less information out there on how to properly use it efficiently.

3. Are there any other alternatives I should consider?

Not that I can think of at the moment. The most common solution is a recursive CTE, generally.