java,data-structures,tree,graph-algorithm,depth-first-search

You don't need stack here. Only recursion: public void dfs(Node node) { if (node == null) { return; } System.out.println("Node: " + node.getVertex()); node.state = State.Visited; for (Node n : node.getAdjacent()) { if (n.state != State.Visited) { dfs(n); } } } UPDATE To check path existence: public boolean isPath(Graph graph,...

algorithm,depth-first-search,edges

Your relationships for forward and back edges are incorrect - you should exchange them. Apart from that, I would recommend reading this paragraph from wikipedia: http://en.wikipedia.org/wiki/Depth-first_search#Output_of_a_depth-first_search it includes a more intuitive and straightforward definition of those edges and a good picture: Direct answers to your questions When we have for...

algorithm,data-structures,graph,binary-tree,depth-first-search

It's always better to work just with current state, not next or prevous (no matter, dfs, or bfs). boolean search(Graph g, Node current, Node target) { if (current == null || target == null) return false; current.state = State.Visited; if (current == target) return true; for(Node u: current.getChildNodes()) { if(u.state...

java,algorithm,graph,graph-algorithm,depth-first-search

Switch 4 : Toggles all numbers that have modulus 1 with 3 1 % 3 = 1 4 % 3 = 1 7 % 3 = 1 10 % 3 = 1 Switch #1: 0000000000 <- Switch #2: 0101010101 <- Switch #3: 1010101010 Switch #4: 0110110110 <-...

search,graph,depth-first-search,breadth-first-search

And how would you define "best" ? If you know that the goal node is at depth n from the root node (the node from which you begin the search), BFS - will ensure that the search won't iterate nodes with depth > n. That said, DFS might still "choose"...

"static" in this context essentially means "there is only one of these that is shared by all invokations of this function". You're still passing a copy of the variable as a parameter to the other functions. If you want a called function to be able to modify a variable, you...

c++,algorithm,recursion,depth-first-search,dfs

