Medium Graphs
DFS Graph
Traverses a graph depth-first starting from node 0, using an explicit LIFO stack: it visits the start node, dives into one unvisited neighbor as deep as possible, then backtracks to explore the next one — the same building block used to detect cycles and find connected components. Receives the graph as a square adjacency matrix, where a nonzero value at row i, column j marks an edge between nodes i and j (0 means no edge). Returns the node indices in the order they were visited; nodes unreachable from node 0 are never visited.
Visualization
- Input
- Result
Algorithm code
// DFS Graph — a single pure function. Receives a graph as an N×N adjacency
// matrix and returns the depth-first traversal order of node indices
// starting from node 0, using an explicit LIFO stack.
/**
* @param {number[][]} adjacencyMatrix - N×N matrix where a truthy value at
* row i, column j marks an edge between nodes i and j
* @returns {number[]} node indices in depth-first visit order from node 0
*/
export function dfsGraph(adjacencyMatrix) {
const nodeCount = adjacencyMatrix.length;
const order = [];
if (nodeCount === 0) {
return order;
}
const visited = new Array(nodeCount).fill(false);
const stack = [0];
while (stack.length > 0) {
const node = stack.pop();
if (visited[node]) {
continue;
}
visited[node] = true;
order.push(node);
for (let neighbor = nodeCount - 1; neighbor >= 0; neighbor -= 1) {
if (adjacencyMatrix[node][neighbor] && !visited[neighbor]) {
stack.push(neighbor);
}
}
}
return order;
}FUNCTION dfsGraph(adjacencyMatrix):
nodeCount ← length(adjacencyMatrix)
order ← empty list
IF nodeCount = 0:
RETURN order
visited ← array of nodeCount false values
stack ← [0]
WHILE stack is not empty:
node ← pop from stack
IF visited[node]:
CONTINUE
visited[node] ← true
append node to order
FOR neighbor FROM nodeCount - 1 DOWNTO 0:
IF adjacencyMatrix[node][neighbor] AND NOT visited[neighbor]:
push neighbor to stack
RETURN order