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
24
votes
4answers
186k 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 ...
21
votes
1answer
25k 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: ...
13
votes
1answer
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 ...
12
votes
3answers
406 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 ...
12
votes
1answer
326 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: ...
11
votes
2answers
1k 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 ...
11
votes
1answer
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 ...
11
votes
3answers
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-...
10
votes
2answers
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: ...
10
votes
2answers
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, ...
9
votes
1answer
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 ...
9
votes
1answer
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 ...
8
votes
4answers
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 ...
8
votes
3answers
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 ...
8
votes
2answers
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 ...
8
votes
1answer
988 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. ...
8
votes
1answer
897 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 ...
7
votes
2answers
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 ...
7
votes
2answers
205 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 ...
7
votes
1answer
814 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. ...
7
votes
2answers
1k views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
7
votes
1answer
651 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\$. ...
7
votes
1answer
393 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 ...
7
votes
1answer
665 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 ...
6
votes
2answers
3k views

DFS in a binary tree

Problem statement: Perform a depth first traversal on a BST and print the elements traversed. ...
6
votes
2answers
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 ...
6
votes
3answers
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'...
6
votes
4answers
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 ...
6
votes
1answer
68 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 ...
6
votes
2answers
8k 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? ...
6
votes
1answer
543 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 ...
6
votes
2answers
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. ...
6
votes
1answer
177 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 ...
6
votes
1answer
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. ...
6
votes
1answer
104 views

01 Matrix is too slow when solved using DFS

I tried solving Leetcode 01 Matrix problem. It is running too slow when solved using DFS approach. Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance ...
6
votes
1answer
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 ...
6
votes
1answer
5k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
6
votes
0answers
344 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 ...
6
votes
0answers
672 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. ...
5
votes
5answers
11k views

DFS in Binary Tree

I have written this code for DFS in a binary tree and would like improvements on it. ...
5
votes
3answers
21k 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
votes
2answers
198 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 ...
5
votes
2answers
547 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' ...
5
votes
2answers
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 ...
5
votes
1answer
13k views

DFS/BFS implementation of Cormen's pseudo code

This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this. ...
5
votes
1answer
161 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) ...
5
votes
1answer
10k 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 ...
5
votes
1answer
111 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 ...
5
votes
1answer
4k 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 ...
5
votes
1answer
75 views

Given a binary tree, \$T\$ whose nodes have positive values, find the value of the maximal path

Problem Problem is Maximum sum path from https://firecode.io Given a binary tree, \$T\$, whose nodes have positive values find the value of a maximal path. A path is a simple path from a node to ...