As of May 31, 2023, we have updated our Code of Conduct.

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
Filter by
Sorted by
Tagged with
3k views

### BFS' shortest path unweighted directed graph

The code I have is based on BFS and a little bit of Dijkstra and returns the shortest path of an unweighted directed graph as an integer. I was wondering if someone could take a look at my code too ...
• 41
7k views

### Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
• 440
1k views

### CLRS Implementation of BFS and DFS in C++

I tried to implement BFS and DFS from Introduction to Algorithms by Cormen. Any suggestions on how to improve my code? GraphStructures.h ...
• 85
1k views

### Implementation of BFS on a graph

I have written the code below as a BFS implementation. Could someone please review. In particular, I want to know if there could be a memory leak. ...
1k views

### Get a path between graph nodes using breadth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using breadth-first search. I'm doing this to improve my style ...
• 435
189 views

### Calculating shortest possible route between two given nodes

I recently came across this problem: Heroes in Indian movies are capable of superhuman feats. For example, they can jump between buildings, jump onto and from running trains, catch bullets with ...
• 389
1 vote
137 views

### Efficient keyword trie implementation in C++ with failure/output links

For a current project implementing a parser for a bifurcation analysis tool, I wanted to utilize a keyword trie based solution, as there are possibly a ton of user supplied keywords. However, i found ...
• 4,221
1 vote
1k views

I have implemented a breadth-first search and I'm more or less looking for suggestions on how I can improve on what I've done here. How to use: ...
• 397
1 vote
12k views

### Print tree level by level including Empty node

Here is my code to print tree in a level by level way. It needs to print an empty node as well to keep tree structure like full binary tree for elegancy reasons. I'm wondering if anything you think ...
• 3,443
6k views

### Create a complete binary tree and do level order traversal on it

How can I optimize this code? ...
55k views

...
• 363
54 views

### LinkedList of Nodes at each level - optimalization

That's already known problem: to return an array of linked lists that contain values of elements at each level. Eg for tree with depth n there should be n linked lists. I wrote the solution: ...
• 131
829 views

### Recursive Breadth First Search Knights Tour

This program was written on Windows 7 using Visual Studio 2012 Professional. Some of the issues encountered may have been fixed or changed in a more recent version. This is a quote from my second ...
• 22.4k
346 views

### Finding the Least Common Ancestor of a Binary Tree

Input a binary tree (the root node) and 2 other nodes that need to be assessed for finding the least common ancestor (LCA) Code: a. Finding the nodes first with either ...
300 views

### Knights Tour - Improved Refactored Recursive Breadth First Search for

