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
1answer
65 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: ...
1
vote
0answers
702 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: ...
6
votes
2answers
8k 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. ...
6
votes
0answers
672 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. ...
0
votes
1answer
4k views

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

...
2
votes
1answer
4k 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 ...
8
votes
2answers
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 ...
6
votes
1answer
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. ...
2
votes
1answer
305 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 ...
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 ...
3
votes
1answer
229 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 ...
5
votes
1answer
111 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 ...
2
votes
1answer
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 ...
1
vote
2answers
656 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 ...
1
vote
2answers
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: ...
9
votes
1answer
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 ...
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 ...
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. ...
3
votes
0answers
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 ...
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
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 ...
5
votes
2answers
4k 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 ...
6
votes
4answers
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 ...
5
votes
5answers
11k views

DFS in Binary Tree

I have written this code for DFS in a binary tree and would like improvements on it. ...
2
votes
1answer
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-...
8
votes
1answer
988 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. ...
12
votes
3answers
406 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 ...
1
vote
0answers
688 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). ...
3
votes
1answer
108 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 ...
2
votes
2answers
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 ...
4
votes
2answers
645 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, ...
0
votes
1answer
213 views

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

Problem: Data: ...
2
votes
1answer
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. ...
2
votes
0answers
134 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 ...
13
votes
1answer
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 ...
7
votes
2answers
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 ...
8
votes
1answer
897 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 ...
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 ...
1
vote
1answer
557 views

Minesweeper algorithm that works within O(1) space complexity

For minesweeper algorithm, instead of the most obvious BFS or DFS solution, I want a O(1) space solution. First of all, I'll explain how the program works. I will pass in a 2D array, with 1 ...
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 ...
21
votes
1answer
25k views

Check if a directed graph contains a cycle

I am trying to optimize execution time of this function which detects cycle in a directed graph: ...
7
votes
2answers
205 views

Search for Tree

Here is a search implementation for my tree. It searches each node in a breadth-first manner first, but it goes deeper in a depth-first manner, in the event it needs to go deeper. I know there may ...
7
votes
1answer
393 views

Depth First Backtracking Puzzle Solver

There is this type of puzzle that can easily be solved with a depth-first backtracking solver. I wrote one in python 3.4 and like to get some feedback. I'm especially interested in the following ...
2
votes
2answers
937 views

DFS Undirected Graph

The code included below was written in response to a programming exercise that was sent to me by a company that I am applying to. The purpose of the code is explained at this link. This code passes ...
4
votes
1answer
35k 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? ...
1
vote
1answer
354 views

Python script to convert hierarchical JSON to LaTeX itemize

I have the following JSON: ...
8
votes
4answers
49k views

Depth-first search in Python

I wrote this DFS in Python and I was wondering if it correct. Somehow it seems too simple to me. Each node is a class with attributes: visited: Boolean ...
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 ...
0
votes
1answer
2k views

Iteratively-Deepening Depth First Search (queue and non-queue)

I am aware that most 'generic' BFS algorithms that use a queue also check for uniqueness of visitation to 'speed things up' as it were, but I'm a bit unclear as to how to implement such a method as I'...
2
votes
2answers
1k views

Parse a tree & return the various paths

Input: { 1: [2,3], 2:[4], 3: [5,6], 4:[6] } Expected output: [[1, 2, 4, 6], [1, 3, 5], [1, 3, 6]] My Code: ...