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
0answers
64 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: ...
1
vote
0answers
48 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 ...
-1
votes
2answers
64 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 ...
6
votes
1answer
118 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 ...
3
votes
1answer
50 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. ...
4
votes
0answers
55 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 ...
3
votes
1answer
53 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 ...
1
vote
0answers
654 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-...
5
votes
2answers
138 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 ...
3
votes
1answer
107 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). ...
3
votes
1answer
42 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 ...
3
votes
2answers
104 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 ...
2
votes
2answers
154 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 ...
2
votes
1answer
62 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
0answers
61 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 ...
4
votes
2answers
84 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 ...
3
votes
2answers
213 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 ...
1
vote
1answer
102 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 ...
5
votes
2answers
271 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' ...
4
votes
1answer
78 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 ...
5
votes
1answer
149 views

LeetCode: Add and Search Word C#

This is a Leetcode problem: Design a data structure that supports the following two operations: void addWord(word) ...
3
votes
1answer
295 views

Find all concatenated words in a given list of words

This is a Leetcode problem - Given a list of words (without duplicates), write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a ...
2
votes
2answers
83 views

Leetcode: Flatten binary tree to linked list C#

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ Please comment on performance Given a binary tree, flatten it to a linked list in-place. For example, given the following ...
4
votes
1answer
161 views

Return all valid paren strings with a given length

The problem is Given a non-negative integer n, return all valid parentheses strings with n open parens and ...
3
votes
1answer
71 views

Find number of islands Leetcode

Here is the question: Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally ...
3
votes
1answer
1k views

Java Maze Solver (DFS)

I was asked to create a Java program that will navigate through a series of mazes. I would like to know if this is the optimal way of using a DFS or is there a better way and I am doing something ...
1
vote
0answers
43 views

Choose numbers from a grid, minimising the sum

Given a 2-D input matrix, I need to pick elements from it. constraint: you can pick one number at each row, each column given: number boards are given expected output: print least sum of ...
4
votes
1answer
59 views

Find the longest connect cells region per color

I have been studying graphs/BFS/DFS. working on wrapping my head around the following problem Given a grid [m,n] where each cell has a value denotes a color, find the longest connected region that ...
4
votes
1answer
94 views

Two versions of Word Break II - exhaustive combinations

I am solving Word Break II from leetcode: Given a non-empty string s and a dictionary wordDict containing a list of non-empty ...
9
votes
2answers
2k views

Generating the powerset in C

I am solving another problem in leetcode. Given a set, generate all the subsets of the set. Input: [1,2,3] Output: ...
1
vote
1answer
644 views

Count number of islands 2d grid

This is a recursive approach using DFS to counting the number of islands. However, I would like to improve performance, while keeping the code clean concise and readable. Better yet can this be solved ...
2
votes
0answers
68 views

DFS logic to traverse a graph

I tried to literally convert recursive algorithm taught here to iterative, by simulating the recursive stack exactly as much as possible. I have tested my code and it passed all test cases. Please ...
5
votes
1answer
6k views

Searching a maze using DFS and BFS in Python 3

I solved the problem posted from Make School Trees and Maze article, which asks me to searching a maze using DFS and BFS in Python. Here's the final output from PyGame: I would like to ask for code ...
2
votes
0answers
552 views

Max flow Ford-Fulkerson using DFS augmented path retrieval

I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably? ...
0
votes
1answer
1k views

Depth First Search of graph in Python

Task: Do DFS traversal from a given given graph and print output. Is this code the correct implementation of DFS traversal in Graph? ...
6
votes
2answers
2k views

DFS in a binary tree

Problem statement: Perform a depth first traversal on a BST and print the elements traversed. ...
7
votes
1answer
574 views

Cheapest flights with at most k stops

This is the Cheapest Flights Within K Stops problem from leetcode.com: There are \$n\$ cities connected by \$m\$ flights. Each fight starts from city \$u\$ and arrives at \$v\$ with a price \$w\$. ...
1
vote
0answers
826 views

Depth First Search using Adjacency List

My aim to implement adjacency list correctly. After takin help from here, I have implemented it. I have tried to implement it here, but it was suggested that it is most likely adjacency matrix. Help ...
2
votes
1answer
8k views

Directed Graph Implementation in Java

Here I've attached my java implementation of a directed graph. I've used a modified adjacency-list mechanic to utilize a map instead of a list for quicker lookup times. Looking for comments / ...
2
votes
1answer
841 views

Binary Search Tree Implementation in Java

Looking for critiques on my BST implementation, particularly to check if I'm building the common operational methods and traversal algorithms properly. Code has been lightly tested, and I've tried to ...
4
votes
1answer
1k views

DFS implementation

I implemented DFS using recursion in Go. When I dfs the graph, I am able to get the path of traversal. But I'm unsure what else could I add to this DFS in order to make the search better. Also, Is ...
1
vote
0answers
89 views

Ruby Sudoku Solver without classes

I'm writing a Sudoku solver in Ruby to complete a coding challenge with the following restrictions. Failing to follow the following restrictions will result in an invalid submission: Do ...
2
votes
2answers
1k views

DFS implementation in Rust

...
1
vote
1answer
210 views

I want to check neighborhoods of cell in two dimensional array in C++

I want to write a function which will return all possible/valid 'X' moves around my Target cell depending on it position inside the following two dimensional array. ...
0
votes
1answer
270 views

At least 2 paths down the binary tree have the same sum

Problem statement Write a function that given a binary tree, returns true if at least 2 paths down the tree have the same sum. A path is a series of nodes from the root to the leaf. Examples: ...
1
vote
0answers
123 views

Timeout on Python code to count connected components on HackerRank

I'm trying to solve the "Roads and Bridges" problem on HackerRank https://www.hackerrank.com/challenges/torque-and-development/problem I believe the code works, but just needs to be optimized for ...
4
votes
1answer
418 views

Longest Increasing Path in a Matrix from leetcode

Solved this: Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move ...
2
votes
0answers
356 views

BinaryTree traversed in postorder (DFS), iteratively

I was given this coding question for a technical interview: Given a binary tree, implement a method to populate the list post_ordered_list with the data of the nodes traversed in postorder, ...
5
votes
1answer
3k views

Sudoku solver recursive solution with clear structure

Problem statement Similar to Leetcode 37 Sudoku solver, the algorithm is to determine if the sudoku board can be filled with ‘1’,‘2’,…,‘9’. A sudoku board is represented as a two-dimensional 9x9 ...
3
votes
1answer
115 views

templated Depth-FirstSearch algorithm

I have worked on a simple iterative implementation of the common DFS algorithm for my personal template library. The algorithm itself works, but I try to get a feeling for how to seperate the data and ...