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.
5
votes
3answers
341 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
99 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
44 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
89 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:
...
1
vote
4answers
59 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
68 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
259 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
78 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
69 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
102 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
164 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 ...
3
votes
1answer
2k 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 shortest path between a given source and destination.
...
3
votes
1answer
4k 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
91 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
439 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
132 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
292 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
341 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
232 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
232 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
116 views
What could I possibly change with this BFS and code to enhance its performance?
This code is supposed to find, in a graph, the node with the smallest maximum distance to all the other nodes. The problem can be found here.
For instance, in this example graph:
2 is the node ...
6
votes
4answers
2k 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
5k 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
372 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
2k 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 ...
7
votes
1answer
204 views
Breadth First Search not SOLID enough v2.0
Here is a link to my original question:
Breadth First Search not SOLID enough
Here is my first attempt at refactoring. Instead of using a Tuple, I used a ...
4
votes
1answer
143 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 ...
8
votes
1answer
293 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
458 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
192 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
400 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?
...
8
votes
2answers
889 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
...
8
votes
2answers
102 views
Improving performance of A* search in PHP
I need to figure out what can be done to improve the performance of a A* search algorithm in PHP. The idea is to look for the shortest path, in number of hops, between two points in a "map". Actual ...
5
votes
2answers
1k views
Print binary search tree by levels function implementation
I do not like this implementation as is seems too much complicated. My idea was to implement some BFS algorithm variant.
Some points to notice:
I use one queue.
In the begining put the tree ...
6
votes
4answers
73k views
Depth First Search & Breadth First Search implementation
I've implemented DFS and BFS implementations. I want to check if the code is readable, contains any issues, and can be improved.
GraphImplementation
...
5
votes
1answer
103 views
BFS implementation that walks a tile-based field
I wrote a BFS implementation that walks a tile-based field. It takes a function that should return true for walkable tiles and false for walls. It also takes the start and end points. It currently ...
5
votes
1answer
2k views
Binary tree level order traversal algoritm
I am trying to solve this Binary tree lever order traversal:
...
4
votes
1answer
215 views
Modified BFS code optimizations
I need some help reviewing this code in terms of making as fast as possible. This is a modified version of BFS that does quite a bit of processing on the side.
Use case:
I have a large graph ...
3
votes
1answer
706 views
Solve a maze in the form of a 2D array using BFS - Haskell
Suggestions for improving coding style are greatly appreciated.
...
3
votes
2answers
459 views
Time Limit Exceeded in BFS maze solver
Here's a problem that I tried solving:
Lakshagraha was a house built of lacquer, made by the Kauravas to kill
the Pandavas. The Kauravas wanted to burn the house down when the
Pandavas were ...
0
votes
1answer
3k views
Breadth-first tree traversal using STL list
I am writing code for breadth-first search of a tree with C++'s STL. Please help as I am new to the STL.
...
6
votes
1answer
383 views
Shortest Path in a Unit Cost DAG BFS in Hadoop
Just got done implementing a shortest path algo of a unit cost DAG BFS in Hadoop and wanting to get anyone's opinion on how I could have done it better. The main issue I see is that I lose the ...
3
votes
1answer
7k views
DFS/BFS implementation of Cormen's pseudo code
This is DFS/BFS C++ code for Cormen pseudo code. Please comment on this.
...
6
votes
1answer
403 views
BFS for creating a queue without repetitions and with loops in the graph
I have a pipeline with loops of filters and one input filter. The rest are splitters, transform and output.
I would like my code to go over the filters and push them into a queue (order is ...
2
votes
1answer
227 views
BFS implementation to find connected components taking too long
This is in continuation to a question I asked here. Given the total number of nodes (employees) and the adjacency list (friendship amongst employees), I need to find all the connected components.
...
3
votes
3answers
3k 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 ...
2
votes
1answer
3k views
Breadth- and Depth-first search code
Here is my breadth-first search (bfs) and depth-first search (dfs) code for graph traversal. Please give me some constructive ...
6
votes
1answer
3k views
Improve Graph Adjacency List Implementation and Operations
I am studying graphs and I am trying to make a library in C# for myself and anyone else interested, that is didactic and simple, so I can remember how to solve common problems.
I would like to ...
5
votes
2answers
881 views
Pouring water problem
I just began to study Scala (coming from Python I had quite a few problems with types) and I want to know if my first code to solve a real problem is nicely done or if there is some points that need ...
