The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.

Filter by
Sorted by
Tagged with
3
votes
2answers
694 views

Given two words and a dictionary's word list, find all shortest transformation sequence

This is a leetcode problem (https://leetcode.com/problems/word-ladder-ii/description/) Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(...
3
votes
1answer
325 views

Searching an exit in a matrix map using breadth-first search algorithm

I'm trying to solve an online problem about breadth-first search algorithm. The problem can be resumed as: Given height and width of a map, read the map where "S" is your initital position, "x" is ...
2
votes
2answers
8k views

Using BFS to solve 8-puzzle game using Python 2

I'm trying to solve the 8-puzzle game using BFS, DFS and A* algorithms implemented using Python 2.7. For now, I have managed to solve a couple of test cases using BFS and I want to know how I can ...
5
votes
2answers
306 views

Modifying list while iterating during Breadth-first search

I am writing a function for implementing breadth-first search over a no. of nodes in a directed graph. The nodes are all numbers from 1-100. This is my implementation: ...
7
votes
2answers
183 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 ...
4
votes
2answers
915 views

Python breadth first search algorithm

Any pointers, or any advice on how to clean up my code/make more pythonic would be appreciated. ...
7
votes
2answers
1k views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
3
votes
1answer
693 views

Performance of BFS in Python 3

How can I increase speed performance of this Python 3 programming challenge? Find the shortest path from one point to another (last line) Example: ...
2
votes
1answer
1k views

Word Ladder JavaScript Implementation

For a big dictionary, the following code gives a time limit error. I was trying to use ES6 constructs in the code. The inputs that gave TLE are here. I have tried to use BFS for the problem, adding ...
4
votes
2answers
2k views

Depth and breadth first search

I am practicing interview questions, I wrote this code to perform BFS and DFS on a graph in Python. How can it be optimized, and how can it be made more readable? ...
16
votes
3answers
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 ...
4
votes
1answer
1k views

Hackerrank: KnightL on a Chessboard

Problem statement KnightL is a chess piece that moves in an L shape. We define the possible moves of KnightL(a,b) as any movement from some position (x1, y1) to ...
5
votes
1answer
2k 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 ...
1
vote
2answers
158 views

Java sequential BFS

I am currently working on optimizing my code. In order to do that, I have to make sure that my sequential BFS works perfectly. Then, I should I apply threads or executor service to run it in parallel. ...
6
votes
1answer
1k 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 ...
2
votes
0answers
1k views

Leetcode 317: Shortest distance from all buildings

Problem statement: You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a ...
2
votes
1answer
183 views

The BFS approach to the SmartWordToy challenge

I'm currently working on solving the SmartWordToy TopCoder problem: The toy company "I Can't Believe It Works!" has hired you to help develop educational toys. ...
3
votes
1answer
94 views

Storing configurations of states to a database - Breadth First Search

I have wrote some code to store all possible configurations of a set of numbers in the sliding tile puzzle but the process of doing slow is very slow. Say, for instance, I have a sliding tile puzzle ...
8
votes
1answer
4k 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 ...
0
votes
2answers
368 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 ...
6
votes
1answer
253 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. ...
1
vote
0answers
1k views

Breadth-First Search in C: Maze-like use of 2D arrays, linked list

Problem: In a grid of nodes pick a starting node(has mode2), and using Breadth-First search, find one with a ending node (has mode1). You can make walls so it's harder for the search. And that ...
1
vote
2answers
1k views

Hackerrank: Connected Cells in a Grid

Problem statement Consider a matrix with \$n\$ rows and \$m\$ columns, where each cell contains either a \$0\$ or a \$1\$ and any cell containing a is called a filled cell. Two cells are said to be ...
12
votes
2answers
447 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 ...
6
votes
1answer
400 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 ...
3
votes
1answer
2k views

BFS' shortest path unweighted directed graph

The code I have is based on BFS and a little bit of Dijkstra and returns the shortest path of an unweighted directed graph as an integer. I was wondering if someone could take a look at my code too ...
6
votes
1answer
4k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
3
votes
2answers
670 views

CLRS Implementation of BFS and DFS in C++

I tried to implement BFS and DFS from Introduction to Algorithms by Cormen. Any suggestions on how to improve my code? GraphStructures.h ...
4
votes
1answer
1k views

Implementation of BFS on a graph

I have written the code below as a BFS implementation. Could someone please review. In particular, I want to know if there could be a memory leak. ...
2
votes
1answer
1k views

Get a path between graph nodes using breadth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using breadth-first search. I'm doing this to improve my style ...
0
votes
2answers
145 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 ...
1
vote
0answers
61 views

Thread pool based unweighted path finder in Java for graphs with slow expansion operator

Introduction Given a directed unweighted graph, the objective of this library is to find a shortest path from a given source node to a given target node. Clearly, one candidate algorithm to find ...
1
vote
0answers
99 views

Efficient keyword trie implementation in C++ with failure/output links

For a current project implementing a parser for a bifurcation analysis tool, I wanted to utilize a keyword trie based solution, as there are possibly a ton of user supplied keywords. However, i found ...
1
vote
1answer
1k views

JavaScript breadth-first search algorithm

I have implemented a breadth-first search and I'm more or less looking for suggestions on how I can improve on what I've done here. How to use: ...
1
vote
1answer
9k views

Print tree level by level including Empty node

Here is my code to print tree in a level by level way. It needs to print an empty node as well to keep tree structure like full binary tree for elegancy reasons. I'm wondering if anything you think ...
1
vote
0answers
68 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 ...
3
votes
3answers
5k views

Create a complete binary tree and do level order traversal on it

How can I optimize this code? ...
17
votes
2answers
40k views

BFS Implementation in Python 3

...
3
votes
0answers
50 views

LinkedList of Nodes at each level - optimalization

That's already known problem: to return an array of linked lists that contain values of elements at each level. Eg for tree with depth n there should be n linked lists. I wrote the solution: ...
3
votes
1answer
581 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 ...
2
votes
2answers
302 views

Finding the Least Common Ancestor of a Binary Tree

Input a binary tree (the root node) and 2 other nodes that need to be assessed for finding the least common ancestor (LCA) Code: a. Finding the nodes first with either ...
5
votes
1answer
252 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 ...
2
votes
1answer
62 views

ExtensionMethods for iterating hierarchically data structures depth/breath-first

I wrote a few simple extension methods that allow to traverse a hierachically data structure depth-first or breath-first using LINQ: Usage: ...
6
votes
2answers
6k 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. ...
3
votes
0answers
1k 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....
6
votes
1answer
6k views

Breadth-first search on a tree in Python

The following code performs breadth first search on a mockup tree ...
5
votes
1answer
712 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, ...
3
votes
1answer
169 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: ...
9
votes
1answer
915 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 ...
8
votes
2answers
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 ...