Courtesy of Patrick Murphy, wrong output was coming due to small mistake which i easily corrected using following contion: if(parent.get(key)==null) The correct code is: import java.util.*; class BST { Node root; LinkedList<Node> q=new LinkedList<Node>(); TreeMap<Integer,Integer> level=new TreeMap<Integer,Integer>(); TreeMap<Integer,Node> parent=new TreeMap<Integer,Node>(); Node insert(Node x,int key) { if(x==null) { parent.put(key,null); return new...

algorithm,graph,shortest-path,bfs

Consider a graph like this: A---(3)-----B | | \-(1)-C--(1)/ The shortest path from A to B is via C (with a total weight of 2). A normal BFS will take the path directly from A to B, marking B as seen, and A to C, marking C as seen. At...

Yep, that's correct. As soon as you dequeue the node from the queue, you know that you've discovered the shortest path to it. Hope this helps!...

You will need to distinguish three states that a node can be in: unprocessed (not yet seen) discovered (queued) processed (traversed, outputted) With the visited boolean array you might either tag nodes when they are discovered or when they have been traversed. While the term "visited" usually refers to the...

algorithm,graph,directed-graph,bfs

you can use the following pseudo-code: ( you can save the distance from the source node in BFS by setting the distance property of each node to father.distance + 1, and the initial node has a distance of 0. also the initial distance for every node is infinite) BFS(G,targetNode), remember...

Here's your problem : public class Solution { ... static boolean tree[][]; ... public static void main(String[] args) { ... boolean tree[][]=new boolean[vertices+1][vertices+1]; ... You initialize a local tree array instead of your static tree member, which remains null. Change it to : public class Solution { ... static boolean...

c++,pointers,reference,tile,bfs

Firstly reference must be initialized, so you would have to set it in the constructor. Secondly you can't re-assign reference, so your SetCameFrom function won't work. Use pointers for this. Tile * cameFrom; But it's also good to initialize pointer to 0 (or nullptr in C++11) in the constructor. Tile::Tile(int...

Usually the BFS algorithm is simply in order to walk all the nodes in the graph in a breath first manner. As apposed to a DFS (depth first) algorithm which is usually implemented using recursion. For the purpose of finding the shortest distance you need to modify the algorithm: if...

std::map::operator[] is non-const because it will insert elements if needed: int main() { std::map<std::string, std::string> m; m["new element"] = "1"; } The problem is that m is a const AdjList&, on which you cannot call non-const member functions. You can use std::map::find() instead: auto itor = m.find(n); if (itor !=...

algorithm,c++11,shortest-path,bfs

The problem is with memset(d,INF,sizeof(d)); memset() only fills memory with a byte value. Here it will wind up filling the array with the least significant byte of the int value INF. To fix it, create an explicit for loop or use std::fill() instead....

php,multidimensional-array,php-5.5,bfs

Somebody posted, but soon removed the solution. Nevertheless thanks man! It works <? public function handleTree(&$array, $callback) { foreach ($array as &$item) { handleTree($item['items'], $callback); $item = $callback($item) + ['items' => $item['items']]; } } ...

Doing bfs/dfs to answer one query say find "Sally" would suffice. You will need a hashtable H such that when traversing the tree and you are at a node say x then just store in hash table the parent of x, H[x]=parent(x). Also note you can mark parent of root...

I found the issue. Everytime that you are adding a new friend into your friend array, you are overwriting the previous one. What this means is that when you first add number 1, it has a partner of 2. But, when you add 3 1, you overwrite 1 and it...

You are dereferencing your iterator incorrectly print_state(stdout, &it); You would use the * operator print_state(stdout, *it) And judging by the signature of print_state print_state(FILE*, const state_t*) It looks like it should actually be print_state(stdout, &(*it)) ...

As a matter of fact, this function does not compute the diameter. It computes the furthest vertex from a given vertex v. To compute the diameter of a tree, you need first to choose an arbitrary vertex (let's say v), then find the vertex that is furthest away from v...

Basically you are calling the function biggest_dist for each node ( Also i guess you should return bdist not bdist-1). So for each node you get the distance of the maximum node from this node. So here is the pseudocode to get the node with minimum maximum distance /*g is...

algorithm,data-structures,shortest-path,maze,bfs

Your idea is wrong. I haven't read the code because what you describe will fail even if implemented perfectly. Consider something like this: x.... ..... ..*** ....* *...* You will traverse the maze like this: x.... ..... ..123 ....4 *...5 Then go from 5 to the bottom-left * and back...

I'm pretty sure you need to keep track of the step-count along with the vertex in your queue. In other words, rather than queuing up just the vertex, include the number of steps taken to reach that vertex: queue = [(start, 0)] #[ ((x, y), steps-so-far) ] Then, in the...

To limit depth, you could create a class that encapsulates the depth and the page to fetch. You can even put some your functions into that class: public class Page { private final int depth; private final String url; public Page(String url, int depth) { this.url = url; this.depth =...

You can use Bellman-Ford's algorithm, and instead to run until |V| - 1 in the outer loop, run until k. The outer loop iterator indicates the maximal length of the shortest path from the source to each target. From wikipedia (with the outer loop index modification) for i from 1...

c++,performance,algorithm,memory,bfs

I see a number of memory leaks. open is never deleted but maybe could allocated in the stack instead of in the heap. std::queue<Node*> open; More important none of the node you push in the queue are deleted this is probably the origin of very big memory consumption. Delete the...

algorithm,graph,directed-graph,dfs,bfs

If you want to figure out your digraph is strongly connected there are several algorithm for that and in wiki you can find this three: Kosaraju's algorithm Tarjan's algorithm Path-based strong component algorithm If you want to check if your digraph is just connected or not, you can simply assume...

I've played around and here is the result nonechar = 'N' spacechar = '_' solution = [[6], [0, 7], [None, 3, None, 8], [2, 5, None, 9], [1, None, 4, None, None, None], [None, None, None, 4],[None, 3]] for i in range(1, len(solution)): for j in range(len(solution[i-1])): if (solution[i-1][j] ==...

So BFS is a common problem in early programming, and while its solution is not particular to Haskell, the functional nature of Haskell makes things a little trickier. So let's start with DFS: import Control.Monad (msum) dfs target [email protected](Tree value children) | value == target = Just tree | otherwise...

graph,cycle,breadth-first-search,bfs,undirected-graph

Here below you will find the code to traverse a graph using BFS and find its cycles. #include <stdio.h> #include <queue> using namespace std; int nodes, edges, src; int graph[100][100], color[100], prev[100]; const int WHITE = 0; const int GRAY = 1; const int BLACK = 2; void print(int); int...