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.
175 questions
2
votes
2
answers
1k
views
DFS Undirected Graph
The code included below was written in response to a programming exercise that was sent to me by a company that I am applying to. The purpose of the code is explained at this link.
This code passes ...
- 21
4
votes
1
answer
36k
views
Depth First Search and Breadth First Search in C++
I am trying to learn DFS and BFS. However, I just want to make sure that I am not doing anything wrong. Would you please determine if the BFS and DFS functions are correct?
...
- 391
1
vote
1
answer
448
views
8
votes
4
answers
50k
views
Depth-first search in Python
I wrote this DFS in Python and I was wondering if it correct. Somehow it seems too simple to me.
Each node is a class with attributes:
visited: Boolean
...
- 417
5
votes
1
answer
444
views
Finding cycles in a graph that pass through a vertex at most k times
I have a project that relies on finding all cycles in a graph that pass through a vertex at most k times. Naturally, I'm sticking with the case of k=1 for the sake of development right now. I've come ...
- 59
0
votes
1
answer
2k
views
Iteratively-Deepening Depth First Search (queue and non-queue)
I am aware that most 'generic' BFS algorithms that use a queue also check for uniqueness of visitation to 'speed things up' as it were, but I'm a bit unclear as to how to implement such a method as I'...
- 143
2
votes
2
answers
1k
views
Parse a tree & return the various paths
Input:
{ 1: [2,3], 2:[4], 3: [5,6], 4:[6] }
Expected output:
[[1, 2, 4, 6], [1, 3, 5], [1, 3, 6]]
My Code:
...
- 153
11
votes
2
answers
2k
views
Speed up Sudoku Solver
I made this Sudoku solver using depth first search, it takes less than 0.1 second to solve any simple solution(no guessing), but if the solution requires guessing (thus using the DFS) its time grows ...
- 712
5
votes
3
answers
22k
views
Graph Creation and BFS + DFS in C#
I was asked to implement a graph and BFS and DFS.
Please comment. Is it understandable? Is my algorithm correct? Are there any optimizations?
...
- 5,253
6
votes
2
answers
1k
views
Constructing a graph and performing a depth-first traversal
Please review the use of pointers and design in graph construction code and its depth first traversal. I haven't used smart pointers as I want to understand any issues in following implementation with ...
- 305
3
votes
2
answers
699
views
has_cycle in directed and undirected graphs
I wrote a program that can tell if a graph has_cycle or not.
Can you please suggest more elegant and eloquent ways for this program?
(Perhaps better ways to represent a graph with vertices and edges?)...
- 161
1
vote
2
answers
7k
views
DFS on a binary tree: marking nodes as visited
I wanted to write depth first search reversal iteratively in Java. Can someone review my code? I'm not that much interested in naming of the variables, but in the structure of the code, i.e. I don't ...
- 861
2
votes
1
answer
6k
views
Nsum problem: find all n elements in an array whose sum equals a given value
I am pretty new to Python, so I want to listen to any advice that improve my coding style in a "pythonic" way, even about naming style of variables. The following code reflects a very general paradigm ...
- 123
1
vote
2
answers
246
views
Code duplication for just an if condition
I have two methods that are near-perfect duplicates. There is of course a code smell. The only thing that changes is the condition to increment a variable.
Language: Java7
...
- 229
6
votes
3
answers
2k
views
Missing level of technical depth (Flatten Tree)
I recently have given a coding test in a reputable IT company. There were three coding questions.
They refused me by saying that
as we felt they didn't demonstrate the level of technical depth we'...
- 409
8
votes
3
answers
7k
views
Depth First Traversal of a Graph
I am learning how to implement a basic undirected graph and perform a depth first traversal.
Please critique my code for correctness, best practices, security, and any other comments that may be ...
25
votes
4
answers
188k
views
Depth First Search & Breadth First Search implementation
I've implemented DFS and BFS implementations. I want to check if the code is readable, contains any issues, and can be improved.
GraphImplementation
...
- 634
1
vote
1
answer
1k
views
Depth first search, use of global variables, and correctness of time
As I was coding this algorithm I found that some variables that are meant to be global behave as they are intended to behave, but others do not. Specifically, my boolean arrays, e.g. ...
- 63
0
votes
2
answers
734
views
How to enumerate the internal nodes and leaves of a tree more elegantly?
Might there be a simpler way to write this code? I'd like to learn to write code more efficiently.
...
- 181
8
votes
2
answers
11k
views
Returning a list of the values from the binary tree
I want to return a list of the values from the binary tree. Is there a shorter and more efficient way to write the method for numbers?
...
- 181
1
vote
2
answers
1k
views
DFS algorithm with generators
Background:
I was working on a project were I needed to write some rules for text-processing. After working on this project for a couple of days and implementing some rules, I realized I needed to ...
- 497
4
votes
1
answer
6k
views
Java cycle detection using DFS in an undirected graph
I am doing interview studies and can't find a simple DFS for a cycle-finding algorithm. I want someone to tell me if my DFS algorithm works and how it can be improved.
Where can you get a typical ...
- 141
5
votes
1
answer
13k
views
DFS/BFS implementation of Cormen's pseudo code
This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this.
...
- 297
2
votes
1
answer
7k
views
Breadth- and Depth-first search code
Here is my breadth-first search (bfs) and depth-first search (dfs) code for graph traversal. Please give me some constructive ...
- 29
12
votes
1
answer
336
views
Depth-first search method for searching for all "superpalindromes" whose prime factors are all <=N
A question was asked over at math.SE (here) about whether or not there are infinitely many superpalindromes. I'm going to rephrase the definition to a more suitable one for coding purposes:
...
