Skip to main content

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
26 votes
3 answers
57k views

BFS Implementation in Python 3

...
Apollo's user avatar
  • 363
25 votes
4 answers
188k 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 ...
fscore's user avatar
  • 634
17 votes
3 answers
7k 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 ...
alecxe's user avatar
  • 17.3k
12 votes
2 answers
598 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 ...
noɥʇʎԀʎzɐɹƆ's user avatar
11 votes
3 answers
1k 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 ...
coderodde's user avatar
  • 28.7k
11 votes
1 answer
6k 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 ...
josfervi's user avatar
  • 167
10 votes
2 answers
3k 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 ...
quartaela's user avatar
  • 505
10 votes
2 answers
309 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 ...
Havenard's user avatar
  • 276
9 votes
4 answers
28k 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. <...
rookie's user avatar
  • 1,233
9 votes
1 answer
10k 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 ...
Hirtol's user avatar
  • 93
9 votes
1 answer
343 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 ...
xaisoft's user avatar
  • 345
9 votes
2 answers
1k views

Python PacMan with son

I have been coding 'Pac-Man' with my 16yo. A hopefully not too boring project to help improve his Python coding. We have just moved the 'Ghosts' into a class which was a good first introduction to ...
Kevin W's user avatar
  • 91
9 votes
1 answer
1k 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 ...
user11881's user avatar
  • 393
9 votes
1 answer
2k views

Maze image solver and animator in Python

This maze solver is a continuation to the maze generator I posted here recently Maze generator & animator in Python This code takes an image containing a 2-color maze as input and solves the maze ...
user avatar
8 votes
2 answers
521 views

Find the first repeating sequence in digits of pi

I wrote a function to return the first n length sequence which occurs twice in the digits of pi. Along with the repeated sequence, I want the indices of the first and second occurrences. For example, ...
cona's user avatar
  • 83
8 votes
2 answers
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 ...
Violet_'s user avatar
  • 81
8 votes
2 answers
9k 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. ...
ruslank's user avatar
  • 145
8 votes
1 answer
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 ...
Tito's user avatar
  • 182
8 votes
1 answer
888 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,...
CIsForCookies's user avatar
7 votes
2 answers
1k 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 ...
Gilad's user avatar
  • 5,311
7 votes
1 answer
945 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)...
Gilad's user avatar
  • 5,311
7 votes
1 answer
901 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 ...
xaisoft's user avatar
  • 345
7 votes
2 answers
13k 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 ...
jatinw21's user avatar
7 votes
2 answers
339 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 ...
Liberul's user avatar
  • 173
7 votes
2 answers
248 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 ...
user avatar
7 votes
2 answers
343 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 ...
wenlong's user avatar
  • 171
7 votes
3 answers
385 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 ...
greenro's user avatar
  • 73
7 votes
2 answers
1k views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
Yksuh's user avatar
  • 71
7 votes
1 answer
99 views

Breadth-first search implementation for finding edge of grid c++

I have implemented a breadth-first search algorithm to find the distance from a point to an edge of a grid. The grid consists of spaces that may have walls between them, effectively blocking certain ...
Andreas Tostrup Christensen's user avatar
7 votes
1 answer
3k 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 ...
123's user avatar
  • 440
7 votes
1 answer
777 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 ...
Bart Platak's user avatar
6 votes
3 answers
2k 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, ...
NinjaG's user avatar
  • 2,469
6 votes
1 answer
772 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 ...
Akshay Aradhya's user avatar
6 votes
3 answers
33k 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 ...
phoenix's user avatar
  • 277
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 ...
Tomislav's user avatar
6 votes
1 answer
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 ...
Daniel Jacobson's user avatar
6 votes
1 answer
41k 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 ...
Aneesh K's user avatar
  • 333
6 votes
2 answers
221 views

LeetCode 126: Word Ladder II -- Memory limit exceeded

I am trying to solve LC126, and got a memory limit exceeded for the following solution. I've seen the answer here -- so I'll try to use Dijkstra as well, but I would like to understand why I get the ...
Mircea's user avatar
  • 322
6 votes
1 answer
986 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, ...
pacmaninbw's user avatar
  • 24k
6 votes
1 answer
705 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. ...
Daniel Chepenko's user avatar
6 votes
1 answer
7k views

Breadth-first search on a tree in Python

The following code performs breadth first search on a mockup tree ...
AlanSTACK's user avatar
  • 225
6 votes
1 answer
1k views

Maze solver BFS in Haskell

I am really excited that I just wrote my Haskell maze solution in bfs. This is my very first haskell (and I still haven't tried to build a maze in haskell so that maze is hard coded xD) ANY ...
Aries_is_there's user avatar
6 votes
1 answer
814 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 ...
badcodingstudent's user avatar
6 votes
1 answer
790 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 ...
Reuben Tanner's user avatar
6 votes
1 answer
574 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, ...
sufjan's user avatar
  • 63
6 votes
1 answer
3k 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 ...
Evan Zamir's user avatar
6 votes
1 answer
8k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
123's user avatar
  • 440
5 votes
3 answers
655 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 ...
noob123's user avatar
  • 51
5 votes
4 answers
5k 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 ...
Mehrdad's user avatar
  • 449
5 votes
3 answers
22k 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? ...
Gilad's user avatar
  • 5,311