# 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.

170 questions
Filter by
Sorted by
Tagged with
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 ...
66 views

### Closest Pair heuristics, graph with adjacency matrix in C++17

I was trying to solve a problem that was briefly mentioned at the beginning of the "The Algorithm Design Manual" by Steven Skiena (Ch 1, Problem 26). It took me some time to build a working ...
234 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 ...
449 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. ...
2k views

### Recursive, depth first search

I wanted to write a function findDeep that would perform a recursive, depth-first search on plain objects and arrays. Comments and criticism welcome. ...
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 ...
399 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 ...
423 views

### Finding cycles in a graph that pass through a vertex at most k times

I have a project that relies on finding all cycles in a graph that pass through a vertex at most k times. Naturally, I'm sticking with the case of k=1 for the sake of development right now. I've come ...
36k views

### Depth First Search and Breadth First Search in C++

I am trying to learn DFS and BFS. However, I just want to make sure that I am not doing anything wrong. Would you please determine if the BFS and DFS functions are correct? ...
661 views

### Basic graph traversals

Below is an implementation of two graph traversals. Graph constructor creates a random graph with a fixed number of edges (fixed as a proportion of the maximum number of vertices, ...
546 views

### Javascript Tree Class

I got caught in the trap of implementing my own data structure. I've created a very general tree structure, where each node gets one parent, some children, and holds a value. I'm mostly looking for ...
1k 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: ...
65 views

### Sudoku solver using backtracting and depth-first-search

I've recently finished my first ever C program. I implemented a Sudoku solver that uses backtracking. Does my code look like a proper C-program? Are there any recommendations for improving my code? <...
162 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 ...
854 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(...
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? ...
3k views

### Finding a loop in a directed graph in Python

I wrote this code to find if a directed graph contains a loop or not. I am pretty new to graphs and I saw some examples on the internet but couldn't actually understand their implementations. So I ...
60 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 ...
653 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 ...
103 views

### LeetCode 839: Similar String Groups II

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time! Problem Two strings X and Y are similar if we can swap two letters (in different positions) ...
403 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 ...
125 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 ...
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. ...
5k views

### Java cycle detection using DFS in an undirected graph

I am doing interview studies and can't find a simple DFS for a cycle-finding algorithm. I want someone to tell me if my DFS algorithm works and how it can be improved. Where can you get a typical ...
128 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 ...
537 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 ...
4k views

### Get all combination of a nested object

I have JSON data which can be an object/array of recursively nested object or array. The value of an array can not be null, but a value in an object can be null. And I would like to return all ...
102 views

### A generic DFS in JavaScript

I implemented a general function for a depth-first-search (DFS) using JavaScript with default arguments and functions that need to be provided in order for it to work. This function is using ...
2k 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 ...
341 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 ...
425 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 ...
2k 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 ...
138 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 ...
39 views

### Detecting a cycle in a directed graph via an adjacency list implementation and a recursive DFS

Here's my attempt. I iterate through each vertex in the graph and do a DFS to see if I reach back on a vertex I already visited in this vertex's iteration. It seems to work but I am not satisfied with ...
55 views

### Creating valid words on an n-by-n grid of characters using depth-first search

I am trying to create a word-finder game. There will be an n-by-n Board filled with Tiles. ...
2k views

...
905 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 ...
639 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 ...
233 views

### DFS algorithm too slow

I am practicing my coding on leetcode, and my submission, although correct for small cases, is timing out for large ones. Could you please let me know how to improve my code? The question is as ...
76 views

### Finding all backedges in an undirected graph

I have tried to implement the DFS algorithm to find all the back-edges in a graph that lead to a cycle in the graph: ...
53 views

### Find the lengths of strongly connected components in a graph

I wrote a code to calculate the lengths of strongly connected components in a graph. The results I get are correct but it scales horribly. This is the code I have. I understand that the runtime ...
355 views

### Maze path finder using Depth-First Search algorithm

I'm trying to resolve this kata from CodeWars. Kata exercise You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). ...
45 views

### Javascript Tree Class 2

This question is the second version of the code here. I'm writing a general tree class. Specifically, each node should have oen parent, some number of children, and hold a value. I'm looking for ...
739 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 ...
160 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 ...
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 ...
848 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 ...
186 views

### Yet another graph search

I noticed there were already countless implementations of graphsearch procedures on here, but there were a couple of features of my approach that I haven't seen in the others, plus I would greatly ...