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.
11
votes
3answers
165 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
51 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
31 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
56 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
68 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
52 views
2
votes
1answer
123 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
52 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 ...
10
votes
1answer
120 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 ...
4
votes
0answers
71 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 ...
4
votes
0answers
77 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
69 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
102 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
146 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 ...
2
votes
1answer
310 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
164 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
110 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
171 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
4k 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
71 views
3
votes
4answers
5k 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
104 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
143 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
64 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
306 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
5k 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?
...
5
votes
2answers
309 views
Constructing a graph and performing a depth-first traversal
Please review the use of pointers and design in graph construction code and its depth first traversal. I haven't used smart pointers as I want to understand any issues in following implementation with ...
3
votes
2answers
165 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 ...
1
vote
2answers
3k views
DFS on a binary tree: marking nodes as visited
I wanted to write depth first search reversal iteratively in Java. Can someone review my code? I'm not that much interested in naming of the variables, but in the structure of the code, i.e. I don't ...
2
votes
1answer
2k views
Nsum problem: find all n elements in an array whose sum equals a given value
I am implementing the algorithm for the following problem with Python. I am pretty new to Python, so I want to listen to any advice that improve my coding style in a "pythonic" way, even about naming ...
1
vote
2answers
212 views
Code duplication for just an if condition
I have two methods that are near-perfect duplicates. There is of course a code smell. The only thing that changes is the condition to increment a variable.
Language: Java7
...
6
votes
3answers
2k views
Missing level of technical depth (Flatten Tree)
I recently have given a coding test in a reputable IT company. There were three coding questions.
They refused me by saying that
as we felt they didn't demonstrate the level of technical depth ...
7
votes
3answers
4k views
Depth First Traversal of a Graph
I am learning how to implement a basic undirected graph and perform a depth first traversal.
Please critique my code for correctness, best practices, security, and any other comments that may be ...
6
votes
4answers
73k views
Depth First Search & Breadth First Search implementation
I've implemented DFS and BFS implementations. I want to check if the code is readable, contains any issues, and can be improved.
GraphImplementation
...
1
vote
1answer
266 views
Depth first search, use of global variables, and correctness of time
As I was coding this algorithm I found that some variables that are meant to be global behave as they are intended to behave, but others do not. Specifically, my boolean arrays, e.g. ...
0
votes
2answers
131 views
How to enumerate the internal nodes and leaves of a tree more elegantly?
Might there be a simpler way to write this code? I'd like to learn to write code more efficiently.
...
3
votes
2answers
1k views
Returning a list of the values from the binary tree
I want to return a list of the values from the binary tree. Is there a shorter and more efficient way to write the method for numbers?
...
1
vote
1answer
311 views
DFS algorithm with generators
Background:
I was working on a project were I needed to write some rules for text-processing. After working on this project for a couple of days and implementing some rules, I realized I needed to ...
4
votes
1answer
3k 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 ...
3
votes
1answer
7k views
DFS/BFS implementation of Cormen's pseudo code
This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this.
...
2
votes
1answer
3k views
Breadth- and Depth-first search code
Here is my breadth-first search (bfs) and depth-first search (dfs) code for graph traversal. Please give me some constructive ...
12
votes
1answer
286 views
Depth-first search method for searching for all “superpalindromes” whose prime factors are all <=N
A question was asked over at math.SE (here) about whether or not there are infinitely many superpalindromes. I'm going to rephrase the definition to a more suitable one for coding purposes:
...
