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.

Filter by
Sorted by
Tagged with
1 vote
3 answers
66 views

DFS search that returns "not found" or distance

Assuming I've the following code: ...
user avatar
  • 143
0 votes
1 answer
57 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. ...
user avatar
0 votes
1 answer
77 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 ...
user avatar
1 vote
1 answer
176 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 ...
user avatar
0 votes
0 answers
50 views

Binary Tree DFS and BFS traversalsclass [python3]

There are six Binary Tree DFS traversals (preorder, inorder, postorder, and their reverse counterparts). Their implementations can be very similar 1, so I factored out the core logic into a class <...
user avatar
  • 243
1 vote
0 answers
70 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 ...
user avatar
1 vote
1 answer
51 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 ...
user avatar
  • 25.3k
-1 votes
1 answer
458 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: +...
user avatar
0 votes
0 answers
95 views

If maze has path

I have applied a DFS solution for to check finding path if exist from beginning point to the end point. OA: Given 2d array, check if there is path from one beginning point to given endpoint in the ...
user avatar
0 votes
2 answers
103 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. ...
user avatar
1 vote
1 answer
278 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): ...
user avatar
3 votes
2 answers
109 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 ...
user avatar
7 votes
6 answers
3k 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: ...
user avatar
  • 425
1 vote
0 answers
65 views

Improving speed of parsing XML file

...
user avatar
  • 11
3 votes
1 answer
96 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 ...
user avatar
2 votes
0 answers
49 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 ...
user avatar
  • 5,249
6 votes
1 answer
127 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 ...
user avatar
5 votes
1 answer
239 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 ...
user avatar
  • 129
5 votes
2 answers
6k 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: ...
user avatar
  • 413
5 votes
1 answer
83 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 ...
user avatar
4 votes
1 answer
193 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) ...
user avatar
  • 3,369
4 votes
1 answer
160 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? <...
user avatar
1 vote
1 answer
238 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. ...
user avatar
1 vote
0 answers
257 views

Kosaraju Algorithm in Java

Problem statement In simple words it say, count total Strongly connected components in the graph. All edges are undirected. I have the following code that uses ...
user avatar
8 votes
1 answer
827 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 ...
user avatar
  • 181
1 vote
1 answer
72 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 ...
user avatar
  • 143
1 vote
0 answers
229 views

GeeksForGeeks: Alien dictionary C#

https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/ please review for performance, the adjacency list is the problematic part for me. Given a sorted dictionary (array ...
user avatar
  • 5,249
1 vote
0 answers
122 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 ...
user avatar
  • 5,249
0 votes
0 answers
43 views

LeetCode: Delete Nodes And Return Forest C#

https://leetcode.com/problems/delete-nodes-and-return-forest/ Given the root of a binary tree, each node in the tree has a distinct value. After deleting all nodes with a value in to_delete, we are ...
user avatar
  • 5,249
1 vote
1 answer
139 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,...
user avatar
  • 5,249
3 votes
0 answers
147 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: ...
user avatar
1 vote
0 answers
234 views

LeetCode: Network Delay Time DFS solution C#

https://leetcode.com/problems/network-delay-time/ There are N network nodes, labelled 1 to N. Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the ...
user avatar
  • 5,249
-1 votes
2 answers
74 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 ...
user avatar
6 votes
1 answer
222 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 ...
user avatar
  • 163
3 votes
1 answer
58 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. ...
user avatar
5 votes
0 answers
153 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 ...
user avatar
  • 173
3 votes
1 answer
56 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 ...
user avatar
1 vote
0 answers
997 views

LeetCode: critical connections in a network C# (Tarjan's algorithm)

https://leetcode.com/problems/critical-connections-in-a-network/ Please review for memory and runtime performance. There are n servers numbered from 0 to n-1 connected by undirected server-to-...
user avatar
  • 5,249
5 votes
2 answers
297 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 ...
user avatar
3 votes
1 answer
832 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). ...
user avatar
3 votes
1 answer
50 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 ...
user avatar
  • 443
4 votes
2 answers
883 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 ...
user avatar
  • 443
2 votes
2 answers
190 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 ...
user avatar
2 votes
1 answer
335 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 <...
user avatar
1 vote
0 answers
237 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 ...
user avatar
  • 1,027
4 votes
2 answers
197 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 ...
user avatar
  • 1,027
3 votes
2 answers
666 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 ...
user avatar
  • 5,249
1 vote
1 answer
200 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 ...
user avatar
  • 2,460
5 votes
2 answers
989 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' ...
user avatar
  • 2,460
4 votes
1 answer
848 views

(Leetcode) 24 game in Python

This is a Leetcode problem - You have 4 cards each containing a number from 1 to 9. You need to judge whether they could be ...
user avatar
  • 2,460