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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 185
21 votes
1 answer
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: ...
user avatar
  • 313
7 votes
2 answers
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 ...
user avatar
7 votes
1 answer
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 ...
user avatar
  • 171
2 votes
2 answers
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 ...
user avatar
  • 21
4 votes
1 answer
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? ...
user avatar
  • 381
1 vote
1 answer
383 views

Python script to convert hierarchical JSON to LaTeX itemize

I have the following JSON: ...
user avatar
  • 247
8 votes
4 answers
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 ...
user avatar
  • 417
5 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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'...
user avatar
  • 143
2 votes
2 answers
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: ...
user avatar
  • 153
11 votes
2 answers
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 ...
user avatar
5 votes
3 answers
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? ...
user avatar
  • 5,249
6 votes
2 answers
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 ...
user avatar
3 votes
2 answers
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?)...
user avatar
1 vote
2 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 123
1 vote
2 answers
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 ...
user avatar
  • 239
6 votes
3 answers
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'...
user avatar
  • 419
8 votes
3 answers
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 ...
user avatar
24 votes
4 answers
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 ...
user avatar
  • 624
1 vote
1 answer
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. ...
user avatar
0 votes
2 answers
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. ...
user avatar
  • 161
6 votes
2 answers
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? ...
user avatar
  • 161
1 vote
2 answers
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 ...
user avatar
  • 497
4 votes
1 answer
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 ...
user avatar
  • 141
5 votes
1 answer
13k views

DFS/BFS implementation of Cormen's pseudo code

This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this. ...
user avatar
  • 297
2 votes
1 answer
7k views

Breadth- and Depth-first search code

Here is my breadth-first search (bfs) and depth-first search (dfs) code for graph traversal. Please give me some constructive ...
user avatar
12 votes
1 answer
330 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: ...
user avatar

1 2 3
4