JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Introduction to graphs and their data structures Will this dfs work? << PREV    [ 1 2 ]
 Re: Will this dfs work? (response to post by misof) | Reply This is very cool, Misof.One question, is there any reason why there is only one stack? If we use one stack for the local variable neighbor, and one for the current node index, is it basically the same thing?I'm guessing that you are using one stack because you are simulating what happens if you use an actual recursive function call? Does it make any difference as far as efficiency / speed are concerned?I guess maybe system memory management of two stacks is harder than for a single one?
 Re: Will this dfs work? (response to post by hughperkins) | Reply Ok, nm, after playing, using a single stack is much easier than using multiple ones.
 Re: Will this dfs work? (response to post by misof) | Reply I tried translating/simplifying misof's code above, not sure if its correct, if anyone spots an error, kindly correct me before i go astray. In the meanwhile, i am still puzzled by backtracking that misof mentioned. Can someone kindly give an example on how backtracking can be used, especially within a dfs template. Thanks in advance. Mafoko.```int g[N][N]; int visited[N];   void dfs(int x){ //recursive for(n=0;n s; s.push(x); visited[x]=1; while (!s.empty()) { int t = s.top(); s.pop(); for(n=0;n
 Re: Will this dfs work? (response to post by mafoko) | Reply Shift operations are usually faster operations than multiply and especially divide.
 Re: Will this dfs work? (response to post by hughperkins) | Reply Perhaps of interest is the fact that some architectures have a seperate stack for "data" than for "instruction pointers". This is useful in a number of ways. Reading the invocation stack becomes trivial, since there is no data on it. Corruption of the invocation stack becomes very difficult. I'm sure there are other benefits.Probably a downside in # of transistors and added complexity - but there is usually a trade off.
 Re: Will this dfs work? (response to post by gladius) | Reply The other glaring issue I saw in this article is the section on BFS:```// Now we need to generate all of the transitions between nodes, we can do this quite easily using some // nested for loops, one for each direction that it is possible for one player to move. Since we need // to generate the following deltas: (-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1) // we can use a for loop from -1 to 1 to do exactly that. for (int player1XDelta = -1; player1XDelta <= -1; player1XDelta++) { for (int player1YDelta = -1; player1YDelta <= -1; player1YDelta++) { for (int player2XDelta = -1; player2XDelta <= -1; player2XDelta++) { for (int player2YDelta = -1; player2YDelta <= -1; player2YDelta++) { ```The loops should obviously go from -1 to 1, not -1 to -1. I think that was the author's intent, and he even says so in the comment, it's just incorrect in the actual pseudocode.
 Forums Tutorial Discussions Introduction to graphs and their data structures Will this dfs work? Previous Thread  |  Next Thread << PREV    [ 1 2 ]