Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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
1 vote
1 answer
785 views

Depth First Search (Adjacency List) in JavaScript

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

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
user avatar
  • 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 ...
user avatar
  • 85
5 votes
1 answer
516 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. ...
user avatar
1 vote
1 answer
658 views

Return a path between graph nodes using depth-first search redo

I previously attempted to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. This is my latest attempt at this ...
user avatar
2 votes
1 answer
7k views

Return path between graph nodes using depth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. I'm doing this to improve my style ...
user avatar
2 votes
2 answers
480 views

A Scala Maze Generator in Functional Style

I'm wondering if there is more I can do to incorporate more idiomatic scala and functional programming principles. I know the maze itself is mutable but i didn't see an easy solution to making it ...
user avatar
  • 155
10 votes
2 answers
2k views

2D grid Hamiltonian path puzzle solver

The puzzle goes like this: in a rectangular 2D grid there are empty spaces (.), exactly one starting point (S, ...
user avatar
  • 201
2 votes
1 answer
102 views

File search program not efficient enough

I have created a program to search for a file in the computer. But I feel it can be improved. Can anyone help me with this? filesearch.py ...
user avatar
  • 185
11 votes
1 answer
2k views

Yet another minimax tree for TicTacToe

I have written a working minimax tree for Tic-Tac-Toe. What I have done so far is create a tree with end node having value 10, 0 or -10 base on win, lose or draw. After I create a tree I then ...
user avatar
  • 215
2 votes
1 answer
4k views

Pattern searching in 2d grid

This is an interview question which i am trying to solve. You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all ...
user avatar
1 vote
1 answer
12k views

C++ Maze Generator

I have made a random maze generator that allows for custom sizes via command arguments. It uses depth-first search and is written is C++. Could you look over my code and suggest any improvements ...
user avatar
  • 165
2 votes
1 answer
67 views

ExtensionMethods for iterating hierarchically data structures depth/breath-first

I wrote a few simple extension methods that allow to traverse a hierachically data structure depth-first or breath-first using LINQ: Usage: ...
user avatar
  • 8,498
1 vote
0 answers
720 views

Graph (adjacency list) and DFS (topological sort)

The vertices on the graph are numbers from 0 to |V| - 1 for convenience. I was thinking later to use a template wrapper for the graph. Graph.h: ...
user avatar
  • 2,964
7 votes
2 answers
9k views

C++ Graph Class Implementation (adjacency list)

I've got a barebones C++ graph class implemented as an adjacency list. The graph consists of a vector of vertices. Each vertex has a vector of outgoing edges that store the destination vertex id. ...
user avatar
  • 135
6 votes
0 answers
738 views

Pseudo-parallel depth-first search

I'm writing a small program that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel depth-first search (dfs) on it. ...
user avatar
0 votes
1 answer
4k views

C++ - printing a binary tree vertically, Depth first [closed]

...
user avatar
  • 19
2 votes
1 answer
5k views

Searching a maze using DFS in C++

I have started learning recursion and search algorithms, especially DFS and BFS. In this program, I have tried to make an implementation of a maze-solving algorithm using DFS. The program is working ...
user avatar
  • 31
8 votes
2 answers
2k views

Make Depth First Search program more time efficient

This is a problem from programming contest. The original problem can be found here on hackerearth.com. In the first line there is one integer T denoting the number of test cases. Description of T ...
user avatar
  • 303
6 votes
1 answer
1k views

Topological sort using recursive DFS

I am currently learning Graph algorithms by solving questions on online judges. The below code is for implementing Topological sort, using recursive DFS. Also, it is my first time with C++ STL. ...
user avatar
2 votes
1 answer
336 views

Get all combination of a nested object with arbitrary levels

I have a JSON data which can be an object/array of recursively nested object or array. The value of an array can not be null, but an value in a object can be null. I would like to return all ...
user avatar
  • 165
4 votes
1 answer
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 ...
user avatar
  • 165
3 votes
1 answer
261 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 ...
user avatar
6 votes
1 answer
118 views

Find the largest continuous descending sum in a 2d matrix

Given a 2d array, the problem is to find the largest sum, where each subsequent is >= the previous digit but < all of the 'neighbour' digits. You can only move up, down, left and right. My ...
user avatar
  • 121
2 votes
1 answer
2k views

Iterative depth-first search and topological sort in Java

This is the iterative depth-first search, that does not abuse the stack. Also, I gathered some information from DFS that may be useful; for example, I am able to do topological sort using the result ...
user avatar
  • 25.3k
1 vote
2 answers
953 views

Get a nested property of a complex object at any level of depth

Given a complex object (with nested objects at any depth) I need to be able to quickly retrieve a value for a given property name. I have designed the following ...
user avatar
  • 667
1 vote
2 answers
2k views

Traversing a stack in my DFS algorithm for finding a path in a maze

I am trying to get this code running as fast as possible when traversing through my stack of my DFS currently the input files are like so: ...
user avatar
  • 131
9 votes
1 answer
1k views

Graph theory using C++ STL

I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object. Any feedback would be ...
user avatar
  • 393
4 votes
2 answers
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 ...
user avatar
  • 65
5 votes
1 answer
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. ...
user avatar
  • 672
3 votes
0 answers
4k views

Depth first search implementation

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the depth first search section (5.8) using javascript. Note you can execute the code here if you don't ...
user avatar
3 votes
1 answer
84 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: ...
user avatar
  • 277
3 votes
1 answer
6k views

Breadth and Depth First Search in Ruby

I was tasked with building three individual methods; one to create a Binary Search Tree (BST), one to carry out a Breadth First Search (BFS), and one to carry out a Depth First Search (DFS). Create ...
user avatar
  • 571
5 votes
4 answers
5k views

Path sum in binary tree

Root to leaf path sum equal to a given number Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given ...
user avatar
  • 439
6 votes
4 answers
3k views

Java Recursive Depth First Search

I've created a recursive depth-first search implementation in Java as an example for an article I am writing on my website. It needs to be concise in order to fit on the page easily (independent of ...
user avatar
5 votes
5 answers
11k views

DFS in Binary Tree

I have written this code for DFS in a binary tree and would like improvements on it. ...
user avatar
  • 439
2 votes
1 answer
4k views

Iterative deepening depth-first search heuristics to solve "3 Missionary And Cannibal" challenge

Missionaries and cannibals problem is a well known Toy Problem to learn basic AI techniques. I implemented it using iterative deepening depth-first search algorithm. My state is represented by a 3-...
user avatar
8 votes
1 answer
1k views

Search iteratively in a ternary search tree

I was trying to write an iterative search function for my Ternary Search Tree class based on a pseudo-code, and now it seems to work, but I think it can definitely be improved. ...
user avatar
12 votes
3 answers
421 views

Kosaraju in Scala

I started coding in Scala some time ago, and also learning some fundamental algorithms in CS. Here's a terribly slow implementation of Kosaraju algorithm to find strongly connected components in a ...
user avatar
  • 161
1 vote
0 answers
761 views

Depth First Search for percolation to find clusters in Go game

I have some questions about Depth First Search and whether I implemented it correctly. Below is a more thorough discussion. The graph in question is a randomly colored square grid (I use 3 colors). ...
user avatar
3 votes
1 answer
112 views

Directed graph path enumerator in Java - follow-up

I have refactored the graph path enumerator. DirectedGraphNode was not changed, so refer to the link above in case you want to have a look at it. The node type is ...
user avatar
  • 25.3k
2 votes
2 answers
2k views

Java DFS Implementation that tracks time and parent node

I have a project where I'm to implement a DFS using a direct graph. The implementation should print the currently visited vertex, the parent (the node from which the current node was reached), and the ...
user avatar
4 votes
2 answers
732 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, ...
user avatar
  • 581
0 votes
1 answer
228 views

Project Euler#18: Maximum Paths I: Brute Forced Depth First Search

Problem: Data: ...
user avatar
  • 1,426
2 votes
1 answer
3k views

Iterative depth first search using adjacency matrix

I have written code for graph traversal using adjacency matrices in an iterative approach. The code should print the graph in a DFS way. ...
user avatar
2 votes
0 answers
135 views

AI for depth-first walking in a maze, with variable depth look ahead search for dead ends and finish point

This code is a part of a little game I've started a week ago. It is too extensive to review at once, so I'm picking the most interesting and crucial parts. Start with the AI. It has public update ...
user avatar
13 votes
1 answer
1k views

Detecting cycles in a directed graph without using mutable sets of nodes

I recently came across the classic algorithm for detecting cycles in a directed graph using recursive DFS. This implementation makes use of a stack to track nodes currently being visited and an extra ...
user avatar
8 votes
2 answers
2k views

Equivalent binary trees (A Tour of Go)

Any suggestions on how to improve the code shown below for the Go-tour exercise? Exercise description: There can be many different binary trees with the same sequence of values stored at the ...
user avatar
  • 127
8 votes
1 answer
987 views

Functional tree iteration in Common Lisp

I'm adding some functionality to an existing library of data structures in Common Lisp, with a view to asking the original author if I can take over maintenance and development of it. While the ...
user avatar
3 votes
1 answer
192 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 ...
user avatar
  • 295