Depth-First Search (Recursive)

Visit a start vertex, then recurse into its first unvisited neighbour all the way down before backtracking. A visited set prevents revisiting, and neighbour insertion order fixes the visit sequence.

Algorithm

On the canonical 6-vertex graph from graph-adjacency-list, starting at vertex 1, the deterministic visit order is [1, 2, 4, 3, 5, 6]. Calls unwind 6 -> 5 -> 4 -> 3 -> 2 -> 1 after all vertices are visited.

recursive descent Follow one branch to its end, then unwind and try the next neighbour.

Visual walkthrough

DFS follows the first unvisited neighbour as far as it can, then unwinds and tries the next branch.

Step 1 - First branch

Starting from 1, insertion order sends DFS to 2, then 4, then 3.

Step 2 - Full DFS order

The final order is [1, 2, 4, 3, 5, 6], then calls unwind 6 -> 5 -> 4 -> 3 -> 2 -> 1.

Basic Implementation

                            basic.cs
                        

                            using System;
using System.Collections.Generic;
class Program {
	static Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
	static HashSet<int> visited = new HashSet<int>();
	static List<int> order = new List<int>();
	static void Dfs(int v) {
		visited.Add(v);
		order.Add(v);
		foreach (int nb in adj[v]) {
			if (!visited.Contains(nb)) {
				Dfs(nb);
			}
		}
	}
	static void Main() {
		adj[1] = new List<int> { 2, 3 };
		adj[2] = new List<int> { 1, 4 };
		adj[3] = new List<int> { 1, 4 };
		adj[4] = new List<int> { 2, 3, 5 };
		adj[5] = new List<int> { 4, 6 };
		adj[6] = new List<int> { 5 };
		Dfs(1);
		Console.WriteLine("[" + string.Join(", ", order) + "]");
	}
}

                        

Complexity

Time: O(V + E)
Space: O(V) recursion depth

Implementation notes

C#: a recursive static Dfs over static adj, visited, and order; string.Join renders the list.
The replay shows the current vertex, the visited set, and the running visit order after each entry, matching the lesson spec.