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.
175 questions
4
votes
1
answer
2k
views
(Leetcode) 24 game in Python
This is a Leetcode problem -
You have 4 cards each containing a number from 1 to 9. You need to
judge whether they could be ...
- 2,485
5
votes
1
answer
227
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,253
4
votes
1
answer
2k
views
Find all concatenated words in a given list of words
This is a Leetcode problem -
Given a list of words (without duplicates), write a program that
returns all concatenated words in the given list of words.
A concatenated word is defined as a ...
- 2,485
2
votes
2
answers
263
views
Leetcode: Flatten binary tree to linked list C#
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
Please comment on performance
Given a binary tree, flatten it to a linked list in-place.
For example, given the following ...
- 5,253
4
votes
1
answer
176
views
Return all valid paren strings with a given length
The problem is
Given a non-negative integer n, return all valid parentheses strings
with n open parens and ...
- 175
3
votes
1
answer
305
views
Find number of islands Leetcode
Here is the question:
Given a 2d grid map of '1's (land) and '0's (water), count the number
of islands. An island is surrounded by water and is formed by
connecting adjacent lands horizontally ...
- 769
3
votes
1
answer
4k
views
Java Maze Solver (DFS)
I was asked to create a Java program that will navigate through a series of mazes. I would like to know if this is the optimal way of using a DFS or is there a better way and I am doing something ...
- 33
4
votes
1
answer
97
views
Find the longest connect cells region per color
I have been studying graphs/BFS/DFS. working on wrapping my head around the following problem
Given a grid [m,n] where each cell has a value denotes a color, find the longest connected region that ...
- 171
4
votes
1
answer
177
views
Two versions of Word Break II - exhaustive combinations
I am solving Word Break II from leetcode:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty ...
- 313
10
votes
2
answers
4k
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: ...
- 313
1
vote
1
answer
1k
views
Count number of islands 2d grid
This is a recursive approach using DFS to counting the number of islands. However, I would like to improve performance, while keeping the code clean concise and readable. Better yet can this be solved ...
- 586
2
votes
0
answers
75
views
DFS logic to traverse a graph
I tried to literally convert recursive algorithm taught here to iterative, by simulating the recursive stack exactly as much as possible.
I have tested my code and it passed all test cases.
Please ...
- 121
5
votes
1
answer
16k
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 ...
- 2,489
2
votes
0
answers
792
views
Max flow Ford-Fulkerson using DFS augmented path retrieval
I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably?
...
0
votes
1
answer
2k
views
Depth First Search of graph in Python
Task: Do DFS traversal from a given given graph and print output.
Is this code the correct implementation of DFS traversal in Graph?
...
- 1,769
6
votes
2
answers
3k
views
DFS in a binary tree
Problem statement: Perform a depth first traversal on a BST and print the elements traversed.
...
- 1,769
7
votes
1
answer
793
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\$.
...
- 173
2
votes
1
answer
13k
views
Directed Graph Implementation in Java
Here I've attached my java implementation of a directed graph. I've used a modified adjacency-list mechanic to utilize a map instead of a list for quicker lookup times. Looking for comments / ...
- 131
2
votes
1
answer
2k
views
Binary Search Tree Implementation in Java
Looking for critiques on my BST implementation, particularly to check if I'm building the common operational methods and traversal algorithms properly. Code has been lightly tested, and I've tried to ...
- 131
5
votes
1
answer
2k
views
DFS implementation
I implemented DFS using recursion in Go. When I dfs the graph, I am able to get the path of traversal. But I'm unsure what else could I add to this DFS in order to make the search better.
Also, Is ...
- 175
3
votes
2
answers
5k
views
1
vote
1
answer
487
views
I want to check neighborhoods of cell in two dimensional array in C++
I want to write a function which will return all possible/valid 'X' moves around my Target cell depending on it position inside the following two dimensional array.
...
- 19
0
votes
1
answer
354
views
At least 2 paths down the binary tree have the same sum
Problem statement
Write a function that given a binary tree, returns true if at least 2 paths down the tree have the same sum. A path is a series of nodes from the root to the leaf.
Examples:
...
- 2,396
4
votes
1
answer
674
views
Longest Increasing Path in a Matrix from leetcode
Solved this:
Given an integer matrix, find the length of the longest increasing
path.
From each cell, you can either move to four directions: left, right,
up or down. You may NOT move ...
- 737
2
votes
0
answers
413
views
BinaryTree traversed in postorder (DFS), iteratively
I was given this coding question for a technical interview:
Given a binary tree, implement a method to populate the list
post_ordered_list with the data of the nodes traversed in postorder,
...
- 2,489
5
votes
1
answer
6k
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 ...
- 2,396
3
votes
1
answer
250
views
templated Depth-FirstSearch algorithm
I have worked on a simple iterative implementation of the common DFS algorithm for my personal template library. The algorithm itself works, but I try to get a feeling for how to seperate the data and ...
- 771
3
votes
1
answer
2k
views
Breadth- and Depth- First Search in C#
Another recreational implementation for review! As a side comment, for some reason I just feel like if (visited.Contains(vertex)) { .. } isn't necessary, as this ...
- 3,137
4
votes
0
answers
7k
views
Make DFS Implementation faster for 8 puzzle problem in Python
I am implementing DFS algorithm for the 8 puzzle problem which works fine if the goal is reached in less than 10 iterations. But for longer number of iterations, my implementation doesn't return the ...
- 41
1
vote
2
answers
632
views
Depth-first search of a graph in C# (HackerRank problem)
I'm trying to solve a problem from HackerRank. I got the correct algorithm, but it seems to be too inefficient. After checking the code with 10 given test cases, 3 cases are good and 7 return a ...
- 11
4
votes
2
answers
1k
views
Given two words and a dictionary's word list, find all shortest transformation sequence
This is a leetcode problem (https://leetcode.com/problems/word-ladder-ii/description/)
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(...
- 539
6
votes
1
answer
687
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 ...
- 357
5
votes
1
answer
417
views
Depth-first Search Non-Reursive Implementation in Clojure
I've created a non-recursive dfs implementation in Clojure. I'm using the wikipedia article on dfs as a guide. I'm very new to Clojure and functional programming in general. Any tips to improve ...
- 53
3
votes
1
answer
2k
views
"The Story of a Tree" solved using depth-first search
Found this problem in hackerrank.
One day Bob drew a tree, with \$n\$ nodes and \$n-1\$ edges on a piece of paper. He soon discovered that parent of a node depends on the root of the tree. The ...
- 205
4
votes
0
answers
374
views
Skiena's DFS on unweighted graphs, in Python 3, with adjacency-list implementation
In the Algorithm Design Manual (2nd ed) pp 172 - 173, Skiena writes:
As algorithm design paradigms go, a depth-first search isn't
particularly intimidating. It is surprisingly subtle, however
...
- 608
4
votes
1
answer
1k
views
Find Eulerian Tour Algorithm - with multithreading and random permutations
After struggling for a long while on this through the algorithms course on Udacity, I finally understood enough of the concept to develop this implementation. However, it lacks efficiency and finesse. ...
user141472
11
votes
3
answers
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-...
- 113
7
votes
2
answers
1k
views
6
votes
1
answer
519
views
Hackerrank - Maximum Disjoint Subtree Product
Problem statement
We define an unrooted tree, T, with the following properties:
T is a connected graph with nodes ...
- 2,396
7
votes
1
answer
750
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 ...
- 2,572
4
votes
2
answers
818
views
Find the longest rectilinear path in a matrix with descending entries
Problem (Skiing):
Each number represents the elevation of that area of the mountain.
From each area (i.e. box) in the grid, you can go north, south, east,
west - but only if the elevation ...
- 157
4
votes
2
answers
2k
views
Depth and breadth first search
I am practicing interview questions, I wrote this code to perform BFS and DFS on a graph in Python.
How can it be optimized, and how can it be made more readable?
...
- 1,291
5
votes
1
answer
125
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 ...
- 167
9
votes
1
answer
4k
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 ...
- 195
7
votes
1
answer
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 ...
- 440
3
votes
1
answer
840
views
Ternary tree preoder traversal (recursive implementation)
Problem statement:
Print out to console the ternary tree preorder traversal. Suppose that the tree can have at most 3 children, left, middle and right. Preorder traversal is to visit the middle ...
- 2,396
7
votes
1
answer
1k
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.
...
- 2,396
1
vote
1
answer
870
views
Depth First Search (Adjacency List) in JavaScript
I am trying to implement a DFS search and graphs. How can I make it better?
...
- 199
6
votes
1
answer
8k
views
Graph and Node classes with BFS and DFS functions
I've created a Node class and a Graph class
...
- 440
3
votes
2
answers
1k
views
CLRS Implementation of BFS and DFS in C++
I tried to implement BFS and DFS from Introduction to Algorithms by Cormen. Any suggestions on how to improve my code?
GraphStructures.h
...
- 85