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
1 vote
1 answer
47 views

performance - Word ladder leetcode

I am working on Word Ladder - LeetCode Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: ...
user avatar
0 votes
0 answers
96 views

Parallel BFS OpenMP C

I'm trying to develop the code to make a parallel version of the BFS (topDown) algorithm on a graph. This is the code I have developed so far: ...
user avatar
0 votes
1 answer
57 views

Find the shortest path from bottom left to top right in a maze using dfs and bfs algorithm

The following code is applying the depth-first search and breadth-first search algorithm to find the shortest path from bottom left to top right in a 10 x 10 grid. ...
user avatar
0 votes
0 answers
49 views

Binary Tree DFS and BFS traversalsclass [python3]

There are six Binary Tree DFS traversals (preorder, inorder, postorder, and their reverse counterparts). Their implementations can be very similar 1, so I factored out the core logic into a class <...
user avatar
  • 243
1 vote
0 answers
102 views

How to create a maze solve search with BFS provide navigation movements

How should I structure this code to create a maze, solve it with breath-first-search (BFS) and to provide basic navigation movements by 1 step within maze with number of moves required to navigate? ...
user avatar
  • 11
4 votes
1 answer
183 views

Breadth first search on trees in Haskell

I'm writing a breadth first search algorithm in Haskell that supports pruning. It is guaranteed that the search will never encounter nodes that have been visited before, so I implemented the search as ...
user avatar
  • 141
1 vote
1 answer
55 views

PureScript breadth-first search implementation

For context, I wrote a function, get_servers, for the game Bitburner which is usually played by writing JavaScript code. Instead, I used PureScript to write the ...
user avatar
  • 259
3 votes
0 answers
276 views

2D Map Optimization via Beam Search in Python

This is a problem based on the game "NGU Industries" in which the objective is to build a factory. Each tile can hold either a production building or a "beacon" which increases the ...
user avatar
7 votes
2 answers
216 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, ...
user avatar
  • 73
3 votes
0 answers
53 views

Breadth First Search Block Puzzle

I am creating a program that will be given a text file as output with the board's dimension and the piece id along with the piece width and length. The goal is to arrange all blocks in the board ...
user avatar
  • 39
9 votes
2 answers
327 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 ...
user avatar
  • 91
1 vote
0 answers
40 views

Breadth first search of a binary-tree with channels

As an exercise in using channels in Go I implemented a breadth-first traversal of a binary tree, using a channel as a queue to store the order of the nodes to traverse. After ironing out a bunch of ...
user avatar
  • 111
5 votes
1 answer
239 views

01 Matrix is too slow when solved using DFS

I tried solving Leetcode 01 Matrix problem. It is running too slow when solved using DFS approach. Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance ...
user avatar
  • 129
4 votes
1 answer
148 views

K-clustering algorithm using Kruskal MST with Disjoint Set in place to check for cycles

here below a working implementation that finds the minimal distance between k(set =4 below) clusters in a graph. I have doubts mainly on the implementation of the ...
user avatar
  • 331
4 votes
1 answer
222 views

Generating unique 2D numpy arrays with 2 adjacent row elements swapped while using BFS in Python

So I have a 12 x 6 2D numpy array for input which consists of 7 possible board objects (characters from 'abcdefg'). From a 2D numpy array I wish to generate all the possible unique 2D arrays, in whose ...
user avatar
  • 41
3 votes
0 answers
135 views

Breadth First Search Python Implementation

I have the below implementation of the BFS algorithm, in which I've used OrderedDict instead of a list or ...
user avatar
  • 413
1 vote
0 answers
157 views

Routes Between Node, Cracking the coding interview

I am going though Cracking the coding interview and trying to improve my coding interview skills. The question is "Given a directed graph, design an algorithm to find out whether there is a route ...
user avatar
1 vote
1 answer
72 views

Depth First Search vs Breadth First Search

So after years of teaching myself, I think I'm ready to stand on the shoulders of giants and ask you a good question! I have a tree of nodes. What I want is a function that returns an array of the ...
user avatar
  • 143
2 votes
0 answers
160 views

Parsing a Graph To Convert It Into Adjacency Lists And CSR And Then Make Connection Queries Using Bidirectional BFS

I was assigned an university project where I had to parse directed graph files coming from SNAP and then convert them into CSR (Compressed Sparse Row) format. Then the client must have the ability to ...
user avatar
  • 165
1 vote
0 answers
64 views

Minimum router Peripherality Breadth First Search (BFS) Algorithm performance

I have solved the MinRouterPeripherality task in codility using javascript using Breadth First Search(BFS) approach. However time complexity is O(N^2). I am really ...
user avatar
2 votes
1 answer
63 views

Is this breadth-first search correct?

I wrote a program that is supposed to be a breadth-first search algorithm, but I'm very new to search algorithm so I don't know if my method is very effective or if there is a simpler way to do this. ...
user avatar
  • 29
3 votes
1 answer
190 views

Finding shortest path in matrix

Given an N x N matrix of positive integers, I need to find the shortest path from the first cell of matrix to the last cell of matrix. I can move exactly x steps from any cell, where x is the value of ...
user avatar
1 vote
2 answers
467 views

Breadth-first search(BFS) Implementation in Python 3 [closed]

I have implemented a BFS. Does this look like a proper implementation of BFS in Python 3? And if you think something needs to be improved, say it. ...
user avatar
4 votes
1 answer
618 views

