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
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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. ...
5
votes
1answer
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. ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
4
votes
1answer
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? ...
4
votes
2answers
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, ...
4
votes
2answers
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 ...
4
votes
1answer
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: ...
4
votes
1answer
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? <...
4
votes
1answer
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 ...
4
votes
2answers
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(...
4
votes
2answers
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? ...
4
votes
2answers
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 ...
4
votes
1answer
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 ...
4
votes
2answers
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 ...
4
votes
1answer
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) ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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. ...
4
votes
1answer
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 ...
4
votes
2answers
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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 ...
3
votes
2answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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. ...
3
votes
2answers
2k views

DFS implementation in Rust

...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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: ...
3
votes
1answer
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 ...
3
votes
1answer
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). ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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
votes
2answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
3k views

PHP implementation of “depth-first search” on the graph data structure

As I am a totally self-taught 'person writing code', I decided to learn algorithms with one online course that taught them using Java for demonstrative purposes. The first topic I covered is the graph ...
3
votes
2answers
665 views

has_cycle in directed and undirected graphs

I wrote a program that can tell if a graph has_cycle or not. Can you please suggest more elegant and eloquent ways for this program? (Perhaps better ways to represent a graph with vertices and edges?)...