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.

23 questions
Filter by
Sorted by
Tagged with
700 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, ...
4k 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 ...
1k 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....
760 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 ...
2k 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? ...
871 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 ...
251 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 ...
3k views

I want to improve this code using STL. Let me know if I should add any other function in this code. ...
167 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: ...
89 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 ...
4k 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 ...
66 views

### Wikipath stack in Java - Part I/IV - The search algorithm

I am working on the following small software stack: The objective of the entire stack is to search for shortest paths in the Wikipedia article graph as fast as possible. As of now, I rely on two ...
329 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 ...
5k 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" -algorithm: Demo.java:...
48 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 ...
190 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 ...
81 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 ...
3k views

(See the next iteration.) I have this Python (3.4) script for demonstrating the performance of the BFS algorithm, both traditional and bidirectional: ...
509 views

### Generalized Missionaries and Cannibals in Java - follow-up

See the previous and initial iteration. Now I have incorporated all the points suggested by mdfst13, and have the following: StateNode.java: ...
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 ...
350 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 ...
(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 ...