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.
180
questions
0
votes
1
answer
299
views
BFS Pathfinding algorithm using Javascript generator
I'm implementing a BFS traversal in a grid-like structure. Because I wanted to experiment with ES6 Generators for a long time, I thought I'd implement the search using that abstraction.
I am sure ...
- 131
3
votes
1
answer
242
views
Flood Fill using unordered_map which has user-defined type as key
I have an implementation of the flood fill algorithm. Assume that an image is provided as a vector of ...
- 539
2
votes
3
answers
1k
views
Find maximum area of island in matrix
I recently solved the problem below from leetcode:
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical)....
- 313
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 ...
- 5,311
9
votes
1
answer
9k
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
0
votes
1
answer
1k
views
Print BFS implementation in JavaScript
Given a graph and a starting vertex print the value of each vertex in a breadth first order.
Let's code out a general BFS algorithm printing each vertex's value in a BFS order. We are given a graph ...
- 2,469
5
votes
1
answer
15k
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 ...
- 2,469
7
votes
2
answers
12k
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
4
votes
1
answer
524
views
Bidirectional BFS on a matrix in Python 2.7
This code is a bidirectional BFS search. Given any two points in a matrix having 0's and 1's, I would like to find if there exists a path between them. Also note that it is forbidden to enter a cell ...
- 179
1
vote
1
answer
11k
views
Perform BFS on a Binary Tree
Task: Perform Breadth first traversal on a Binary Search Tree and print the elements traversed.
...
- 1,731
4
votes
3
answers
4k
views
Breadth First Search using adjacency list
I want to improve this code using STL. Let me know if I should add any other function in this code.
...
- 2,449
3
votes
1
answer
2k
views
BFS to check if path from start node to end node exists
I'm trying to solve a problem from leetcode called Jump Game and it seems to be a pretty simple graph problem where we have to find if a path exists from a start node to an end node. I personally ...
- 151
2
votes
1
answer
13k
views
Directed Graph Implementation in Java
Here I've attached my java implementation of a directed graph. I've used a modified adjacency-list mechanic to utilize a map instead of a list for quicker lookup times. Looking for comments / ...
- 131
4
votes
1
answer
219
views
Finding many paths in a graph
I have a graph which we can think of is representing a network of train tracks. Each node is a station and each edge is a piece of track connecting two stations. Each station node may be connected by ...
- 1,342
6
votes
1
answer
738
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
...
2
votes
1
answer
2k
views
Binary Search Tree Implementation in Java
Looking for critiques on my BST implementation, particularly to check if I'm building the common operational methods and traversal algorithms properly. Code has been lightly tested, and I've tried to ...
- 131
3
votes
1
answer
6k
views
C++ breadth-first search using adjacency matrix
I have written this Breadth First Search program using Adjacency Matrix, taking help from Introduction to Algorithm(CLSR) and from Internet.
I want to optimise this code.
...
- 2,449
6
votes
1
answer
527
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
1
vote
0
answers
730
views
BFS Algorithm in JavaScript
I am new to Trees and BFS/DFS as well as programming and I decided to play around to learn how to traverse trees.
I did not want to use the shift() JavaScript ...
- 11
1
vote
1
answer
463
views
I want to check neighborhoods of cell in two dimensional array in C++
I want to write a function which will return all possible/valid 'X' moves around my Target cell depending on it position inside the following two dimensional array.
...
- 19
8
votes
1
answer
874
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,...
- 351
3
votes
1
answer
6k
views
Recursive BFS solution for tree traversal
I'm somewhat new to the wonderful world of Python, outside of simple codecademy-like challenges online.
This function was part of a project for school. It's tested and works, but I'm looking for some ...
- 55
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,
...
- 2,469
3
votes
1
answer
2k
views
Breadth- and Depth- First Search in C#
Another recreational implementation for review! As a side comment, for some reason I just feel like if (visited.Contains(vertex)) { .. } isn't necessary, as this ...
- 3,045
2
votes
0
answers
1k
views
Cut Off Trees for Golf Event LeetCode challenge
I solved this LeetCode Challenge:
You are asked to cut off trees in a forest for a golf event. The forest
is represented as a non-negative 2D map, in this map:
0 represents the obstacle can'...
- 1,148
4
votes
2
answers
1k
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(...
- 539
3
votes
1
answer
408
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
2
answers
22k
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 ...
- 103
5
votes
2
answers
693
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:
...
- 161
7
votes
2
answers
269
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
4
votes
2
answers
1k
views
Python breadth first search algorithm
Any pointers, or any advice on how to clean up my code/make more pythonic would be appreciated.
...
- 181
7
votes
2
answers
1k
views
3
votes
1
answer
2k
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:
...
3
votes
1
answer
2k
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 ...
- 199
4
votes
2
answers
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?
...
- 1,281
17
votes
3
answers
6k
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.2k
4
votes
1
answer
4k
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 ...
- 2,386
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 ...
- 440
1
vote
2
answers
252
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. ...
- 11
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 ...
- 161
2
votes
0
answers
2k
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,386
2
votes
1
answer
302
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. ...
- 17.2k
3
votes
1
answer
115
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 ...
- 133
11
votes
1
answer
5k
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
0
votes
2
answers
559
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 ...
- 26.7k
6
votes
1
answer
596
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.
...
- 157
1
vote
0
answers
2k
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
2
answers
7k
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 ...
- 2,386
12
votes
2
answers
589
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
7
votes
1
answer
755
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