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.
3
votes
1answer
57 views
3
votes
2answers
87 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
71 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.
...
1
vote
1answer
35 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 ...
1
vote
1answer
50 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 ...
2
votes
2answers
97 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 ...
9
votes
2answers
206 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, ...
2
votes
1answer
84 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
...
10
votes
1answer
314 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 ...
2
votes
1answer
237 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 ...
1
vote
1answer
457 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 ...
2
votes
1answer
50 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
216 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:
...
3
votes
2answers
274 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. ...
4
votes
0answers
170 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
126 views
2
votes
1answer
549 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 ...
7
votes
2answers
392 views
Make Depth First Search program more 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
279 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
40 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
64 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
99 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
86 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
628 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
65 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
532 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:
...
8
votes
1answer
394 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
253 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
228 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
2k 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
59 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
2k 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 ...
4
votes
2answers
1k 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
2k 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
2k 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
1k 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
389 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
279 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
215 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
76 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
434 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
136 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
99 views
2
votes
1answer
1k 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
81 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
422 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
688 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 ...
7
votes
1answer
232 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
159 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
246 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 ...
