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
6
votes
1answer
61 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 ...
6
votes
1answer
89 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 ...
4
votes
1answer
87 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: ...
5
votes
1answer
61 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
1answer
79 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) ...
4
votes
1answer
57 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? <...
1
vote
1answer
82 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. ...
1
vote
0answers
72 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 ...
7
votes
0answers
128 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 ...
1
vote
1answer
61 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 ...
1
vote
0answers
75 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 ...
0
votes
0answers
77 views

LeetCode: Course Schedule II C#

https://leetcode.com/problems/course-schedule-ii/ Please review for performance, please pay attention to the DFS function can this is be optimized? There are a total of n courses you have to take, ...
1
vote
0answers
45 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 ...
0
votes
0answers
26 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 ...
1
vote
1answer
77 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,...
3
votes
0answers
122 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
105 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
68 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
155 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
53 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
71 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
869 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
170 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
229 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
43 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
304 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
160 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
105 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
93 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 ...
4
votes
2answers
107 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
295 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
124 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
418 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
204 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
157 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
530 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
106 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
162 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
125 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
2k 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
45 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 numbers what ...
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
109 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 ...
10
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
844 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
8k 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
596 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
2k 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? ...