Questions tagged [breadth-first-search]
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.
180
questions
26
votes
3
answers
55k
views
25
votes
4
answers
187k
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
17
votes
3
answers
6k
views
Number of Islands in a 2d grid
Recently, I've solved this "Number of Islands" problem on LeetCode, the solution was accepted by the LeetCode OJ.
Problem Description
Given a 2d grid map of '1's (land) and '0's (water), count the ...
- 17.2k
12
votes
2
answers
589
views
Cows with walkie-talkies (USACO Silver Prob. #3; December '16 )
The official problem description is here, which in my opinion is unclear and quite long. Below is my description. I recommend you still read the official description, it has details such as input and ...
- 349
11
votes
3
answers
1k
views
Finding shortest paths in directed graphs
I have very little experience in programming with C++ and the following small "program" is the 2nd one I have ever written in that language. I am most interested in comments regarding naming ...
- 26.6k
11
votes
1
answer
5k
views
Find the shortest path through a maze with a twist: you can knock down one wall
I would like my solution to Google Foobar's prepare_the_bunnies_escape checked for readability, maintainability, extensibility, style, design. I am looking forward ...
- 167
10
votes
2
answers
3k
views
Run time complexity of printing a binary tree level by level
I have some doubts about running time of following question. The problem is printing a binary tree level by level. For example if tree is like
...
- 505
10
votes
2
answers
292
views
Improving performance of A* search in PHP
I need to figure out what can be done to improve the performance of a A* search algorithm in PHP. The idea is to look for the shortest path, in number of hops, between two points in a "map". Actual ...
- 276
9
votes
4
answers
27k
views
Python 8-Puzzle and solver
I wrote a simple 8-Puzzle and solver and am interested in seeing how it might be improved. Please let me know if any style or design changes might enhance the readability/performance of my code.
<...
- 1,233
9
votes
1
answer
9k
views
Solve 8-tile sliding puzzle
I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which ...
- 93
9
votes
1
answer
341
views
Breadth First Search not SOLID enough v2.0
Original question: Breadth First Search not SOLID enough
Here is my first attempt at refactoring. Instead of using a Tuple, I used a ...
- 335
9
votes
2
answers
589
views
Python PacMan with son
I have been coding 'Pac-Man' with my 16yo. A hopefully not too boring project to help improve his Python coding. We have just moved the 'Ghosts' into a class which was a good first introduction to ...
- 91
9
votes
1
answer
1k
views
Graph theory using C++ STL
I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object.
Any feedback would be ...
- 393
9
votes
1
answer
1k
views
Maze image solver and animator in Python
This maze solver is a continuation to the maze generator I posted here recently Maze generator & animator in Python
This code takes an image containing a 2-color maze as input and solves the maze ...
user203258
8
votes
2
answers
4k
views
C++ Graph Implementation
My data set is a list of Edges which are passed as a pair of integers. Based on that, I have the following graph implementation for BFS. Could someone please review ...
- 81
8
votes
2
answers
9k
views
C++ Graph Class Implementation (adjacency list)
I've got a barebones C++ graph class implemented as an adjacency list. The graph consists of a vector of vertices. Each vertex has a vector of outgoing edges that store the destination vertex id. ...
- 145
8
votes
1
answer
6k
views
Improve Graph Adjacency List Implementation and Operations
I am studying graphs and I am trying to make a library in C# for myself and anyone else interested, that is didactic and simple, so I can remember how to solve common problems.
I would like to ...
- 182
8
votes
1
answer
874
views
Beginner's Knight's tour in Python (BFS)
I wanted to implement this as short and effective as I could without using anything that is not basics, in order to improve my skills.
I would appreciate input about things like memory leaks I missed,...
- 351
7
votes
2
answers
1k
views
Iterator for BFS binary tree traversal
I implemented an iterator pattern for C# using IEnumerator and IEnumerable. The goal of the implementation is to traverse a ...
- 5,311
7
votes
2
answers
341
views
Find the first repeating sequence in digits of pi
I wrote a function to return the first n length sequence which occurs twice in the digits of pi. Along with the repeated sequence, I want the indices of the first and second occurrences. For example, ...
- 73
7
votes
1
answer
937
views
BFS for creating a queue without repetitions and with loops in the graph
I have a pipeline with loops of filters and one input filter. The rest are splitters, transform and output.
I would like my code to go over the filters and push them into a queue (order is important)...
- 5,311
7
votes
1
answer
900
views
Breadth First Search not SOLID enough
The following code has a modified version of the Breadth First Search algorithm. It not only visits the nodes, but keeps track of the paths, so I can output various messages later. I would like to ...
- 335
7
votes
2
answers
12k
views
Breadth First Search implementation in Python 3 to find path between two given nodes
This is my Breadth First Search implementation in Python 3 that assumes cycles and finds and prints path from start to goal.
Some background - Recently I've been preparing for interviews and am ...
- 73
7
votes
2
answers
269
views
Degrees of Wikipedia
Here is my attempt on implementing "Degrees of Wikipedia" (much faster version can be seen at degreesofwikipedia.com.It's basically an algorithm which tries to connect two unrelated Wikipedia pages by ...
- 173
7
votes
2
answers
220
views
Search for Tree
Here is a search implementation for my tree. It searches each node in a breadth-first manner first, but it goes deeper in a depth-first manner, in the event it needs to go deeper. I know there may ...
user34073
7
votes
2
answers
339
views
"Ringing in the New Year (2011→ 2012)" puzzle
I am trying to solve the puzzle RINGING IN THE NEW YEAR.
Start at 2011. By moving through the maze and doing any arithmetic operations you encounter, exit the maze with a result of 2012. You may ...
- 171
7
votes
3
answers
351
views
Breadth-first search for clusters of pixels in a given color range
I am a beginner in programming languages, so I apologise if my code is badly formatted or doesn't make any sense.
My program gets an image and a RGB color range as input and it counts how many pixels ...
- 73
7
votes
2
answers
1k
views
7
votes
1
answer
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 ...
- 440
7
votes
1
answer
755
views
Shortest Path (BFS) through a maze
Background
I have decided to use this year's Advent Of Code to learn Haskell. I feel like I vaguely understand the language and can solve most of the problems with relative ease. However, the code I ...
- 171
6
votes
3
answers
2k
views
Binary Search Tree BFS iteratively
I was given this coding question for a technical interview:
Given a binary tree, implement a method to populate the list
level_ordered_list with the data of the nodes traversed level-order,
...
- 2,469
6
votes
1
answer
738
views
Read CSV and use bidirectional BFS to find the shortest connections between actors
I have a really huge file¹ with 17 million records in it.
Here is a sample of the file:
Actor Movie
1,2
2,2
3,1
4,3
2,3
...
6
votes
3
answers
33k
views
Shortest path using Breadth First Search
I have sample graphs like the following (un-directed un-weighted cyclic graphs). My goal is to find the shortest path between a given source and destination.
I have found this implementation on web ...
- 277
6
votes
2
answers
8k
views
BFS shortest path program
The task was to find the shortest path between P and K in a maze. You can move horizontally and vertically, where # is a wall and ...
- 83
6
votes
1
answer
3k
views
Breadth first search implementation (also includes functions for finding shortest path and number of connected components)
I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the breadth first search section (5.7) using javascript. I also have a ...
- 445
6
votes
1
answer
41k
views
Printing a tree level by level
I have written a program to print a binary tree level by level on different lines, like the tree would actually look if drawn on paper.
I have done a BFS traversal and then I proceed to print the ...
- 333
6
votes
2
answers
115
views
LeetCode 126: Word Ladder II -- Memory limit exceeded
I am trying to solve LC126, and got a memory limit exceeded for the following solution.
I've seen the answer here -- so I'll try to use Dijkstra as well, but I would like to understand why I get the ...
- 300
6
votes
1
answer
968
views
Recursive Breadth First Search for Knights Tour
This was written as an experiment in performance, based on another question here on CodeReview. Input into the algorithm is the number of squares on one edge of the chess board, the point of origin, ...
- 22.3k
6
votes
1
answer
595
views
Minimum number of flight segments using breadth-first search
I'm practising with graphs, and trying to solve a problem of calculating the minimum number of flight segments, applying breadth-first search.
The code is working, but I think, that it's not clean.
...
- 157
6
votes
1
answer
7k
views
Breadth-first search on a tree in Python
The following code performs breadth first search on a mockup tree
...
- 225
6
votes
1
answer
1k
views
Maze solver BFS in Haskell
I am really excited that I just wrote my Haskell maze solution in bfs. This is my very first haskell (and I still haven't tried to build a maze in haskell so that maze is hard coded xD)
ANY ...
- 964
6
votes
1
answer
811
views
Optimizing breadth-first-search code
I wrote code using some kind of breadth-first-search algorithm in order to find a path (any path!) from a start point to an end point. There are no weights/different distances involved from path-to ...
6
votes
1
answer
771
views
Shortest Path in a Unit Cost DAG BFS in Hadoop
Just got done implementing a shortest path algo of a unit cost DAG BFS in Hadoop and wanting to get anyone's opinion on how I could have done it better. The main issue I see is that I lose the ...
- 251
6
votes
1
answer
527
views
Dictrie: Extending the Python dictionary into a Trie
I implemented a trie in Python2.7 as a dictionary of dictionaries by extending the UserDict class to allow native dictionary access syntax and iteration.
For example, ...
- 63
6
votes
1
answer
3k
views
Breadth First Search for a Slider Puzzle Solver
I plan to implement a few other solvers (depth first search, A*, etc), hence why I'm using the abstract base class (which is new to me). I'm using Python 3.6, so you'll see f-string literals. I would ...
- 161
6
votes
1
answer
7k
views
Graph and Node classes with BFS and DFS functions
I've created a Node class and a Graph class
...
- 440
5
votes
3
answers
642
views
SPOJ solution of GRAVITY
I am solving problem GRAVITY on SPOJ. Each test case is a rectangular ASCII grid of dimensions m × n, and you have to determine ...
- 51
5
votes
4
answers
5k
views
Path sum in binary tree
Root to leaf path sum equal to a given number
Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given ...
- 449
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,311
5
votes
2
answers
3k
views
BFS tree traversal Scala
I would love some feedback on the following code for BFS traversal in a binary tree. Is there a cleaner way to write this?
...
- 371