Skip to content

dfs ​

dfs(graph, start) visits the vertices reachable from start in iterative depth-first order. The input can be an adjacency list or a Graph<N, i32>; the result contains vertex indices in visitation order.

Function ​

SignatureReturnsDescription
dfs(adj: usize[][], start: usize)usize[]Visits an adjacency-list graph in iterative depth-first order
dfs(graph: Graph<N, i32>, start: usize)usize[]Visits a Graph in iterative depth-first order

The starting vertex must be within the input graph. Neighbors are processed in reverse stack insertion order so the result follows the same order as a recursive traversal over the adjacency list.

Complexity ​

OperationTime Complexity
traversalO(V + E)
memoryO(V)

Examples ​

adjacency list ​

tyrus
import { dfs } from "tyrus:algorithm";

const graph: usize[][] = [[1, 2], [3], [3], []];
const order: usize[] = dfs(graph, 0);

print(order);  // [0, 1, 3, 2]

Study result ​

dfsInfo returns TraversalInfo with the visit order and deterministic stack, depth, and edge metrics.

tyrus
interface TraversalInfo {
    start: usize;
    visitOrder: usize[];
    visitedCount: usize;
    examinedEdgeCount: usize;
    maxFrontierSize: usize;
    maxDepth: usize;
}
tyrus
import { TraversalInfo, dfsInfo } from "tyrus:algorithm";

const info: TraversalInfo = dfsInfo([[1, 2], [3], [3], []], 0);
print(info.visitOrder); // [0, 1, 3, 2]
print(info.visitedCount); // 4
print(info.examinedEdgeCount); // 4
print(info.maxFrontierSize); // 2
print(info.maxDepth); // 2

Graph input ​

tyrus
import { Graph, dfs } from "tyrus:algorithm";

const graph = Graph<i32, i32>();
graph.addEdge(0, 1, 1);
graph.addEdge(0, 2, 1);
graph.addEdge(1, 3, 1);

const order: usize[] = dfs(graph, 0);
print(order);  // [0, 1, 3, 2]