LeetCode: Rotting Oranges in C#

https://leetcode.com/problems/rotting-oranges/ Please review for coding style in 40 minutes job interview. In a given grid, each cell can have one of three values: the value 0 representing an ...
user avatar
  • 5,249
9 votes
1 answer
1k 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
3 votes
2 answers
255 views

Determine if a string is a sequence of dictionary words

This is Leetcode problem 139: "Wordbreak" Problem: Given a non-empty string s and a dictionary wordDict containing a list ...
user avatar
  • 109
1 vote
0 answers
48 views

Typesetting bidirectional breadth first search with Algotype.js

So I have this: And the typesetting code is here: ...
user avatar
  • 25.3k
3 votes
1 answer
50 views

Javascript Tree Class 2

This question is the second version of the code here. I'm writing a general tree class. Specifically, each node should have oen parent, some number of children, and hold a value. I'm looking for ...
user avatar
  • 443
4 votes
2 answers
883 views

Javascript Tree Class

I got caught in the trap of implementing my own data structure. I've created a very general tree structure, where each node gets one parent, some children, and holds a value. I'm mostly looking for ...
user avatar
  • 443
1 vote
1 answer
47 views

Optimising the BFS

The input graph to the bfs function is in the form of edge list representation. ...
user avatar
  • 111
4 votes
1 answer
443 views

(Leetcode) Snakes and Ladders

This is a Leetcode problem - On an \$N\$ x \$N\$ board, the numbers from 1 to N * N are ...
user avatar
  • 2,460
4 votes
2 answers
685 views

(Leetcode) Escape a large maze

This is a Leetcode problem - In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with \$0\$ \$<=\$ ...
user avatar
  • 2,460
1 vote
1 answer
300 views

(Leetcode) K-similar strings in Python

This is a Leetcode problem - Strings A and B are K-similar (for some non-negative integer ...
user avatar
  • 2,460
4 votes
1 answer
2k views

(Leetcode) Sliding puzzle in Python

This is a Leetcode problem: On a 2 x 3 board, there are 5 tiles represented by the integers 1 through ...
user avatar
  • 2,460
3 votes
1 answer
114 views

Leetcode: Find-bottom-left-tree-value

https://leetcode.com/problems/find-bottom-left-tree-value/ Given a binary tree, find the leftmost value in the last row of the tree. Example 1: Input: ...
user avatar
  • 5,249
2 votes
1 answer
124 views

LeetCode: Employee-importance BFS

You are given a data structure of employee information, which includes the employee's unique id, his importance value and his direct subordinates' id. For example, employee 1 is the leader of ...
user avatar
  • 5,249
3 votes
1 answer
355 views

Rubik's Cube in Java

I have this Java implementation of a Rubik's cube's state. My primary concern is DRYness of my code: RubiksCubeNode.java ...
user avatar
  • 25.3k
2 votes
0 answers
85 views

Breadth-first search in Java: Competitive style - follow-up

I have improved my BFS in Java according to vnp's suggestions. Again, we wish to find shortest paths in directed unweighted graphs using BFS, competitive style (no ...
user avatar
  • 25.3k
1 vote
2 answers
340 views

LeetCode: N-ary Tree Level Order Traversal

https://leetcode.com/problems/n-ary-tree-level-order-traversal/ Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example, ...
user avatar
  • 5,249
3 votes
3 answers
774 views

LeetCode: maximum-depth-of-n-ary-tree

https://leetcode.com/problems/maximum-depth-of-n-ary-tree/ Given a n-ary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the ...
user avatar
  • 5,249
1 vote
1 answer
363 views

Breadth-first search in Java: competitive style

Here my attempt was to write a graph algorithm the way a competitive programmer would write under time pressure. The problem to solve was to find a shortest path in a directed, unweighted graph using ...
user avatar
  • 25.3k
4 votes
1 answer
289 views

Object-Oriented Breadth-First Search Implementation

My goal is to write a GUI application where a user can create a maze and select an algorithm. The passage of the algorithm from a selected start and end point should be visualized. The following ...
user avatar
  • 2,498
1 vote
0 answers
7k views

Find the shortest path between two points in a 2D matrix with obstacles

I need to find shortest path between two points in a grid given an obstacles.. Given a 2 dimensional matrix where some of the elements are filled with 1 and rest of the elements are filled. Here ...
user avatar
4 votes
1 answer
70 views

Find the longest connect cells region per color

I have been studying graphs/BFS/DFS. working on wrapping my head around the following problem Given a grid [m,n] where each cell has a value denotes a color, find the longest connected region that ...
user avatar
3 votes
1 answer
3k views

Java breadth-first search for finding the shortest path on a 2D grid with obstacles

Please review my Breadth-first search algorithm implementation in Java for finding the shortest path on a 2D grid map with obstacles. The findPath() method ...
user avatar
6 votes
1 answer
906 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 ...
user avatar
4 votes
1 answer
2k views

Pramp: Sales path

the question is taken from Pramp(really cool site!) there is a more straight forward solution. using recursion. but I thought trying it using BFS. please review only the code of GetCheapestCost ...
user avatar
  • 5,249
0 votes
1 answer
222 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 ...
user avatar
3 votes
1 answer
217 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 ...
user avatar
  • 509
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)....
user avatar