1. Depth-First Search

Introduction

Depth-First Search (DFS) is a fundamental graph traversal algorithm used to explore or search through a graph. It starts at a given vertex and explores as far as possible along each branch before backtracking. It has various applications. For example, it can be used to detect cycles or find connected components.

Algorithm

The DFS algorithm can be implemented using a stack or recursion. Here is a basic outline of the algorithm:

1. Choose a starting vertex and push it onto the stack.
2. While the stack is not empty, pop a vertex and mark it as visited.
3. Push all the unvisited neighbors of the popped vertex onto the stack.

   In this section, we will push neighbors in reverse order, e.g. from big to small. So that the smaller neighbors will be visited first.

4. Repeat steps 2 to 3 until the stack is empty.

Exercise

1. Run DFS algorithm starting at vertex 0 with Auto Play.
2. Change the starting vertex to 3 and run the algorithm manually (by clicking First Step).
3. Try to make a graph with 5 vertices and any number of edges. Choose a starting vertex and calculate the traversal order using DFS without looking at the result. Then, run the algorithm to check your answer.

DFS using stack

When using a stack, we mimic the call stack of recursion by manually maintaining a stack data structure. We start with the initial node and push it onto the stack. Then, while the stack is not empty, we pop a node from the top of the stack, visit it, and push its unvisited neighbors onto the stack. This process continues until the stack becomes empty.

def traversal(adjacency_list):
    visited = set()  # Keep track of visited nodes

    def dfs_stack(start):
        stack = [start]  # Use a stack to simulate the call stack of recursion

        while stack:
            current = stack.pop()  # Take out the current node from the stack
            visited.add(current)  # Mark the current node as visited
            print(current)  # Print the visited node

            # Push unvisited neighbors into the stack in reverse order
            # so that the node with the smallest value will be visited first
            for neighbor in reversed(adjacency_list[current]):
                if (neighbor in visited) or (neighbor in stack): continue
                stack.append(neighbor)

    # Iterate through all nodes in the graph
    for node in adjacency_list:
        if node in visited: continue
        dfs_stack(node)

# Example graph
adjacency_list = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 4],
    3: [1],
    4: [1, 2]
}

traversal(adjacency_list) # 0 1 3 4 2

function traversal(adjacencyList) {
  const visited = new Set() // Keep track of visited nodes

  function dfsStack(start) {
    const stack = [start] // Use a stack to simulate the call stack of recursion

    while (stack.length > 0) {
      const current = stack.pop() // Take out the current node from the stack
      visited.add(current) // Mark the current node as visited
      console.log(current) // Print the visited node

      // Push unvisited neighbors into the stack in reverse order
      // so that the node with the smallest value will be visited first
      for (let i = adjacencyList[current].length - 1; i >= 0; i--) {
        const neighbor = adjacencyList[current][i]
        if (visited.has(neighbor) || stack.includes(neighbor)) continue
        stack.push(neighbor)
      }
    }
  }

  // Iterate through all nodes in the graph
  for (let node in adjacencyList) {
    if (visited.has(node)) continue
    dfsStack(node)
  }
}

// Example graph
const adjacencyList = {
  0: [1, 2],
  1: [0, 3, 4],
  2: [0, 4],
  3: [1],
  4: [1, 2],
}

traversal(adjacencyList) // 0 1 3 4 2

DFS using recursion

On the other hand, DFS can also be implemented recursively. In the recursive version, we start from a selected node and mark it as visited. Then, for each unvisited neighbor of the current node, we recursively call the DFS function, effectively exploring deeper into the graph. This process continues until all nodes have been visited.

def traversal(adjacency_list):
    visited = set()  # Keep track of visited nodes

    def dfs_recursive(current):
        visited.add(current)  # Mark the current node as visited
        print(current)  # Print the visited node

        # Explore the unvisited neighbors
        for neighbor in adjacency_list[current]:
            if neighbor in visited: continue
            dfs_recursive(neighbor)  # Explore the unvisited neighbors

    # Iterate through all nodes in the graph
    for node in adjacency_list:
        if node in visited: continue
        dfs_recursive(node)

# Example graph
adjacency_list = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 4],
    3: [1],
    4: [1, 2]
}

traversal(adjacency_list) # 0 1 3 4 2

function traversal(adjacencyList) {
  const visited = new Set() // Keep track of visited nodes

  function dfsRecursive(current) {
    visited.add(current) // Mark the current node as visited
    console.log(current) // Print the visited node

    for (let neighbor of adjacencyList[current]) {
      if (!visited.has(neighbor)) continue
      dfsRecursive(neighbor) // Explore the unvisited neighbors
    }
  }

  // Iterate through all nodes in the graph
  for (let node in adjacencyList) {
    if (visited.has(node)) continue
    dfsRecursive(node)
  }
}

// Example graph
const adjacencyList = {
  0: [1, 2],
  1: [0, 3, 4],
  2: [0, 4],
  3: [1],
  4: [1, 2],
}

traversal(adjacencyList) // 0 1 3 4 2