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
3answers
21k 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? ...
6
votes
2answers
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 ...
3
votes
2answers
649 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?)...
1
vote
2answers
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 ...
2
votes
1answer
5k 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 ...
1
vote
2answers
233 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 ...
6
votes
3answers
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'...
8
votes
3answers
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 ...
24
votes
4answers
186k 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 ...
1
vote
1answer
826 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. ...
0
votes
2answers
623 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. ...
6
votes
2answers
7k 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? ...
1
vote
2answers
850 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 ...
4
votes
1answer
5k 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 ...
5
votes
1answer
12k views

DFS/BFS implementation of Cormen's pseudo code

This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this. ...
2
votes
1answer
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 ...
12
votes
1answer
325 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: ...

1 2 3
4