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.

182 questions
Filter by
Sorted by
Tagged with
57k views

...
• 363
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 ...
• 634
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 ...
• 17.3k
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 ...
• 349
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 ...
• 28.7k
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 ...
• 167
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 ...
• 505
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 ...
• 276
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. <...
• 1,233
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 ...
• 93
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 ...
• 345
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 ...
• 91
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 ...
• 393
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 ...
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, ...
• 83
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 ...
• 81
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. ...
• 145
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 ...
• 182
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,...
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 ...
• 5,311
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)...
• 5,311
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 ...
• 345
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 ...
• 73
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 ...
• 173
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 ...
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 ...
• 171
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 ...
• 73
1k views

DFS and BFS in a graph in C++

Here goes the depth first search: ...
• 71
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 ...
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 ...
• 440
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 ...
• 171
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, ...
• 2,469
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 ...
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 ...
• 277
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
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 ...
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 ...
• 333
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 ...
• 322
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, ...
• 24k
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. ...
7k views

Breadth-first search on a tree in Python

The following code performs breadth first search on a mockup tree ...
• 225
1k views

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 ...
814 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 ...
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 ...
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, ...
• 63
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 ...
• 161
8k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
• 440
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 ...
• 51
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 ...
• 449