Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

-4
votes
0answers
17 views

LeetCode 773. Sliding Puzzle - DFS Logic [on hold]

I tried to solve the LeetCode Sliding Logic Puzzle using BFS and DFS. My BFS solution worked, but my DFS solution did not ... and I cannot figure out why. Here is the original question: https://...
3
votes
1answer
136 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
36 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
53 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
56 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
730 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
279 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 ...
0
votes
0answers
163 views

Depth-First Search tree traversal in JavaScript

Given a graph and a starting vertex print the value of each vertex in a depth-first order. I include the code for DFS iteratively by solving the starter problem of traversing and printing values ...
2
votes
0answers
63 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
313 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
917 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
1k views

DFS in a binary tree

Problem statement: Perform a depth first traversal on a BST and print the elements traversed. ...
7
votes
1answer
411 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
701 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
4k 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
484 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
601 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
76 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 ...
1
vote
2answers
518 views
1
vote
1answer
179 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
207 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
103 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
309 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
284 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, ...
4
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 ...
2
votes
1answer
94 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 ...
2
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
405 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
270 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
503 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
322 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
143 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
229 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
168 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
654 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
924 views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
5
votes
1answer
260 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 ...
7
votes
1answer
383 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 ...
4
votes
2answers
461 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 ...
4
votes
2answers
1k 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? ...
5
votes
1answer
69 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 ...
8
votes
1answer
1k 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 ...
5
votes
1answer
2k 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
568 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 ...
1
vote
1answer
452 views

Depth First Search (Adjacency List) in JavaScript

I am trying to implement a DFS search and graphs. How can I make it better? ...
7
votes
1answer
4k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
3
votes
2answers
618 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 ...
3
votes
1answer
320 views

Snakes and Ladders using a magic die

This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game. ...