Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Graph Traversal - Depth First Search(DFS)

Graphs are made up of nodes (vertices) connected by edges. Traversing a graph means visiting all its nodes in a structured way. This helps solve problems like finding paths, detecting cycles, and searching for specific values.

Two widely used traversal techniques are:

  • Depth-First Search (DFS): Explores as far as possible along each branch before backtracking.
  • Breadth-First Search (BFS): Explores all neighbors of a node before moving deeper.

This lesson focuses on the Depth-First Search (DFS) approach.

.....

.....

.....

Like the course? Get enrolled and start learning!
D

davemednikov

· 2 years ago

Both Step-by-step illustrations of DFS on this page have issues.

For the first graph, containing the vertices [0, 1, 2, 3, 4], the visual representation of the stack behaves like a queue.

When vertex 0 is visited, vertices [1, 2, 3] are pushed onto the stack. On the next turn, vertex 1 is "popped" from the stack and moved to the visited list. The visual representation looks like a queue, where the item with index 0 is popped. It effectively looks like vertex 1 was removed using popleft() instead of pop().

A proper visual representation of the stack would pop vertex 3, since it is the furthest-to-the-right element in the stack. For this entire course queues and stacks have been read from left-to-right.

The graph of the tree-like structure with vertices `[A, B, C, D, E,

Aleksa Rajkovic

Aleksa Rajkovic

· 4 months ago

Please consider removing the part where the algorithm is processing connections of already visited node e.g.

while stack:
    current = stack.pop()

    if not visited[current]:
        print(current, end=" ")
        visited[current] = True

        # MOVE THIS INSIDE: Only add neighbors if we just visited 'current' for the first time
        for neighbor in self.adjacencyList[current]:
            if not visited[neighbor]:
                stack.append(neighbor)
Oluwasemire Olaniyi

Oluwasemire Olaniyi

· 2 years ago

Please correct the algorithm for DFS. This is sooooooo wrong.

Show 1 reply