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.
179 questions
1
vote
0
answers
64
views
PathFinding.java: Drawing a random perfect maze via randomized DFS
Intro
Still working on PathFinding.java. This time I concentrate on three private methods of GridModel that are responsible for generating random perfect mazes. A maze is perfect if for each two cells ...
- 32.3k
1
vote
0
answers
71
views
Fixed BIDDFS (bidirectional iterative deepening depth first search) in Java
Intro
I have this GitHub repository for doing pathfinding in directed unweighted graphs. This post is about BIDDFS proposed by Richard Korf in his paper.
Code
...
- 32.3k
1
vote
0
answers
40
views
LibID: a Java library containing some iterative deepening algorithms for pathfinding on directed unweighted graphs
Intro
I have this GitHub repository containing some iterative deepening pathfinding algorithms.
Code
...
- 32.3k
5
votes
1
answer
363
views
Iterative DFS with Optimized Space Complexity
Background
I can't seem to find an existing answer solving this doubt of mine.
In academic books, it seems that DFS is usually presented in both recursive and iterative forms.
The implementations ...
- 151
1
vote
1
answer
74
views
How to count disconnected components in grid efficiently, if we can move left, right, down and top from any cell
I solved this problem: A. Ice Skating, Codeforces
My approach was to create grid from given snow drifts coordinates, then convert this grid into graph and then count how many disconnected components ...
- 171
6
votes
3
answers
746
views
Program that brute forces to find the minimum dominating set
This program solves the minimum dominating set but it takes an insanely long time to run. In case you do not know, in graph theory, a dominating set for a graph G is a subset D of its vertices, such ...
2
votes
1
answer
300
views
Finding the longest path on a grid with obstacles from the top to the bottom
I have a rectangle of . (platforms) and # (obstacles). I can start at any platform in the top row and go to the left, right or ...
1
vote
1
answer
149
views
Order of values in dfs and bfs
Let's consider a matrix of integers m:
[[1,2,3]
[4,5,6]
[7,8,9]]
Which represents a graph:
...
- 171
2
votes
0
answers
209
views
Backtracking graph algorithms for a word puzzle in Python
Motivation
Recently, Buzzfeed released a browser-based puzzle game called "Pyramid Scheme." It is available at the following link. The puzzle in an initial state looks like this:
To solve ...
- 163
3
votes
1
answer
81
views
Optimize Island Counter program
I am doing some assignments on my own and one of them is about a Island Counting program, I have come up with a working program but the problem is its very slow.
When running test on for example maps ...
- 33
2
votes
1
answer
150
views
USACO Silver "Wormhole Sort" solver
I'm struggling a bit with a USACO silver question using Python: http://usaco.org/index.php?page=viewproblem2&cpid=992.
The question provides an unsorted list of numbers (...
- 21
3
votes
1
answer
158
views
Exceeded time limit on Trie search with Backtracking using Swift
I have been trying to solve Trie related problems over at leet code and came across this interesting problem 211. Design Add and Search Words Data Structure
Here is the question for convenience:
211. ...
- 253
1
vote
1
answer
99
views
Shortest path in dags: Part 2/3 - the preprocessing and shortest path algorithms
Part 1/3
Part 3/3
I have this library for performing shortest path queries on dags (directed acyclic graphs). This post presents the shortest path algorithms and the topological sorters. Two ...
- 32.3k
1
vote
3
answers
136
views
0
votes
1
answer
253
views
Find the shortest path from bottom left to top right in a maze using dfs and bfs algorithm
The following code is applying the depth-first search and breadth-first search algorithm to find the shortest path from bottom left to top right in a 10 x 10 grid. ...
- 157