Tagged Questions
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
52 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 dfs on it.
How can I make the ...
-1
votes
1answer
37 views
2
votes
1answer
57 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 ...
4
votes
2answers
169 views
+50
Make Depth First Search program more efficient
This is a problem from programming contest.
In the first line there is one integer T denoting the number of test
cases. Description of T test cases follow. Each one have two integers
N and K ...
1
vote
0answers
30 views
Searching a Maze Using DFS [closed]
I am new to recursion and searching algorithms and am trying to implement a maze searching program using DFS. I have tried troubleshooting the issue, but there seems to be an error with my code. Any ...
4
votes
0answers
47 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
24 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 ...
3
votes
1answer
19 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
70 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
78 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 ...
1
vote
1answer
164 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
55 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
122 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:
...
7
votes
1answer
208 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
3answers
105 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
130 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
548 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
51 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
0answers
619 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 ...
3
votes
2answers
730 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 ...
6
votes
4answers
981 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 ...
4
votes
5answers
408 views
DFS in Binary Tree
I have written this code for DFS in a binary tree and would like improvements on it.
...
1
vote
0answers
364 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 ...
7
votes
1answer
206 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.
...
11
votes
3answers
235 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
159 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
62 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
225 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 ...
3
votes
2answers
108 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
76 views
2
votes
1answer
629 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
67 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 ...
12
votes
1answer
265 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 ...
5
votes
2answers
300 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 ...
6
votes
1answer
162 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
109 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
157 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
382 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 ...
4
votes
1answer
2k 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
189 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
173 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
255 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 ...
3
votes
1answer
17k 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
101 views
4
votes
4answers
15k 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
...
4
votes
0answers
179 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
469 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 ...
1
vote
2answers
91 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:
...
10
votes
2answers
455 views
Speed up Sudoku Solver
I made this Sudoku solver using depth first search, it takes less than 0.1 second to solve any simple solution(no guessing), but if the solution requires guessing (thus using the DFS) its time grows ...
1
vote
1answer
10k views
Graph Creation and BFS + DFS in C#
I was asked to implement a graph and BFS and DFS.
Please comment. Is it understandable? Is my algorithm correct? Are there any optimizations?
...
