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.
25
questions
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
5
votes
1
answer
297
views
Knights Tour - Improved Refactored Recursive Breadth First Search for
The development and testing was performed on a Dell M6400 Laptop (Intel Core 2 Duo) running Centos 7, g++ compiler version 4.8.5, compiler switches -O3 -std=c++0x -D__cplusplus=201103L. (machine ...
- 22.3k
4
votes
0
answers
2k
views
Breadth-first search: traditional and bidirectional in Python - follow-up
I have refactored the version of the previous (and initial) iteration according to the answer by alexwlchan. As a reminder, this snippet compares breadth-first search against its bidirectional variant....
- 26.6k
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
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
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
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
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
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 ...
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
5
votes
1
answer
7k
views
Generalized Missionaries and Cannibals in Java
See the next iteration.
I was in the mood for some basic AI, and decided to code up an algorithm for solving "\$M\$ missionaries, \$C\$ cannibals in the boat with \$B\$ places" -problem:
...
- 26.6k
4
votes
3
answers
4k
views
Breadth First Search using adjacency list
I want to improve this code using STL. Let me know if I should add any other function in this code.
...
- 2,449
4
votes
1
answer
3k
views
(Leetcode) Sliding puzzle in Python
This is a Leetcode problem:
On a 2 x 3 board, there are 5 tiles represented by the integers 1
through ...
- 2,468
4
votes
2
answers
994
views
Javascript Tree Class
I got caught in the trap of implementing my own data structure. I've created a very general tree structure, where each node gets one parent, some children, and holds a value.
I'm mostly looking for ...
- 443
3
votes
1
answer
827
views
Recursive Breadth First Search Knights Tour
This program was written on Windows 7 using Visual Studio 2012 Professional. Some of the issues encountered may have been fixed or changed in a more recent version.
This is a quote from my second ...
- 22.3k
3
votes
1
answer
194
views
Finding smallest number of moves
We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this:
...
user92977
2
votes
1
answer
252
views
Graph radius in Java - follow-up
See the previous and initial iteration.
Terminology
Given an undirected graph \$G = (V, E)\$, the eccentricity of a node \$u \in V\$, \$e(u)\$, is the maximum length (number of edges) of a shortest ...
- 26.6k
2
votes
0
answers
91
views
Breadth-first search in Java: Competitive style - follow-up
I have improved my BFS in Java according to vnp's suggestions. Again, we wish to find shortest paths in directed unweighted graphs using BFS, competitive style (no ...
- 26.6k
1
vote
2
answers
5k
views
Breadth-first search: traditional and bidirectional in Python
(See the next iteration.)
I have this Python (3.4) script for demonstrating the performance of the BFS algorithm, both traditional and bidirectional:
...
- 26.6k
1
vote
1
answer
389
views
Breadth-first search in Java: competitive style
Here my attempt was to write a graph algorithm the way a competitive programmer would write under time pressure. The problem to solve was to find a shortest path in a directed, unweighted graph using ...
- 26.6k
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
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
0
votes
2
answers
189
views
Calculating shortest possible route between two given nodes
I recently came across this problem:
Heroes in Indian movies are capable of superhuman feats. For example,
they can jump between buildings, jump onto and from running trains,
catch bullets with ...
- 389
0
votes
2
answers
559
views
BFS in a grid with wall breaking saldo in Java
In this problem, we are given a 2-dimentional grid, with each cell being walkable or holding a wall. Given an integer \$s \geq 0\$, find the shortest path from the source node to target node breaking ...
- 26.6k
0
votes
1
answer
915
views
Graph radius in Java
(See the next iteration.)
The following snippet is a brute-force algorithm for computing a graph radius in time \$\Theta(V^2 + VE)\$ and space \$\Theta(V)\$ simply by doing \$|V|\$ breadth-first ...
- 26.6k