The following change to your code should help: int Search::DFSUtil(std::string search_key, Graph& x, int current_node, Color(visited_nodes)[], bool& goal_f){ visited_nodes[current_node-1] = GREY; //-1 because array index start from 0 but nodes index on the graph starts from 1 if(x.get_node_value(current_node) == search_key ){ goal_f = 1; return current_node; } else{ std::queue <int>...

The problem is that dfs is returning an int, and then you're trying to assign that int to an array. Try: visitados[i] = dfs(1, vertices, visitados, matriz);...

tree,binary-search-tree,graph-algorithm,depth-first-search,breadth-first-search

The problem you're trying to solve is called the maximum independent set problem applied to trees. As a hint, think about the following: For each complete subtree of the tree, think about the optimal solution for that subtree in two cases - the case where you include that node in...

c++,c,algorithm,depth-first-search,breadth-first-search

You can implement adjacency list with vectors like this, it is much easier than using pointers. Check the code, it is also much easier to understand how it works. #include <bits/stdc++.h> using namespace std; vector<int> edges[5]; bool visited[5]; void dfs(int x) { visited[x] = true; for(int i=0; i < edges[x].size();...

java,components,depth-first-search

Your solution is almost done. You had to adjust the variables' scope to be within the for loop that checks the visited array. Also you have to use indexes that start from 0 because u can cause an ArrayIndexOutOfBoundsException. Also you do not have to give source as input. Here...

python,graph-theory,depth-first-search

As mentioned in the comment, your algorithm has no reason to terminate if you allow arbitrary cycles. What you could do is allow for a maximum path length and dismiss all paths that are too long: def find_all_paths(graph, start, end, path=[], max_length=10): if len(path) >= max_length: return [] path =...

Look at node a - what could DFS do in node a? It could go either to b or e. We see that it chose b, because a->b is a tree edge and a->e is a forward edge (check the definition of tree/forward edge). In b the only choice was...

c++,boost,depth-first-search,boost-graph,visitor

If you want to "track" which "route" vertex is currently being explored, you can use code similar to "predecessor_recorder" in your visitor. Details on predefined predecessor_recorder can be found here: http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/predecessor_recorder.html. In fact, you probably would better of with dijkstra_shortest_paths. That algorithm reports a predecessor map for you. You can...

python,recursion,depth-first-search

Try something like this: def all_paths_dfs(graph, start, end, path=None): if path is None: path = [] path.append(start) all_paths = set() if start == end: all_paths.add(tuple(path)) else: for neighbor in graph[start]: if neighbor not in path: all_paths |= all_paths_dfs(graph, neighbor, end, path) path.pop() return all_paths if __name__ == "__main__": graph =...

python,algorithm,graph-theory,depth-first-search

Here is a working solution that uses two stacks during the iterative subroutine. The array traceBack holds the vertices that have been explored and is associated with complementary 2D-array, stack, that holds arrays of edges that have yet to be explored. These two arrays are linked; when we add an...

algorithm,search,time,time-complexity,depth-first-search

No you are not wrong, of course if you find the destination in current node's neighbors (children in your wordings), you can terminate it. However, I will stick to "standard" implementation due to 2 reasons: (Just my personal concerns) Easier Implementation, Higher Readability, For example, you may want to do...

c++,c,algorithm,depth-first-search,maze

It's better if we used basic AI knowledge. Define a set of valid operations for this specific problem, an initial state, a final state and let your program use a search tree of states with the defined operations to find the solution.

list,artificial-intelligence,depth-first-search

Open list helps you in both depth first and breadth first searches to traverse your tree properly. Think about algorithms step by step. You are in a node with many children and your are going to expand one of them. After expansion there should be a mechanism to get back...

java,algorithm,arraylist,graph-theory,depth-first-search

I will assume that you have a State class with the following attributes (if you like graphs, use Node instead of State): Set<Town> unused; // towns not yet visited ArrayList<Town> path; // current path double dist; // total distance in path Then use code like this one to recursively try...

c++,segmentation-fault,depth-first-search

In the second case, the dfs function causes infinite recursion. The first call is dfs(u=2, c=1); which calls dfs(u=1, c=1); which calls dfs(u=2, c=1); and so on ad nauseum. If you run your code in a debugger you should be able to see what happened by outputting the stack trace...

algorithm,time-complexity,depth-first-search,iterative-deepening

If the tree is not balanced and the answer lies nearer to the root than the deepest leaf, then the answer will be found by a depth-limit which is less than the maximum depth of the tree, whereas depth first search may have to search half of the tree to...

Look this is your error : depth_first_search(X, X, [X],0). depth_first_search(X, Y, [X|T],L):- link(X, Z , L1), depth_first_search(Z, Y, T,L2),L=L1+L2. GOAL depth_first_search("Erbil", "Duhok", PathToGoal,Dis). It's working for me now :)...

java,algorithm,depth-first-search,maze

I think the problem is that when you make a move from A to B, you are pushing the new position B onto the stack. This means that when you backtrack you never get back to A. Try reordering: position = doMove(position, move) cells.setVisited(position); stack.push(position); to stack.push(position); position = doMove(position,...

Listing a vector's contents via brace-enclosed list is only valid in C++11 or later. You will need to use a compiler that complies with C++11 to compile this code.

c++,priority-queue,depth-first-search,topological-sort

The problem seems to be that pq.top is called before all outgoing edges of the current node have been checked. Consider the following graph: Nodes: A, B, C; Edges A->B, A-C. Let C have a smaller priority value, i.e. it should come first. During dfs(A), you check B before C....

ruby-on-rails,ruby,recursion,depth-first-search

Because depth_first_search(node.child_left, target) isn't the last line of your method, it's value will never be returned. You need to return it's value if it's value is not nil. Here is an example of one way to solve your problem: def depth_first_search(node, target) if node.value == target puts "yes" return node...

algorithm,graph,shortest-path,depth-first-search,breadth-first-search

If anyone is interested in how I solved this here is my solution: def dfs(self, v): if v.successor is None: # this is the root node v.cost = 0 v.visited = True for adj in v.adj: if adj.visited is False: # set the parent adj.successor = v adj.cost = v.cost...

c,graph,depth-first-search,adjacency-list

I cannot tell if this is the only problem with your code, but the visited array should not be declared on the stack. The way your code is now, there is a separate visited array for each recursive call of your function. Instead, you should make it a pointer to...

Inclusion/Exclusion will give you the number of quadruples, but won't give you the quadruples themselves. Let Ai be the set of quadruples satisfying Lj<=Xj<=Rj for all j, with Xi=X(i+1) (where the indices are cyclic, so X5 means X1). In the example you provided, A1 = { (1114), (1124), (2214), (2224),...

algorithm,matrix,depth-first-search

char[][] M = new char[][]; init(M); count = 0; for each row: for each element of the row: if M[row][column] == specific_char: count = count + 1; return count; ...

You were told wrong, your output is correct. You can check it by hand: 1 2 3 4 5 6 7 8 1 {0, 1, 0, 0, 1, 1, 0, 0} 2 {1, 0, 0, 0, 0, 1, 1, 0} 3 {0, 0, 0, 1, 0, 0, 1, 0} 4...

python,set,cluster-computing,depth-first-search,breadth-first-search

It seems from your example that for any X and Y, if X in graph[Y] then Y in graph[X}. If that's the case, then: def addNode(name, neighbors, graph, clusterlist): graph[name] = neighbors clusters = set() for n in neighbors: graph[n].add(name) for c in clusterlist: if n in c: c.add(name) clusters.add(frozenset(c))...