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
21
votes
4answers
184k 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 ...
15
votes
2answers
36k views

BFS Implementation in Python 3

...
15
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 ...
12
votes
2answers
438 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 ...
11
votes
3answers
973 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 ...
10
votes
2answers
2k 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 ...
10
votes
2answers
202 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 ...
9
votes
1answer
3k views

Solve 8-tile sliding puzzle

I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which ...
9
votes
1answer
895 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 ...
8
votes
1answer
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 ...
8
votes
1answer
3k 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 ...
8
votes
1answer
379 views

Beginner's Knight's tour in Python (BFS)

I wanted to implement this as short and effective as I could without using anything that is not basics, in order to improve my skills. I would appreciate input about things like memory leaks I missed,...
7
votes
2answers
458 views

Iterator for BFS binary tree traversal

I implemented an iterator pattern for C# using IEnumerator and IEnumerable. The goal of the implementation is to traverse a ...
7
votes
4answers
19k 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. <...
7
votes
1answer
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 ...
7
votes
2answers
176 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 ...
7
votes
2answers
3k views

Breadth First Search implementation in Python 3 to find path between two given nodes

This is my Breadth First Search implementation in Python 3 that assumes cycles and finds and prints path from start to goal. Some background - Recently I've been preparing for interviews and am ...
7
votes
2answers
202 views

Search for Tree

Here is a search implementation for my tree. It searches each node in a breadth-first manner first, but it goes deeper in a depth-first manner, in the event it needs to go deeper. I know there may ...
7
votes
2answers
333 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 ...
7
votes
3answers
303 views

Breadth-first search for clusters of pixels in a given color range

I am a beginner in programming languages, so I apologise if my code is badly formatted or doesn't make any sense. My program gets an image and a RGB color range as input and it counts how many pixels ...
7
votes
2answers
976 views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
7
votes
1answer
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 ...
6
votes
1answer
510 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
1answer
838 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)...
6
votes
2answers
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 ...
6
votes
1answer
3k views

Breadth first search implementation (also includes functions for finding shortest path and number of connected components)

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the breadth first search section (5.7) using javascript. I also have a ...
6
votes
1answer
36k views

Printing a tree level by level

I have written a program to print a binary tree level by level on different lines, like the tree would actually look if drawn on paper. I have done a BFS traversal and then I proceed to print the ...
6
votes
1answer
237 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. ...
6
votes
2answers
5k 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. ...
6
votes
1answer
5k views

Breadth-first search on a tree in Python

The following code performs breadth first search on a mockup tree ...
6
votes
1answer
761 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 ...
6
votes
1answer
384 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 ...
6
votes
1answer
691 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 ...
6
votes
1answer
201 views

Dictrie: Extending the Python dictionary into a Trie

I implemented a trie in Python2.7 as a dictionary of dictionaries by extending the UserDict class to allow native dictionary access syntax and iteration. For example, ...
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 ...
6
votes
1answer
4k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
5
votes
3answers
589 views

SPOJ solution of GRAVITY

I am solving problem GRAVITY on SPOJ. Each test case is a rectangular ASCII grid of dimensions m × n, and you have to determine ...
5
votes
3answers
1k views

Binary Search Tree BFS iteratively

I was given this coding question for a technical interview: Given a binary tree, implement a method to populate the list level_ordered_list with the data of the nodes traversed level-order, ...
5
votes
3answers
28k views

Shortest path using Breadth First Search

I have sample graphs like the following (un-directed un-weighted cyclic graphs). My goal is to find the shortest path between a given source and destination. I have found this implementation on web ...
5
votes
3answers
20k 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
votes
2answers
3k views

Path sum in binary tree

Root to leaf path sum equal to a given number Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given ...
5
votes
1answer
12k views

DFS/BFS implementation of Cormen's pseudo code

This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this. ...
5
votes
2answers
271 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: ...
5
votes
1answer
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, ...
5
votes
1answer
3k views

Searching a maze using DFS and BFS in Python 3

I solved the problem posted from Make School Trees and Maze article, which asks me to searching a maze using DFS and BFS in Python. Here's the final output from PyGame: I would like to ask for code ...
5
votes
2answers
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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:...
5
votes
2answers
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 ...