How it works
Depth-first traversal follows one branch as far as possible before returning to other pending branches. A stack represents that pending work explicitly, avoiding recursive calls. The sample starts at A, explores B and then D, and finally returns to the pending C branch.
The graph contains both a shared destination and a cycle back to A. The visited set ensures each node is processed once. Add returns false for an already visited node, so the traversal skips it before recording output or adding more neighbors. Without that check, the cycle could keep producing work indefinitely.
Stack order matters. A stack is last-in, first-out, so pushing B and then C would explore C first. Reversing the stored neighbor sequence before pushing preserves the intended listed order for this example. If a deterministic report is required, establish a deterministic neighbor order rather than relying on an unordered collection.
DFS visitation order is not a shortest-path guarantee. It can reach a destination through a long branch before examining a shorter alternative. Use breadth-first traversal for shortest edge counts in an unweighted graph, or another appropriate algorithm when edge weights matter. Traversal strategy should follow the question being asked.
Practice by removing the cycle, adding an isolated node, and reversing A's neighbor list. Predict which changes affect the order and which nodes remain unreachable from A. A traversal from one starting node does not automatically visit every disconnected component.
Finally, adapt the code to traverse every component by starting another DFS from each unvisited graph key. Decide whether the graph contract requires every referenced neighbor to be a declared key and validate that boundary. Useful graph tests cover cycles, shared nodes, disconnected components, and ordering assumptions rather than only a simple tree.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
var graph = new Dictionary<string, string[]> {
["A"] = new[] { "B", "C" }, ["B"] = new[] { "D" },
["C"] = new[] { "D" }, ["D"] = new[] { "A" }
};
var pending = new Stack<string>();
var visited = new HashSet<string>(StringComparer.Ordinal);
var order = new List<string>();
pending.Push("A");
while (pending.Count > 0) {
string node = pending.Pop();
if (!visited.Add(node)) continue;
order.Add(node);
foreach (string next in graph[node].Reverse()) pending.Push(next);
}
Console.WriteLine(string.Join(",", order));
Expected output
A,B,D,C
Push neighbors in reverse order when the first listed neighbor should be explored next.