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.
175 questions
1
vote
1
answer
49
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 ...
- 161
6
votes
3
answers
707
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
262
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
117
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:
...
- 161
1
vote
0
answers
187
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 ...
- 153
3
votes
1
answer
71
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
1
vote
0
answers
113
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 (cows) and a number of ...
- 11
3
votes
1
answer
131
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
68
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 ...
- 29.8k
1
vote
3
answers
93
views
0
votes
1
answer
237
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
0
votes
1
answer
179
views
Recursive DFS to find Euler Cycle
I have referred to this for what constitutes as an Euler Cycle: https://xlinux.nist.gov/dads/HTML/eulercycle.html
This assignment required me to use Depth First Search and have the methods I have ...
1
vote
1
answer
984
views
Helper get_all_neighbors (in a grid) function - python
So a little context to understand the code:
This is a helper function to solve a bigger problem here
Quick summary: A Knight is in a dungeon/2D grid of Ints, starts at 0,0 and must reach the last ...
- 113
1
vote
0
answers
368
views
Codewars: Path Finder
Task
You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return true if you can reach position [N-1, N-1] or false ...
1
vote
1
answer
76
views
Loan graph simplification in Java: the recursive DFS for searching for directed cycles
The class in this post returns a directed cycle in a financial loan graph. A financial loan graph consists of nodes and directed arcs. If there is an arc \$(u, v)\$ with weight \$w = w(u, v)\$, then ...
- 29.8k
0
votes
1
answer
1k
views
Find Passable Lanes in Rows and Columns
I have implemented the following question and looking forward for the reviews.
Question Explanation :
We have a two-dimensional board game involving snakes. The board has two types of squares on it: +...
- 930
0
votes
2
answers
196
views
Given a 2d matrix with chars find the target string
I am looking for a simpler implementation of the following question.
Could it get better?
I am expecting the new solution via DFS again. Thanks.
OA: Given a 2d matrix with chars and a target string.
...
- 930
1
vote
1
answer
1k
views
How does one write DFS in python with a Deque without reversed for Trees?
I have implemented a correct version of DFS (with comments explaining the implementation):
...
- 128
3
votes
2
answers
396
views
Check if point is inside a bitmap shape
Inspired by this question, here's some C code to check if a point is "inside" of a shape on a simple black and white bitmap.
For this exercise:
Set bits form the "outlines" of a ...
- 11.9k
7
votes
6
answers
4k
views
C++ implementation of depth-first search
I got the C++ implementation of depth-first search (DFS) from here and made slight modifications to it. The modified code is as follows:
...
- 435
3
votes
1
answer
426
views
Detecting a cycle in a directed graph via an adjacency list implementation and a recursive DFS
Here's my attempt. I iterate through each vertex in the graph and do a DFS to see if I reach back on a vertex I already visited in this vertex's iteration. It seems to work but I am not satisfied with ...
- 119
2
votes
0
answers
74
views
LeetCode: Number of enclaves C#
https://leetcode.com/problems/number-of-enclaves/
Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)
A move consists of walking from one land square 4-directionally to ...
- 5,253
6
votes
1
answer
280
views
Graph: Depth First Search (N citizens with pairs of friends)
I have solved problem 10608 on UVA Online Judge using Python 3.5.1. My solution works, but it takes too long to run when the online judge evaluates it.
Problem
There is a town with N citizens. It is ...
- 63
5
votes
1
answer
719
views
01 Matrix is too slow when solved using DFS
I tried solving Leetcode 01 Matrix problem.
It is running too slow when solved using DFS approach.
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance ...
- 129
6
votes
2
answers
18k
views
Depth First Search Using Stack in Python
I have implemented a depth first search using a stack (in a separate class). Any suggestions please on improvements for the below code:
...
- 435
5
votes
1
answer
125
views
Closest Pair heuristics, graph with adjacency matrix in C++17
I was trying to solve a problem that was briefly mentioned at the beginning of the "The Algorithm Design Manual" by Steven Skiena (Ch 1, Problem 26).
It took me some time to build a working ...
4
votes
1
answer
352
views
LeetCode 839: Similar String Groups II
I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!
Problem
Two strings X and Y are similar if we can swap two letters (in different positions) ...
- 3,542
4
votes
1
answer
293
views
Sudoku solver using backtracting and depth-first-search
I've recently finished my first ever C program. I implemented a Sudoku solver that uses backtracking.
Does my code look like a proper C-program? Are there any recommendations for improving my code?
<...
2
votes
1
answer
372
views
Sum of all Paths in Binary Tree
Problem
For the given binary tree return the list which has sum of every paths in a tree. i.e Every path from root to leaf.
I've written following solution.
...
- 299
8
votes
1
answer
2k
views
Recursive and iterative implementation on Kosaraju algorithm
Kosaraju algorithm is mainly phrased as two recursive subroutines running postorder DFS twice to mark SCCs with linear time complexity O(V+E) below,
For each vertex \$u\$ of the graph, mark \$u\$ as ...
- 181
1
vote
1
answer
84
views
Depth First Search vs Breadth First Search
So after years of teaching myself, I think I'm ready to stand on the shoulders of giants and ask you a good question!
I have a tree of nodes. What I want is a function that returns an array of the ...
- 143
1
vote
0
answers
302
views
LeetCode:MineSweeper C#
https://leetcode.com/problems/minesweeper/
please review for performance. I really don't like the implementation I made for GetNumberOfMines() function, but within the time limits i did this. it is ...
- 5,253
1
vote
1
answer
221
views
LeetCode: FloodFill C#
https://leetcode.com/problems/flood-fill/
An image is represented by a 2-D array of integers, each integer
representing the pixel value of the image (from 0 to 65535).
Given a coordinate (sr,...
- 5,253
3
votes
0
answers
176
views
N-Queens Puzzle
The N-Queens puzzle can be solved in many ways. One is by a depth-first-search backtracking algorithm.
Below is my generalized version using mutual recursion:
...
user73941
-1
votes
2
answers
79
views
algorithm to find a zero in a board game [closed]
I got asked this question in an interview and I came up with a solution which I shared in the below but apparently it was not enough to pass. I'm looking forward to hearing how this problem could be ...
- 383
6
votes
1
answer
271
views
Clojure depth first search maze problem from Classic CS Problems in Python Book
I am an experienced self-taught professional Python programmer working my way through the book Classic Computer Science Problems in Python to try to catch myself up on some of the things I missed by ...
- 163
3
votes
1
answer
126
views
Creating valid words on an n-by-n grid of characters using depth-first search
I am trying to create a word-finder game. There will be an n-by-n Board filled with Tiles.
...
- 33
5
votes
0
answers
219
views
A generic DFS in JavaScript
I implemented a general function for a depth-first-search (DFS) using JavaScript with default arguments and functions that need to be provided in order for it to work.
This function is using ...
- 173
3
votes
1
answer
78
views
Find the lengths of strongly connected components in a graph
I wrote a code to calculate the lengths of strongly connected components in a graph. The results I get are correct but it scales horribly.
This is the code I have. I understand that the runtime ...
- 139
5
votes
2
answers
460
views
Optimize depth-first search for sliding tile puzzle
My current code implementing a depth-first search works well for puzzle 1. But my code is too slow; I think I use too many loops and I am not sure I am using the right data structure. So I have a ...
- 53
3
votes
1
answer
2k
views
Maze path finder using Depth-First Search algorithm
I'm trying to resolve this kata from CodeWars.
Kata exercise
You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). ...
- 185
3
votes
1
answer
51
views
Javascript Tree Class 2
This question is the second version of the code here.
I'm writing a general tree class. Specifically, each node should have oen parent, some number of children, and hold a value.
I'm looking for ...
- 443
4
votes
2
answers
1k
views
Javascript Tree Class
I got caught in the trap of implementing my own data structure. I've created a very general tree structure, where each node gets one parent, some children, and holds a value.
I'm mostly looking for ...
- 443
2
votes
2
answers
261
views
Ruby implementation for Hacker Rank connected cells in a grid
https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem
problem statement:
Consider a matrix where each cell contains either a 1 or a 0. Any
cell containing a 1 is called a ...
- 153
2
votes
1
answer
394
views
Find articulation points/ cut vertices in graph
I would like to get some feedback on my completed code that finds and displays the articulation vertices in an undirected graph.
I included a test case within the code, it should (and does) print <...
1
vote
0
answers
304
views
Graph-coloring solution using depth-first search
I'm trying to solve this question:
Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.
The park consists of n squares ...
- 1,031
4
votes
2
answers
251
views
Finding a vertex of a tree such that every subtree rooted at that vertex is of a uniform color
I'm trying to optimally solve codeforces problem 763A:
Each New Year Timofey and his friends cut down a tree of n vertices
and bring it home. After that they paint all the n its vertices, so
...
- 1,031
3
votes
2
answers
1k
views
Find all possible words in a board of characters
This question has 2 possible solutions and I am trying to implement the DFS solution.
Here is the Trie and DFS solution: Boggle using Trie and DFS
Please review for performance.
Given a ...
- 5,253
1
vote
1
answer
269
views
(Leetcode) Freedom Trail
I would like to know whether I could make my solution to this challenge shorter and more efficient. Below is the description of the challenge (this is a Leetcode problem) -
In the video game ...
- 2,485
5
votes
2
answers
1k
views
(Leetcode) Minesweeper game
This is a Leetcode problem -
Let's play the Minesweeper game
(Wikipedia,
online game)!
You are given a 2D char matrix representing the game board. 'M'
represents an unrevealed mine, 'E' ...
- 2,485