# Questions tagged [depth-first-search]

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

178 questions
Filter by
Sorted by
Tagged with
187k views

### Depth First Search & Breadth First Search implementation

I've implemented DFS and BFS implementations. I want to check if the code is readable, contains any issues, and can be improved. GraphImplementation ...
28k views

### Check if a directed graph contains a cycle

I am trying to optimize execution time of this function which detects cycle in a directed graph: ...
1k views

### Detecting cycles in a directed graph without using mutable sets of nodes

I recently came across the classic algorithm for detecting cycles in a directed graph using recursive DFS. This implementation makes use of a stack to track nodes currently being visited and an extra ...
413 views

### Kosaraju in Scala

I started coding in Scala some time ago, and also learning some fundamental algorithms in CS. Here's a terribly slow implementation of Kosaraju algorithm to find strongly connected components in a ...
328 views

### Depth-first search method for searching for all "superpalindromes" whose prime factors are all <=N

A question was asked over at math.SE (here) about whether or not there are infinitely many superpalindromes. I'm going to rephrase the definition to a more suitable one for coding purposes: ...
2k views

### Speed up Sudoku Solver

I made this Sudoku solver using depth first search, it takes less than 0.1 second to solve any simple solution(no guessing), but if the solution requires guessing (thus using the DFS) its time grows ...
2k views

### Yet another minimax tree for TicTacToe

I have written a working minimax tree for Tic-Tac-Toe. What I have done so far is create a tree with end node having value 10, 0 or -10 base on win, lose or draw. After I create a tree I then ...
3k views

### Depth First Search Implementation (iterative)

Here is my code for Depth First Search and, as far as I know, it is working fine on most cases. It is not very efficient as I have implemented it for the very first time.. Warning: It is only for bi-...
3k views

### Generating the powerset in C

I am solving another problem in leetcode. Given a set, generate all the subsets of the set. Input: [1,2,3] Output: ...
1k views

### 2D grid Hamiltonian path puzzle solver

The puzzle goes like this: in a rectangular 2D grid there are empty spaces (.), exactly one starting point (S, ...
3k views

### Hacker Rank: Journey to the Moon (Graph Theory)

I am attempting to complete the "Journey to the Moon" problem described below: There are N trained astronauts numbered from 0 to N-1. But those in charge of the mission did not receive ...
1k views

### Graph theory using C++ STL

I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object. Any feedback would be ...
49k views

### Depth-first search in Python

I wrote this DFS in Python and I was wondering if it correct. Somehow it seems too simple to me. Each node is a class with attributes: visited: Boolean ...
7k views

### Depth First Traversal of a Graph

I am learning how to implement a basic undirected graph and perform a depth first traversal. Please critique my code for correctness, best practices, security, and any other comments that may be ...
2k views

### Make Depth First Search program more time efficient

This is a problem from programming contest. The original problem can be found here on hackerearth.com. In the first line there is one integer T denoting the number of test cases. Description of T ...
1k views

### Search iteratively in a ternary search tree

I was trying to write an iterative search function for my Ternary Search Tree class based on a pseudo-code, and now it seems to work, but I think it can definitely be improved. ...
955 views

### Functional tree iteration in Common Lisp

I'm adding some functionality to an existing library of data structures in Common Lisp, with a view to asking the original author if I can take over maintenance and development of it. While the ...
3k views

### C++ implementation of depth-first search

I got the C++ implementation of depth-first search (DFS) from here and made slight modifications to it. The modified code is as follows: ...
2k views

### Equivalent binary trees (A Tour of Go)

Any suggestions on how to improve the code shown below for the Go-tour exercise? Exercise description: There can be many different binary trees with the same sequence of values stored at the ...
206 views

### Search for Tree

Here is a search implementation for my tree. It searches each node in a breadth-first manner first, but it goes deeper in a depth-first manner, in the event it needs to go deeper. I know there may ...
901 views

### Leetcode 17. Letter Combinations of a Phone Number

Problem Statement Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. ...
1k views

### DFS and BFS in a graph in C++

Here goes the depth first search: ...
8k views

### C++ Graph Class Implementation (adjacency list)

I've got a barebones C++ graph class implemented as an adjacency list. The graph consists of a vector of vertices. Each vertex has a vector of outgoing edges that store the destination vertex id. ...
675 views

### Cheapest flights with at most k stops

This is the Cheapest Flights Within K Stops problem from leetcode.com: There are $n$ cities connected by $m$ flights. Each fight starts from city $u$ and arrives at $v$ with a price $w$. ...
409 views

### Depth First Backtracking Puzzle Solver

There is this type of puzzle that can easily be solved with a depth-first backtracking solver. I wrote one in python 3.4 and like to get some feedback. I'm especially interested in the following ...
692 views

### A DFS sudoku solver

This is my attempt at a Sudoku solver using a DFS approach. I mainly developed it to become a better Rust developer, but if you have any performance tips, I will be glad to hear them :) My program ...
3k views

