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
1
vote
1
answer
2k
views
Finding the node with the smallest maximum distance to all the other nodes
This code is supposed to find, in a graph, the node with the smallest maximum distance to all the other nodes. The problem from Quora is :
How do I find the node that has the least maximum distance ...
- 11
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
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
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
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
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
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 ...
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
1
vote
1
answer
5k
views
Crawl multiple pages at once
This an update to my last question.
I want to process multiple pages at once pulling URLs from tier_list in the crawl_web ...
- 111
1
vote
2
answers
1k
views
Basic search engine
I want to improve efficiency of this search engine. It works in about 10 seconds for a search depth of 1, but 4 minutes at 2 etc.
I tried to give straightforward comments and variable names, any ...
- 111
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
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
5
votes
2
answers
2k
views
Print binary search tree by levels function implementation
I do not like this implementation as is seems too much complicated. My idea was to implement some BFS algorithm variant.
Some points to notice:
I use one queue.
In the begining put the tree ...
- 281
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
5
votes
1
answer
156
views
BFS implementation that walks a tile-based field
I wrote a BFS implementation that walks a tile-based field. It takes a function that should return true for walkable tiles and false for walls. It also takes the start and end points. It currently ...
- 377
5
votes
1
answer
3k
views
Binary tree level order traversal algoritm
I am trying to solve this Binary tree lever order traversal:
...
- 171
5
votes
1
answer
471
views
Modified BFS code optimizations
I need some help reviewing this code in terms of making as fast as possible. This is a modified version of BFS that does quite a bit of processing on the side.
Use case:
I have a large graph (...
- 215
3
votes
1
answer
2k
views
Solve a maze in the form of a 2D array using BFS - Haskell
Suggestions for improving coding style are greatly appreciated.
...
- 201
4
votes
2
answers
1k
views
Time Limit Exceeded in BFS maze solver
Here's a problem that I tried solving:
Lakshagraha was a house built of lacquer, made by the Kauravas to kill
the Pandavas. The Kauravas wanted to burn the house down when the
Pandavas were ...
- 41
0
votes
1
answer
4k
views
Breadth-first tree traversal using STL list
I am writing code for breadth-first search of a tree with C++'s STL. Please help as I am new to the STL.
...
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
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
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
3
votes
1
answer
783
views
BFS implementation to find connected components taking too long
This is in continuation to a question I asked here. Given the total number of nodes (employees) and the adjacency list (friendship amongst employees), I need to find all the connected components.
<...
- 141
4
votes
4
answers
6k
views
Shortest path in a grid between two points
I have this problem where I have to find the shortest path in an NxM grid from point A (always top left) to point B (always bottom right) by only moving right or down. Sounds easy, eh? Well here's the ...
- 233
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
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
5
votes
2
answers
2k
views
Pouring water problem
I just began to study Scala (coming from Python I had quite a few problems with types) and I want to know if my first code to solve a real problem is nicely done or if there is some points that need ...
- 183
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