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.

151 questions
Filter by
Sorted by
Tagged with
20 views

### Optimising the BFS

The input graph to the bfs function is in the form of edge list representation. ...
350 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'...
136 views

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 ...
36 views

This is a Leetcode problem - On an $N$ x $N$ board, the numbers from 1 to N * N are ...
94 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 ...
138 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$ $<=$ ...
105 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 ...
69 views

### (Leetcode) K-similar strings in Python

This is a Leetcode problem - Strings A and B are K-similar (for some non-negative integer ...
69 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: ...
112 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, ...
120 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 ...
78 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 ...
88 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 ...
50 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 ...
442 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 ...
3k 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 ...
56 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 ...
1k 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 ...
5k views

### Shortest path in a grid between two points

I have this problem where I have to find the shortest path in an NxM grid from point A (always top left) to point B (always bottom right) by only moving right or down. Sounds easy, eh? Well here's the ...
171 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 ...
37k views

...
154 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 ...
1k 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 ...
140 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 ...
78 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 ...
328 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)....
477 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 ...
3k 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 ...
268 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 ...
3k views

### Sum of left and right nodes (individually) in a Binary Search Tree

I have written a program which calculates the sum of all the left nodes and the sum of right nodes in a Binary search tree. I have used BFS to traverse the tree. The code is as follows: ...
3k 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 ...
7k 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 ...
5k 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. ...
36k 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 ...
4k 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 ...
361 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 ...
3k views

### Perform BFS on a Binary Tree

Task: Perform Breadth first traversal on a Binary Search Tree and print the elements traversed. ...
4k 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 ...
178 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 ...
3k views

I want to improve this code using STL. Let me know if I should add any other function in this code. ...
580 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 ...
6k 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 / ...
171 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 ...
4k 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 ...
514 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 ...
621 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 ...
5k views

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. ...
204 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, ...