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
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. ...
• 161
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 ...
• 173
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 ...
• 41
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 ...
• 598
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: ...
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 ...
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 ...
• 5,249
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 ...
• 121
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? ...
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, ...
• 2,469
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 ...
• 151
1 vote
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 ...
1 vote
65 views

...
• 11
1 vote
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 ...
• 299
1 vote
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 ...
• 5,249
1 vote
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 ...
• 5,249
1 vote
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 ...
• 5,249
1 vote
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-...
• 5,249
1 vote
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 ...
• 1,027
1 vote
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 ...
• 11
1 vote
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 ...
• 2,439
1 vote
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 ...
1 vote
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 ...
• 11
1 vote
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: ...
• 2,964
1 vote
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). ...
• 258
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 <...
• 243
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 ...