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.
0
votes
2answers
50 views
BFS in a grid with wall breaking saldo in Java
In this problem, we are given a 2-dimentional grid, with each cell being walkable or holding a wall. Given an integer \$s \geq 0\$, find the shortest path from the source node to target node breaking ...
6
votes
1answer
63 views
Minimum number of flight segments using breadth-first search
I'm practising with graphs, and trying to solve a problem of calculating the minimum number of flight segments, applying breadth-first search.
The code is working, but I think, that it's not clean.
...
1
vote
0answers
27 views
Breadth-First Search in C: Maze-like use of 2D arrays, linked list
Problem:
In a grid of nodes pick a starting node(has mode2), and using Breadth-First search, find one with a ending node (has mode1).
You can make walls so it's harder for the search. And that ...
1
vote
2answers
269 views
Hackerrank: Connected Cells in a Grid
Problem statement
Consider a matrix with \$n\$ rows and \$m\$ columns, where each cell contains either a \$0\$ or a \$1\$ and any cell containing a is called a filled cell. Two cells are said to be ...
11
votes
2answers
193 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 ...
6
votes
1answer
87 views
Shortest Path (BFS) through a maze
Background
I have decided to use this year's Advent Of Code to learn Haskell. I feel like I vaguely understand the language and can solve most of the problems with relative ease. However, the code I ...
1
vote
1answer
44 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 ...
3
votes
1answer
51 views
3
votes
2answers
87 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
...
4
votes
1answer
103 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.
...
3
votes
1answer
39 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 ...
0
votes
0answers
36 views
Return 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 ...
0
votes
2answers
98 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 ...
1
vote
0answers
43 views
Thread pool based unweighted path finder in Java for graphs with slow expansion operator
Introduction
Given a directed unweighted graph, the objective of this library is to find a shortest path from a given source node to a given target node. Clearly, one candidate algorithm to find ...
0
votes
0answers
50 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 ...
2
votes
1answer
157 views
JavaScript breadth-first search algorithm
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:
...
1
vote
1answer
99 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 ...
1
vote
0answers
40 views
Wikipath stack in Java - Part I/IV - The search algorithm
I am working on the following small software stack:
The objective of the entire stack is to search for shortest paths in the Wikipedia article graph as fast as possible. As of now, I rely on two ...
3
votes
3answers
422 views
7
votes
1answer
2k views
2
votes
0answers
43 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:
...
4
votes
1answer
92 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 ...
2
votes
2answers
80 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 ...
5
votes
1answer
155 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 ...
2
votes
1answer
50 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:
...
3
votes
2answers
267 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. ...
2
votes
0answers
589 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
2k views
Breadth-first search on a tree in Python
The following code performs breadth first search on a mockup tree
...
4
votes
1answer
209 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
110 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
392 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
2k 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
91 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
1k 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
268 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
974 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
342 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
2k 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
638 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 ...
4
votes
2answers
1k 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
505 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
352 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
144 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
1k 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
780 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
136 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
4k 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
222 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
158 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
244 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 ...
