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
Filter by
Sorted by
Tagged with
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
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
2k views

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
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
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
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
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 ...
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
811 views

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 ...
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
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
4k views

I want to improve this code using STL. Let me know if I should add any other function in this code. ...
• 2,449
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
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
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
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: ...
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
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
5k views

(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
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
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
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
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
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
(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 ...