Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# 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.

180 questions
Filter by
Sorted by
Tagged with
1 vote
593 views

### Minesweeper algorithm that works within O(1) space complexity

For minesweeper algorithm, instead of the most obvious BFS or DFS solution, I want a O(1) space solution. First of all, I'll explain how the program works. I will pass in a 2D array, with 1 ...
3k views

### PHP implementation of "depth-first search" on the graph data structure

As I am a totally self-taught 'person writing code', I decided to learn algorithms with one online course that taught them using Java for demonstrative purposes. The first topic I covered is the graph ...
• 185
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: ...
• 313
212 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 ...
414 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 ...
• 171
982 views

### DFS Undirected Graph

The code included below was written in response to a programming exercise that was sent to me by a company that I am applying to. The purpose of the code is explained at this link. This code passes ...
• 21
36k views

### Depth First Search and Breadth First Search in C++

I am trying to learn DFS and BFS. However, I just want to make sure that I am not doing anything wrong. Would you please determine if the BFS and DFS functions are correct? ...
• 381
1 vote
383 views

### Python script to convert hierarchical JSON to LaTeX itemize

I have the following JSON: ...
• 247
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 ...
• 417
428 views

### Finding cycles in a graph that pass through a vertex at most k times

I have a project that relies on finding all cycles in a graph that pass through a vertex at most k times. Naturally, I'm sticking with the case of k=1 for the sake of development right now. I've come ...
2k views

### Iteratively-Deepening Depth First Search (queue and non-queue)

I am aware that most 'generic' BFS algorithms that use a queue also check for uniqueness of visitation to 'speed things up' as it were, but I'm a bit unclear as to how to implement such a method as I'...
• 143
1k views

### Parse a tree & return the various paths

Input: { 1: [2,3], 2:[4], 3: [5,6], 4:[6] } Expected output: [[1, 2, 4, 6], [1, 3, 5], [1, 3, 6]] My Code: ...
• 153
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 ...
• 712
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? ...
• 5,249
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 ...
• 305
679 views

### has_cycle in directed and undirected graphs

I wrote a program that can tell if a graph has_cycle or not. Can you please suggest more elegant and eloquent ways for this program? (Perhaps better ways to represent a graph with vertices and edges?)...
• 161
1 vote
7k views

### DFS on a binary tree: marking nodes as visited

I wanted to write depth first search reversal iteratively in Java. Can someone review my code? I'm not that much interested in naming of the variables, but in the structure of the code, i.e. I don't ...
• 861
6k views

### Nsum problem: find all n elements in an array whose sum equals a given value

I am pretty new to Python, so I want to listen to any advice that improve my coding style in a "pythonic" way, even about naming style of variables. The following code reflects a very general paradigm ...
• 123
1 vote
240 views

### Code duplication for just an if condition

I have two methods that are near-perfect duplicates. There is of course a code smell. The only thing that changes is the condition to increment a variable. Language: Java7 ...
• 239
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'...
• 419
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 ...
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 ...
• 624
1 vote
1k views

### Depth first search, use of global variables, and correctness of time

As I was coding this algorithm I found that some variables that are meant to be global behave as they are intended to behave, but others do not. Specifically, my boolean arrays, e.g. ...
673 views

### How to enumerate the internal nodes and leaves of a tree more elegantly?

Might there be a simpler way to write this code? I'd like to learn to write code more efficiently. ...
• 161
10k 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? ...
• 161
1 vote
1k views

### DFS algorithm with generators

Background: I was working on a project were I needed to write some rules for text-processing. After working on this project for a couple of days and implementing some rules, I realized I needed to ...
• 497
6k views

### Java cycle detection using DFS in an undirected graph

I am doing interview studies and can't find a simple DFS for a cycle-finding algorithm. I want someone to tell me if my DFS algorithm works and how it can be improved. Where can you get a typical ...
• 141
13k views

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

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