The development and testing was performed on a Dell M6400 Laptop (Intel Core 2 Duo) running Centos 7, g++ compiler version 4.8.5, compiler switches -O3 -std=c++0x -D__cplusplus=201103L. (machine ...
• 22.4k
68 views

### ExtensionMethods for iterating hierarchically data structures depth/breath-first

I wrote a few simple extension methods that allow to traverse a hierachically data structure depth-first or breath-first using LINQ: Usage: ...
• 8,528
9k 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. ...
• 145
2k views

I have refactored the version of the previous (and initial) iteration according to the answer by alexwlchan. As a reminder, this snippet compares breadth-first search against its bidirectional variant....
• 26.7k
7k views

### Breadth-first search on a tree in Python

The following code performs breadth first search on a mockup tree ...
• 225
969 views

### Recursive Breadth First Search for Knights Tour

This was written as an experiment in performance, based on another question here on CodeReview. Input into the algorithm is the number of squares on one edge of the chess board, the point of origin, ...
• 22.4k
194 views

### Finding smallest number of moves

We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this: ...
1k views

### Graph theory using C++ STL

I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object. Any feedback would be ...
• 393
4k views

### C++ Graph Implementation

My data set is a list of Edges which are passed as a pair of integers. Based on that, I have the following graph implementation for BFS. Could someone please review ...
• 81
252 views

### Graph radius in Java - follow-up

See the previous and initial iteration. Terminology Given an undirected graph $G = (V, E)$, the eccentricity of a node $u \in V$, $e(u)$, is the maximum length (number of edges) of a shortest ...
• 26.7k
3k views

### Breadth first search implementation (also includes functions for finding shortest path and number of connected components)

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the breadth first search section (5.7) using javascript. I also have a ...
915 views

(See the next iteration.) The following snippet is a brute-force algorithm for computing a graph radius in time $\Theta(V^2 + VE)$ and space $\Theta(V)$ simply by doing $|V|$ breadth-first ...
• 26.7k
1 vote
5k views

(See the next iteration.) I have this Python (3.4) script for demonstrating the performance of the BFS algorithm, both traditional and bidirectional: ...
• 26.7k
2k views

### BFS for modified shortest path

Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ? The itinerary of each ...
• 597
6k views

### Breadth and Depth First Search in Ruby

I was tasked with building three individual methods; one to create a Binary Search Tree (BST), one to carry out a Breadth First Search (BFS), and one to carry out a Depth First Search (DFS). Create ...
• 571
4k views

### Shortest path on a maze with keys and doors

The locks of the doors present in the maze are of 7 types: A, B, C, D, E, F and G. There are also some copies of keys around the maze, which can be of types a, b, c, d, e, f or g. A key of type a ...
• 597
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 ...
• 449
642 views

### SPOJ solution of GRAVITY

I am solving problem GRAVITY on SPOJ. Each test case is a rectangular ASCII grid of dimensions m × n, and you have to determine ...
• 51
2k views

### Breadth-First Search heuristics to find solution to Water Jug Challenge

I started learning AI recently. In AI, searches should be avoided and everything in AI is a search problem. One of the easiest problem where we could use general AI search techniques is the water jug ...
• 283
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
2k views

### Checking whether a graph is bipartite using BFS

I am solving a simple problem that checks whether a graph is two-colourable (bipartite graph). I am using BFS for this approach using C++ STL. I've replaced cin and ...
736 views

### Basic graph traversals

Below is an implementation of two graph traversals. Graph constructor creates a random graph with a fixed number of edges (fixed as a proportion of the maximum number of vertices, ...
• 593
8k views

### Recursive Level Order traversal

I have come up with this code to do level order traversal recursively for a binary search tree. ...
937 views

### Doing tree search in Java

I have this tiny library for building unbalanced, binary trees and doing tree search on them. I tried hard to define a generic API that would allow custom implementations of trees. ...
• 26.7k
193 views

### Yet another graph search

I noticed there were already countless implementations of graphsearch procedures on here, but there were a couple of features of my approach that I haven't seen in the others, plus I would greatly ...
• 295
1 vote
607 views

### Minesweeper algorithm that works within O(1) space complexity

For minesweeper algorithm, instead of the most obvious BFS or DFS solution, I want a O(1) space solution. First of all, I'll explain how the program works. I will pass in a 2D array, with 1 ...
220 views

### Search for Tree

Here is a search implementation for my tree. It searches each node in a breadth-first manner first, but it goes deeper in a depth-first manner, in the event it needs to go deeper. I know there may ...
33k views

### Shortest path using Breadth First Search

I have sample graphs like the following (un-directed un-weighted cyclic graphs). My goal is to find the shortest path between a given source and destination. I have found this implementation on web ...
• 277
36k views

### Depth First Search and Breadth First Search in C++

I am trying to learn DFS and BFS. However, I just want to make sure that I am not doing anything wrong. Would you please determine if the BFS and DFS functions are correct? ...
• 391
691 views

### Grid walk problem and solving it recursively

On CodeEval, there's a Grid Walk challenge: There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the ...
• 445
41k 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 ...
• 333
4k 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: ...
• 333
4k views

### Shortest path through a maze

I was trying to solve this problem in Java: Given a 2-D array of black and white entries representing a maze with designated entrance and exit points, find the shortest path from entrance to exit, ...
• 1,203
1k views

### BFS Maze Solver in Scala

I recently got a Scala developer position, so I'd like to get more comfortable with Scala on my own. Here is a maze solver that I wrote (previously in other languages) that I translated to Scala. Any ...
• 201
1k views

### Determining if there is a route between two nodes in a directed graph

This algorithm should return a boolean value, telling if there is a path between two nodes in a given directed graph. ...
• 131