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
5
votes
1answer
10k 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
628 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? ...
6
votes
2answers
3k views

DFS in a binary tree

Problem statement: Perform a depth first traversal on a BST and print the elements traversed. ...
7
votes
1answer
651 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
868 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
11k 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
1k 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 ...
5
votes
1answer
2k 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
98 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 ...
3
votes
2answers
2k views

DFS implementation in Rust

...
1
vote
1answer
264 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
278 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
145 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
504 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
383 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
4k 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
134 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 ...
3
votes
1answer
2k views

Breadth- and Depth- First Search in C#

Another recreational implementation for review! As a side comment, for some reason I just feel like if (visited.Contains(vertex)) { .. } isn't necessary, as this ...
4
votes
0answers
2k 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 ...
1
vote
2answers
418 views

Depth-first search of a graph in C# (HackerRank problem)

I'm trying to solve a problem from HackerRank. I got the correct algorithm, but it seems to be too inefficient. After checking the code with 10 given test cases, 3 cases are good and 7 return a ...
4
votes
2answers
828 views

Given two words and a dictionary's word list, find all shortest transformation sequence

This is a leetcode problem (https://leetcode.com/problems/word-ladder-ii/description/) Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(...
6
votes
1answer
543 views

Recursive Depth First Search for finding valid sudoku boards in Python 3

I am not an experienced programmer, and I decided to make a program that could find all possible sudoku arrangements just for fun. As far as I can see, the program is working all right, but I'd like ...
5
votes
1answer
232 views

Depth-first Search Non-Reursive Implementation in Clojure

I've created a non-recursive dfs implementation in Clojure. I'm using the wikipedia article on dfs as a guide. I'm very new to Clojure and functional programming in general. Any tips to improve ...
3
votes
1answer
861 views

“The Story of a Tree” solved using depth-first search

Found this problem in hackerrank. One day Bob drew a tree, with \$n\$ nodes and \$n-1\$ edges on a piece of paper. He soon discovered that parent of a node depends on the root of the tree. The ...
4
votes
0answers
332 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 ...
4
votes
1answer
1k views

Find Eulerian Tour Algorithm - with multithreading and random permutations

After struggling for a long while on this through the algorithms course on Udacity, I finally understood enough of the concept to develop this implementation. However, it lacks efficiency and finesse. ...
11
votes
3answers
3k views

Depth First Search Implementation (iterative)

Here is my code for Depth First Search and, as far as I know, it is working fine on most cases. It is not very efficient as I have implemented it for the very first time.. Warning: It is only for bi-...
7
votes
2answers
1k views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
5
votes
1answer
380 views

Hackerrank - Maximum Disjoint Subtree Product

Problem statement We define an unrooted tree, T, with the following properties: T is a connected graph with nodes ...
7
votes
1answer
665 views

A DFS sudoku solver

This is my attempt at a Sudoku solver using a DFS approach. I mainly developed it to become a better Rust developer, but if you have any performance tips, I will be glad to hear them :) My program ...
4
votes
2answers
646 views

Find the longest rectilinear path in a matrix with descending entries

Problem (Skiing): Each number represents the elevation of that area of the mountain. From each area (i.e. box) in the grid, you can go north, south, east, west - but only if the elevation ...
4
votes
2answers
2k views

Depth and breadth first search

I am practicing interview questions, I wrote this code to perform BFS and DFS on a graph in Python. How can it be optimized, and how can it be made more readable? ...
5
votes
1answer
75 views

Given a binary tree, \$T\$ whose nodes have positive values, find the value of the maximal path

Problem Problem is Maximum sum path from https://firecode.io Given a binary tree, \$T\$, whose nodes have positive values find the value of a maximal path. A path is a simple path from a node to ...
9
votes
1answer
3k views

Hacker Rank: Journey to the Moon (Graph Theory)

I am attempting to complete the "Journey to the Moon" problem described below: There are N trained astronauts numbered from 0 to N-1. But those in charge of the mission did not receive ...
6
votes
1answer
3k views

BFS/DFS Web Crawler

I've built a web crawler that starts at an origin URL and crawls the web using a BFS or DFS method. Everything is working fine, but the performance is horrendous. I think the major cause of this is ...
3
votes
1answer
582 views

Ternary tree preoder traversal (recursive implementation)

Problem statement: Print out to console the ternary tree preorder traversal. Suppose that the tree can have at most 3 children, left, middle and right. Preorder traversal is to visit the middle ...
7
votes
1answer
814 views

Leetcode 17. Letter Combinations of a Phone Number

Problem Statement Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. ...
1
vote
1answer
670 views

Depth First Search (Adjacency List) in JavaScript

I am trying to implement a DFS search and graphs. How can I make it better? ...
6
votes
1answer
5k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
3
votes
2answers
838 views

CLRS Implementation of BFS and DFS in C++

I tried to implement BFS and DFS from Introduction to Algorithms by Cormen. Any suggestions on how to improve my code? GraphStructures.h ...
5
votes
1answer
442 views

Snakes and Ladders using a magic die

This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game. ...
1
vote
1answer
541 views

Return a path between graph nodes using depth-first search redo

I previously attempted to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. This is my latest attempt at this ...
2
votes
1answer
5k views

Return path between graph nodes using depth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. I'm doing this to improve my style ...
2
votes
2answers
426 views

A Scala Maze Generator in Functional Style

I'm wondering if there is more I can do to incorporate more idiomatic scala and functional programming principles. I know the maze itself is mutable but i didn't see an easy solution to making it ...
10
votes
2answers
1k views

2D grid Hamiltonian path puzzle solver

The puzzle goes like this: in a rectangular 2D grid there are empty spaces (.), exactly one starting point (S, ...
2
votes
1answer
100 views

File search program not efficient enough

I have created a program to search for a file in the computer. But I feel it can be improved. Can anyone help me with this? filesearch.py ...
11
votes
1answer
2k views

Yet another minimax tree for TicTacToe

I have written a working minimax tree for Tic-Tac-Toe. What I have done so far is create a tree with end node having value 10, 0 or -10 base on win, lose or draw. After I create a tree I then ...
2
votes
1answer
4k views

Pattern searching in 2d grid

This is an interview question which i am trying to solve. You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all ...
1
vote
1answer
10k views

C++ Maze Generator

I have made a random maze generator that allows for custom sizes via command arguments. It uses depth-first search and is written is C++. Could you look over my code and suggest any improvements ...