Depth-First Search (DFS)

Definition

Definition

Depth-First Search (DFS) is a fundamental graph traversal algorithm used to explore nodes and edges of a graph. It starts at a chosen node and explores as far as possible along each branch before backtracking

Explanation

Begin from a chosen node in the graph. Proceed by exploring each branch extensively before returning back. Keep track of visited nodes to prevent revisiting them

Guidance

• Choose a starting node
• Visit the node and mark it as visited
• Explore one of its neighbors
  • if the neighbor has unvisited neighbors, explore another neighbor
  • if all neighbors are visited, backtrack to the previous node
• Repeat steps until all nodes are visited

Tips

• use a stack or recursion for implementation
• be cautious of infinite loops in cyclic graphs
• optimize memory usage by marking visited nodes appropriately

Practice

Practice

DFS(graph, start_node):
  initialize an empty stack
  push start_node onto the stack
  initialize an empty set to keep track of visited nodes

  while stack is not empty:
    current_node = pop from stack
    if current_node is not visited:
      mark current_node as visited
      visit current_node

      for each neighbor in graph[current_node]:
        if neighbor is not visited:
          push neighbor onto stack

Solution

package main

import (
	"container/list"
)

// Graph DFS
func DFS(graph [][]int, start int) {
	visited := make([]bool, len(graph))
	stack := list.New()
	stack.PushBack(start)

	for stack.Len() > 0 {
		element := stack.Back()
		stack.Remove(element)
		node := element.Value.(int)
		if !visited[node] {
			visited[node] = true
			fmt.Printf("%d ", node)

			for _, neighbor := range graph[node] {
				if !visited[neighbor] {
					stack.PushBack(neighbor)
				}
			}
		}
	}
}

// Binary Tree DFS
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func DFSBinaryTree(root *TreeNode) {
	if root == nil {
		return
	}
	stack := list.New()
	stack.PushBack(root)

	for stack.Len() > 0 {
		element := stack.Back()
		stack.Remove(element)
		node := element.Value.(*TreeNode)
		fmt.Printf("%d ", node.Val)

		if node.Right != nil {
			stack.PushBack(node.Right)
		}
		if node.Left != nil {
			stack.PushBack(node.Left)
		}
	}
}

import java.util.*;

// Graph DFS
class Graph {

  void DFS(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Stack<Integer> stack = new Stack<>();
    stack.push(start);

    while (!stack.isEmpty()) {
      int node = stack.pop();
      if (!visited[node]) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
          if (!visited[neighbor]) {
            stack.push(neighbor);
          }
        }
      }
    }
  }
}

// Binary Tree DFS
class BinaryTree {

  void dfs(TreeNode root) {
    if (root == null) {
      return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
      TreeNode node = stack.pop();
      System.out.print(node.val + " ");

      if (node.right != null) {
        stack.push(node.right);
      }
      if (node.left != null) {
        stack.push(node.left);
      }
    }
  }

  static class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }
}

// Graph DFS
function DFS(graph, start) {
  let visited = new Array(graph.length).fill(false);
  let stack = [];
  stack.push(start);

  while (stack.length > 0) {
    let node = stack.pop();
    if (!visited[node]) {
      visited[node] = true;
      process.stdout.write(node + " ");

      for (let neighbor of graph[node]) {
        if (!visited[neighbor]) {
          stack.push(neighbor);
        }
      }
    }
  }
}

// Binary Tree DFS
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function DFSBinaryTree(root) {
  if (root === null) {
    return;
  }
  let stack = [];
  stack.push(root);

  while (stack.length > 0) {
    let node = stack.pop();
    process.stdout.write(node.val + " ");

    if (node.right !== null) {
      stack.push(node.right);
    }
    if (node.left !== null) {
      stack.push(node.left);
    }
  }
}

import java.util.*

// Graph DFS
fun DFS(graph: List<List<Int>>, start: Int) {
    val visited = BooleanArray(graph.size)
    val stack = Stack<Int>()
    stack.push(start)

    while (!stack.isEmpty()) {
        val node = stack.pop()
        if (!visited[node]) {
            visited[node] = true
            print("$node ")

            for (neighbor in graph[node]) {
                if (!visited[neighbor]) {
                    stack.push(neighbor)
                }
            }
        }
    }
}

// Binary Tree DFS
class DepthFirstSearch {

    fun dfs(root: TreeNode?) {
        if (root == null) {
            return
        }
        val stack = Stack<TreeNode>()
        stack.push(root)

        while (!stack.isEmpty()) {
            val node = stack.pop()
            print("${node.`val`} ")

            if (node.right != null) {
                stack.push(node.right)
            }
            if (node.left != null) {
                stack.push(node.left)
            }
        }
    }

    class TreeNode(var `val`: Int) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }
}

# Graph DFS
def dfs_graph(graph, start):
    visited = [False] * len(graph)
    stack = []
    stack.append(start)

    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            print(node, end=" ")

            for neighbor in graph[node]:
                if not visited[neighbor]:
                    stack.append(neighbor)

# Binary Tree DFS
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def dfs_binary_tree(root):
    if not root:
        return
    stack = []
    stack.append(root)

    while stack:
        node = stack.pop()
        print(node.val, end=" ")

        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

use std::collections::VecDeque;

// Graph DFS
fn dfs(graph: &Vec<Vec<usize>>, start: usize) {
    let mut visited = vec![false; graph.len()];
    let mut stack = Vec::new();
    stack.push(start);

    while let Some(node) = stack.pop() {
        if !visited[node] {
            visited[node] = true;
            print!("{} ", node);

            for &neighbor in &graph[node] {
                if !visited[neighbor] {
                    stack.push(neighbor);
                }
            }
        }
    }
}

// Binary Tree DFS
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn dfs_binary_tree(root: Option<Box<TreeNode>>) {
    let mut stack = Vec::new();
    stack.push(root);

    while let Some(mut node) = stack.pop() {
        if let Some(n) = node.as_ref() {
            print!("{} ", n.val);

            if let Some(right) = &n.right {
                stack.push(Some(right.clone()));
            }
            if let Some(left) = &n.left {
                stack.push(Some(left.clone()));
            }
        }
    }
}

// Graph DFS
function DFS(graph: number[][], start: number): void {
  const visited: boolean[] = new Array(graph.length).fill(false);
  const stack: number[] = [];
  stack.push(start);

  while (stack.length > 0) {
    const node: number = stack.pop()!;
    if (!visited[node]) {
      visited[node] = true;
      process.stdout.write(`${node} `);

      for (const neighbor of graph[node]) {
        if (!visited[neighbor]) {
          stack.push(neighbor);
        }
      }
    }
  }
}

// Binary Tree DFS
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function DFSBinaryTree(root: TreeNode | null): void {
  if (!root) {
    return;
  }
  const stack: (TreeNode | null)[] = [];
  stack.push(root);

  while (stack.length > 0) {
    const node: TreeNode | null = stack.pop()!;
    if (node !== null) {
      process.stdout.write(`${node.val} `);

      if (node.right !== null) {
        stack.push(node.right);
      }
      if (node.left !== null) {
        stack.push(node.left);
      }
    }
  }
}