Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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.

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers
738 views

Pseudo-parallel depth-first search

I'm writing a small program that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel depth-first search (dfs) on it. ...
user avatar
5 votes
0 answers
154 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
4 votes
0 answers
4k views

Make DFS Implementation faster for 8 puzzle problem in Python

I am implementing DFS algorithm for the 8 puzzle problem which works fine if the goal is reached in less than 10 iterations. But for longer number of iterations, my implementation doesn't return the ...
user avatar
  • 41
4 votes
0 answers
361 views

Skiena's DFS on unweighted graphs, in Python 3, with adjacency-list implementation

In the Algorithm Design Manual (2nd ed) pp 172 - 173, Skiena writes: As algorithm design paradigms go, a depth-first search isn't particularly intimidating. It is surprisingly subtle, however ...
user avatar
  • 598
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
3 votes
0 answers
4k views

Depth first search implementation

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the depth first search section (5.8) using javascript. Note you can execute the code here if you don't ...
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
2 votes
0 answers
70 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 ...
user avatar
  • 121
2 votes
0 answers
712 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? ...
user avatar
2 votes
0 answers
403 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, ...
user avatar
  • 2,469
2 votes
0 answers
135 views

AI for depth-first walking in a maze, with variable depth look ahead search for dead ends and finish point

This code is a part of a little game I've started a week ago. It is too extensive to review at once, so I'm picking the most interesting and crucial parts. Start with the AI. It has public update ...
user avatar
1 vote
0 answers
71 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
0 answers
65 views

Improving speed of parsing XML file

...
user avatar
  • 11
1 vote
0 answers
258 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
1 vote
0 answers
231 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
123 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
1 vote
0 answers
240 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 vote
0 answers
998 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
1 vote
0 answers
238 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
1 vote
0 answers
47 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 ...
user avatar
1 vote
0 answers
896 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 ...
user avatar
  • 2,439
1 vote
0 answers
107 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 ...
user avatar
1 vote
0 answers
159 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 ...
user avatar
  • 11
1 vote
0 answers
720 views

Graph (adjacency list) and DFS (topological sort)

The vertices on the graph are numbers from 0 to |V| - 1 for convenience. I was thinking later to use a template wrapper for the graph. Graph.h: ...
user avatar
  • 2,964
1 vote
0 answers
761 views

Depth First Search for percolation to find clusters in Go game

I have some questions about Depth First Search and whether I implemented it correctly. Below is a more thorough discussion. The graph in question is a randomly colored square grid (I use 3 colors). ...
user avatar
0 votes
0 answers
51 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
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
0 answers
44 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 votes
1 answer
465 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