### BFS/DFS Web Crawler

I've built a web crawler that starts at an origin URL and crawls the web using a BFS or DFS method. Everything is working fine, but the performance is horrendous. I think the major cause of this is ...
3k views

### DFS in a binary tree

Problem statement: Perform a depth first traversal on a BST and print the elements traversed. ...
1k views

### Constructing a graph and performing a depth-first traversal

Please review the use of pointers and design in graph construction code and its depth first traversal. I haven't used smart pointers as I want to understand any issues in following implementation with ...
2k views

### Missing level of technical depth (Flatten Tree)

I recently have given a coding test in a reputable IT company. There were three coding questions. They refused me by saying that as we felt they didn't demonstrate the level of technical depth we'...
3k views

### Java Recursive Depth First Search

I've created a recursive depth-first search implementation in Java as an example for an article I am writing on my website. It needs to be concise in order to fit on the page easily (independent of ...
117 views

### Find the largest continuous descending sum in a 2d matrix

Given a 2d array, the problem is to find the largest sum, where each subsequent is >= the previous digit but < all of the 'neighbour' digits. You can only move up, down, left and right. My ...
9k views

### Returning a list of the values from the binary tree

I want to return a list of the values from the binary tree. Is there a shorter and more efficient way to write the method for numbers? ...
115 views

### Graph: Depth First Search (N citizens with pairs of friends)

I have solved problem 10608 on UVA Online Judge using Python 3.5.1. My solution works, but it takes too long to run when the online judge evaluates it. Problem There is a town with N citizens. It is ...
608 views

### Recursive Depth First Search for finding valid sudoku boards in Python 3

I am not an experienced programmer, and I decided to make a program that could find all possible sudoku arrangements just for fun. As far as I can see, the program is working all right, but I'd like ...
205 views

### Clojure depth first search maze problem from Classic CS Problems in Python Book

I am an experienced self-taught professional Python programmer working my way through the book Classic Computer Science Problems in Python to try to catch myself up on some of the things I missed by ...
1k views

### Topological sort using recursive DFS

I am currently learning Graph algorithms by solving questions on online judges. The below code is for implementing Topological sort, using recursive DFS. Also, it is my first time with C++ STL. ...
6k views

### Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
652 views

### Recursive and iterative implementation on Kosaraju algorithm

Kosaraju algorithm is mainly phrased as two recursive subroutines running postorder DFS twice to mark SCCs with linear time complexity O(V+E) below, For each vertex u of the graph, mark u as ...
725 views

### Pseudo-parallel depth-first search

I'm writing a small program that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel depth-first search (dfs) on it. ...
11k views

### DFS in Binary Tree

I have written this code for DFS in a binary tree and would like improvements on it. ...
248 views

### Optimize depth-first search for sliding tile puzzle

My current code implementing a depth-first search works well for puzzle 1. But my code is too slow; I think I use too many loops and I am not sure I am using the right data structure. So I have a ...
822 views

### (Leetcode) Minesweeper game

This is a Leetcode problem - Let's play the Minesweeper game (Wikipedia, online game)! You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' ...
22k views

### Graph Creation and BFS + DFS in C#

I was asked to implement a graph and BFS and DFS. Please comment. Is it understandable? Is my algorithm correct? Are there any optimizations? ...
4k views

### Path sum in binary tree

Root to leaf path sum equal to a given number Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given ...
3k views

### Depth First Search Using Stack in Python

I have implemented a depth first search using a stack (in a separate class). Any suggestions please on improvements for the below code: ...
13k views

### DFS/BFS implementation of Cormen's pseudo code

This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this. ...
167 views

### LeetCode: Add and Search Word C#

This is a Leetcode problem: Design a data structure that supports the following two operations: void addWord(word) ...
12k views

### Searching a maze using DFS and BFS in Python 3

I solved the problem posted from Make School Trees and Maze article, which asks me to searching a maze using DFS and BFS in Python. Here's the final output from PyGame: I would like to ask for code ...
5k views

### Sudoku solver recursive solution with clear structure

Problem statement Similar to Leetcode 37 Sudoku solver, the algorithm is to determine if the sudoku board can be filled with ‘1’,‘2’,…,‘9’. A sudoku board is represented as a two-dimensional 9x9 ...