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.

learn more… | top users | synonyms

4
votes
0answers
39 views

Knights Tour - Improved Refactored Recursive Breadth First Search for

This development and testing was done on a Dell M6400 Laptop (Intel Core 2 Duo) running Centos 7, g++ compiler, compiler switches -O3 -std=c++0x -D__cplusplus=201103L. (machine bought August 2009 with ...
1
vote
0answers
25 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: ...
-1
votes
0answers
25 views

Algorithm to draw the shortest path in grid

I want to find the shortest path between two points in the grid, and than mark the path with '+' sign. I found the shortest path using BFS algorithm, but now I'm not sure how can I mark it using ...
3
votes
2answers
122 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. ...
1
vote
0answers
141 views

Breadth-first search: traditional and bidirectional in Python - follow-up

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....
6
votes
1answer
705 views

Breadth-first search on a tree in Python

The following code performs breadth first search on a mockup tree ...
4
votes
1answer
113 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, ...
2
votes
1answer
80 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: ...
8
votes
1answer
259 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 ...
8
votes
2answers
713 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 ...
2
votes
1answer
79 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 ...
6
votes
1answer
269 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 ...
0
votes
1answer
153 views

Graph radius in Java

(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 ...
1
vote
2answers
405 views

Breadth-first search: traditional and bidirectional in Python

(See the next iteration.) I have this Python (3.4) script for demonstrating the performance of the BFS algorithm, both traditional and bidirectional: ...
2
votes
1answer
173 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 ...
3
votes
0answers
842 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 ...
1
vote
1answer
225 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 ...
3
votes
2answers
817 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 ...
5
votes
3answers
437 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 ...
2
votes
2answers
239 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 ...
1
vote
0answers
104 views

Generalized Missionaries and Cannibals in Java - follow-up

See the previous and initial iteration. Now I have incorporated all the points suggested by mdfst13, and have the following: StateNode.java: ...
5
votes
1answer
669 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" -algorithm: Demo.java:...
1
vote
4answers
519 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 ...
3
votes
2answers
119 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, ...
4
votes
3answers
3k views

Recursive Level Order traversal

I have come up with this code to do level order traversal recursively for a binary search tree. ...
2
votes
1answer
143 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. ...
3
votes
1answer
119 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 ...
1
vote
1answer
167 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 ...
7
votes
2answers
192 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 ...
4
votes
3answers
10k 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 ...
3
votes
1answer
19k 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? ...
3
votes
1answer
148 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 ...
3
votes
1answer
6k 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 ...
3
votes
1answer
671 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: ...
4
votes
1answer
930 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, ...
3
votes
2answers
471 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 ...
3
votes
2answers
464 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. ...
8
votes
3answers
250 views

Breadth-first search for clusters of pixels in a given color range

I am a beginner in programming languages, so I apologise if my code is badly formatted or doesn't make any sense. My program gets an image and a RGB color range as input and it counts how many pixels ...
1
vote
1answer
149 views

Finding the node with the smallest maximum distance to all the other nodes

This code is supposed to find, in a graph, the node with the smallest maximum distance to all the other nodes. The problem from Quora is : How do I find the node that has the least maximum ...
6
votes
4answers
5k views

Python 8-Puzzle and solver

I wrote a simple 8-Puzzle and solver and am interested in seeing how it might be improved. Please let me know if any style or design changes might enhance the readability/performance of my code. <...
1
vote
1answer
11k views

Graph Creation and BFS + DFS in C#

I was asked to implement a graph and BFS and DFS. Please comment. Is it understandable? Is my algorithm correct? Are there any optimizations? ...
11
votes
3answers
458 views

Finding shortest paths in directed graphs

I have very little experience in programming with C++ and the following small "program" is the 2nd one I have ever written in that language. I am most interested in comments regarding naming ...
6
votes
2answers
4k views

BFS shortest path program

The task was to find the shortest path between P and K in a maze. You can move horizontally and vertically, where # is a wall and ...
8
votes
1answer
264 views

Breadth First Search not SOLID enough v2.0

Original question: Breadth First Search not SOLID enough Here is my first attempt at refactoring. Instead of using a Tuple, I used a ...
5
votes
1answer
318 views

Optimizing breadth-first-search code

I wrote code using some kind of breadth-first-search algorithm in order to find a path (any path!) from a start point to an end point. There are no weights/different distances involved from path-to ...
7
votes
1answer
451 views

Breadth First Search not SOLID enough

The following code has a modified version of the Breadth First Search algorithm. It not only visits the nodes, but keeps track of the paths, so I can output various messages later. I would like to ...
1
vote
1answer
983 views

Crawl multiple pages at once

This an update to my last question. I want to process multiple pages at once pulling URLs from tier_list in the crawl_web ...
1
vote
2answers
274 views

Basic search engine

I want to improve efficiency of this search engine. It works in about 10 seconds for a search depth of 1, but 4 minutes at 2 etc. I tried to give straightforward comments and variable names, any ...
4
votes
2answers
845 views

BFS tree traversal Scala

I would love some feedback on the following code for BFS traversal in a binary tree. Is there a cleaner way to write this? ...
9
votes
2answers
1k views

Run time complexity of printing a binary tree level by level

I have some doubts about running time of following question. The problem is printing a binary tree level by level. For example if tree is like ...