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
5
votes
1
answer
295
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 ...
CommunityBot
- 1
5
votes
1
answer
7k
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" -problem:
...
- 26.7k
1
vote
0
answers
25
views
Figure out all paths of all nodes up to k depth
I'm trying to figure out all the paths of all the nodes up to K depth.
It seems to be a dynamic programming problem, my attempt seems to be working however its slower than I expected
I would think ...
- 111
4
votes
1
answer
578
views
Find center of an undirected graph
Task: implement an algorithm to find graph center \$Z(G)\$ given undirected tree \$G\$.
This is my first time programming in C++ so any (elementary) feedback is appreciated.
The way I did it is:
Run ...
- 44.8k
6
votes
2
answers
116
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 ...
- 69.1k
1
vote
1
answer
130
views
Optimizing BFS code to find connected components in a graph
I am writing a Python code to find the connected components of a graph using BFS. The code works but takes a long time to run. Please suggest possible optimizations of my code.
The graph is stored as ...
- 131
1
vote
1
answer
141
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:
...
- 11.8k
0
votes
0
answers
590
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:
...
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 ...
- 3,336
1
vote
0
answers
137
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? ...
- 5,499
0
votes
1
answer
210
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. ...
- 7,646
1
vote
1
answer
66
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 ...
- 719
7
votes
2
answers
342
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, ...
- 33k
3
votes
0
answers
336
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 ...
- 479
3
votes
0
answers
84
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 ...
- 39
9
votes
2
answers
594
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 ...
- 42.3k
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 ...
4
votes
2
answers
994
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 ...
- 724
1
vote
0
answers
106
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 ...
- 111
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 ...
CommunityBot
- 1
5
votes
1
answer
464
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 ...
- 921
4
votes
1
answer
233
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 ...
- 331
4
votes
1
answer
262
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 ...
- 1,471
4
votes
1
answer
674
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 ...
Mast♦
- 13k
1
vote
0
answers
175
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 ...
- 6,393
3
votes
0
answers
174
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 ...
- 9,832
26
votes
3
answers
55k
views
1
vote
1
answer
77
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 ...
CommunityBot
- 1
2
votes
0
answers
236
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 ...
- 165
2
votes
1
answer
69
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. ...
- 1,240
1
vote
0
answers
77
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 ...
- 278
3
votes
1
answer
253
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 ...
- 558
1
vote
0
answers
55
views
Typesetting bidirectional breadth first search with Algotype.js
So I have this:
And the typesetting code is here:
...
- 26.7k
4
votes
1
answer
499
views
(Leetcode) Snakes and Ladders
This is a Leetcode problem -
On an \$N\$ x \$N\$ board, the numbers from 1 to N * N are
...
- 9,832
1
vote
2
answers
547
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.
...
- 9,775
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 ...
CommunityBot
- 1
3
votes
2
answers
384
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 ...
- 69.1k
3
votes
1
answer
51
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 ...
- 13.9k
1
vote
1
answer
57
views
Optimising the BFS
The input graph to the bfs function is in the form of edge list representation.
...
CommunityBot
- 1
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
4
votes
1
answer
318
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 ...
- 2,773
3
votes
1
answer
660
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
...
CommunityBot
- 1
4
votes
2
answers
817
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\$ \$<=\$ ...
- 33k
4
votes
1
answer
3k
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 ...
- 34.8k
2
votes
1
answer
347
views
(Leetcode) K-similar strings in Python
This is a Leetcode problem -
Strings A and B are K-similar (for some non-negative integer
...
- 29.1k
3
votes
1
answer
120
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:
...
- 110k
2
votes
2
answers
417
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, ...
- 13.9k
4
votes
3
answers
844
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 ...
- 13.9k
2
votes
1
answer
131
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 ...
CommunityBot
- 1
1
vote
1
answer
389
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 ...
- 26.7k