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
24
votes
4answers
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
...
21
votes
1answer
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:
...
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
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 ...
12
votes
1answer
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:
...
11
votes
2answers
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 ...
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
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.
...
8
votes
1answer
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 ...
7
votes
6answers
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:
...
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
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 ...
7
votes
1answer
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.
...
7
votes
2answers
1k views
7
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. ...
7
votes
1answer
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\$.
...
7
votes
1answer
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 ...
7
votes
1answer
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 ...
7
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
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
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 ...
6
votes
2answers
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?
...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
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
6k views
6
votes
0answers
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 ...
6
votes
0answers
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.
...
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
2answers
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 ...
5
votes
2answers
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' ...
5
votes
3answers
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
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
2answers
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:
...
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
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)
...
5
votes
1answer
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 ...
5
votes
1answer
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 ...