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
2
votes
2answers
132 views

Ruby implementation for Hacker Rank connected cells in a grid

https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem problem statement: Consider a matrix where each cell contains either a 1 or a 0. Any cell containing a 1 is called a ...
2
votes
1answer
28 views

Find articulation points/ cut vertices in graph

I would like to get some feedback on my completed code that finds and displays the articulation vertices in an undirected graph. I included a test case within the code, it should (and does) print <...
1
vote
0answers
47 views

Graph-coloring solution using depth-first search

I'm trying to solve this question: Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them. The park consists of n ...
4
votes
2answers
61 views

Finding a vertex of a tree such that every subtree rooted at that vertex is of a uniform color

I'm trying to optimally solve codeforces problem 763A: Each New Year Timofey and his friends cut down a tree of n vertices and bring it home. After that they paint all the n its vertices, so ...
2
votes
2answers
118 views

Find all possible words in a board of characters

This question has 2 possible solutions and I am trying to implement the DFS solution. Here is the Trie and DFS solution: Boggle using Trie and DFS Please review for performance. Given a ...
1
vote
1answer
77 views

(Leetcode) Freedom Trail

I would like to know whether I could make my solution to this challenge shorter and more efficient. Below is the description of the challenge (this is a Leetcode problem) - In the video game ...
5
votes
2answers
115 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' ...
4
votes
1answer
53 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 ...
3
votes
1answer
128 views

Add and Search Word

This is a Leetcode problem: Design a data structure that supports the following two operations: void addWord(word) ...
3
votes
1answer
64 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
votes
2answers
71 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 ...
4
votes
1answer
158 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 ...
3
votes
1answer
49 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 ...
3
votes
1answer
452 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 ...
1
vote
0answers
40 views

Choose numbers from a grid, minimising the sum

Given a 2-D input matrix, I need to pick elements from it. constraint: you can pick one number at each row, each column given: number boards are given expected output: print least sum of ...
4
votes
1answer
56 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 ...
1
vote
0answers
63 views

I have written two versions of Word Break exhaustive combinations. Please comment

I am solving Word Break II from leetcode. https://leetcode.com/problems/word-break-ii/description/ Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add ...
9
votes
2answers
838 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: ...
1
vote
1answer
426 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 ...
2
votes
0answers
66 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 ...
5
votes
1answer
3k 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
votes
0answers
382 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
1answer
1k 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? ...
6
votes
2answers
2k views

DFS in a binary tree

Problem statement: Perform a depth first traversal on a BST and print the elements traversed. ...
7
votes
1answer
479 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\$. ...
1
vote
0answers
770 views

Depth First Search using Adjacency List

My aim to implement adjacency list correctly. After takin help from here, I have implemented it. I have tried to implement it here, but it was suggested that it is most likely adjacency matrix. Help ...
1
vote
1answer
6k 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 / ...
2
votes
1answer
619 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 ...
3
votes
1answer
732 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 ...
1
vote
0answers
80 views

Ruby Sudoku Solver without classes

I'm writing a Sudoku solver in Ruby to complete a coding challenge with the following restrictions. Failing to follow the following restrictions will result in an invalid submission: Do ...
2
votes
2answers
667 views

DFS implementation in Rust

...
1
vote
1answer
183 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. ...
0
votes
1answer
239 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: ...
1
vote
0answers
112 views

Timeout on Python code to count connected components on HackerRank

I'm trying to solve the "Roads and Bridges" problem on HackerRank https://www.hackerrank.com/challenges/torque-and-development/problem I believe the code works, but just needs to be optimized for ...
4
votes
1answer
359 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 ...
2
votes
0answers
312 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, ...
5
votes
1answer
2k 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 ...
3
votes
1answer
108 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 ...
3
votes
1answer
1k 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 ...
4
votes
0answers
431 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 ...
1
vote
2answers
285 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 ...
3
votes
2answers
606 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(...
6
votes
1answer
356 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 ...
5
votes
1answer
165 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 ...
3
votes
1answer
277 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 ...
3
votes
0answers
211 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 ...
4
votes
1answer
733 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. ...
10
votes
3answers
2k 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-...
7
votes
2answers
986 views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
5
votes
1answer
279 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 ...