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
3
votes
1answer
72 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 ...
2
votes
0answers
38 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 ...
1
vote
0answers
44 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 ...
1
vote
1answer
59 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 ...
2
votes
0answers
59 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 ...
1
vote
0answers
35 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 ...
2
votes
1answer
55 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. ...
3
votes
1answer
97 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 ...
1
vote
2answers
198 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. ...
4
votes
1answer
517 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 ...
9
votes
1answer
484 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 ...
3
votes
2answers
119 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 ...
1
vote
0answers
41 views

Typesetting bidirectional breadth first search with Algotype.js

So I have this: And the typesetting code is here: ...
3
votes
1answer
43 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 ...
3
votes
2answers
196 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 ...
1
vote
1answer
42 views

Optimising the BFS

The input graph to the bfs function is in the form of edge list representation. ...
4
votes
1answer
210 views

(Leetcode) Snakes and Ladders

This is a Leetcode problem - On an \$N\$ x \$N\$ board, the numbers from 1 to N * N are ...
4
votes
2answers
327 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\$ \$<=\$ ...
1
vote
1answer
129 views

(Leetcode) K-similar strings in Python

This is a Leetcode problem - Strings A and B are K-similar (for some non-negative integer ...
4
votes
1answer
684 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 ...
3
votes
1answer
97 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: ...
2
votes
1answer
98 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 ...
3
votes
1answer
156 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 ...
2
votes
0answers
71 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 ...
1
vote
2answers
215 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, ...
3
votes
3answers
318 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 ...
1
vote
1answer
226 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 ...
4
votes
1answer
184 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 ...
1
vote
0answers
5k 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 ...
4
votes
1answer
59 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 ...
3
votes
1answer
2k 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 ...
6
votes
1answer
382 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 ...
3
votes
1answer
586 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 ...
0
votes
1answer
118 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 ...
3
votes
1answer
171 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 ...
2
votes
3answers
670 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)....
7
votes
2answers
677 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 ...
9
votes
1answer
6k 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 ...
0
votes
1answer
866 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 ...
5
votes
1answer
8k 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 ...
7
votes
2answers
7k 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 ...
4
votes
1answer
442 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 ...
1
vote
1answer
6k views

Perform BFS on a Binary Tree

Task: Perform Breadth first traversal on a Binary Search Tree and print the elements traversed. ...
4
votes
3answers
3k 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. ...
3
votes
1answer
915 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 ...
2
votes
1answer
9k 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 / ...
4
votes
1answer
177 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 ...
6
votes
1answer
581 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
1answer
902 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 ...
3
votes
1answer
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. ...