[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 4298
  • Last Modified:

Recursive "Breadth first search" (BDF)

Can anybody help me with the code for a recursive Breadth First Search  Traversal-routine for a graph?
I only need a Pseudocode.
My textbook says it's hard, but I'm too lazy to make that queue-ADT ;)
Thanks!

(Sorry, forgot to mention the recursive-part)
0
tryso
Asked:
tryso
1 Solution
 
SeregaCommented:
See http://yoda.cis.temple.edu:8080/UGAIWWW/books/shoham/chapter2/section2.5.html
or this:

Here is an implementation of breadth--first search. Notice that a queue is used instead of a stack; otherwise, this routine is virtually identical to the second implementation of depth--first search:

tree_type
bfs_queue(tree_type tree, BOOL (*predicate)(tree_type))
{
  queue_type queue = create_queue();
  tree_type guess;

  enqueue(tree, queue);
  while (empty_(queue) == FALSE)
    {
      guess = dequeue(queue);
      if (empty_tree(guess) == TRUE)
        continue;
      if (predicate(guess) == TRUE)
        return guess;
      enqueue(left_child(guess), queue);
      enqueue(right_child(guess), queue);
    }
  return the_empty_tree;
}
0
 
LischkeCommented:
C in the Delphi area? ;-) just listening...
0
 
trysoAuthor Commented:
That is an iterative algorithm..
...I need a recursive one.
(as many childs as you want.. but that's no problem)
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
trysoAuthor Commented:
Edited text of question.
0
 
SeregaCommented:
I don't see what language it was. But it pass for opcode. :)
Ok, I think recursive one by another kind of opcode will look like this:

marks: array[0..N] of boolean;
{marks := (FALSE,...,FALSE) }
function bfs_queue(nodenr: integer):integer;
begin
  marks[nodenr] := true;
  if predicate(nodenr) then
    return nodenr;

  if( exist(neighbour(nodenr))
  begin
    neighbourNr := neighbour(nodenr);
    if not marks[neighbourNr] then
    begin
      if predicate(neighbourNr) then
        return neighbourNr;
      marks[neighbourNr] := true;
      res := bfs_queue(nodenr);
      if res > 0 then return res;
      marks[neighbourNr] := false;
      res := bfs_queue(neighbourNr);
      return res;
    end;
  end;  
  return 0;
end;
0
 
trysoAuthor Commented:
Um, might be just fine, but I'm using an adjacency List..
Linked lists instead of Arrays..
They are also weighted.
0
 
johnstonedCommented:
I don't think it's possible to do breadth first search recursivley.  I think if you tried, you would end up doing a depth first search.

I can give you a recursive algorithm for DFS if you want?

Dave.
0
 
trysoAuthor Commented:
Hi,
I've solved the problem semi-satisfactory with a DFS algorithm. I know that it is possible to do a recursive BFS-algorithm because my textbook leaves it to the reader to make a pseudocode for such an algo (although it stresses that it's a difficult task).
I'm not 100% sure wheter Serega solved the problem or not since I used an adjacancy list instead of an adjacancy matrix, but I'll look into it shortly, and think it's fair that he gets the points, taking into account that he at least came very close (and I guess there is no big task to convert from matrix to linked lists..).
Thank you all! :)
- T -

0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now