Solved

Recursive "Breadth first search" (BDF)

Posted on 2000-04-10
8
4,176 Views
Last Modified: 2008-03-17
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
Comment
Question by:tryso
8 Comments
 
LVL 2

Expert Comment

by:Serega
ID: 2699850
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
 
LVL 10

Expert Comment

by:Lischke
ID: 2699870
C in the Delphi area? ;-) just listening...
0
 

Author Comment

by:tryso
ID: 2699905
That is an iterative algorithm..
...I need a recursive one.
(as many childs as you want.. but that's no problem)
0
 

Author Comment

by:tryso
ID: 2699909
Edited text of question.
0
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 2

Accepted Solution

by:
Serega earned 193 total points
ID: 2700257
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
 

Author Comment

by:tryso
ID: 2701315
Um, might be just fine, but I'm using an adjacency List..
Linked lists instead of Arrays..
They are also weighted.
0
 

Expert Comment

by:johnstoned
ID: 2711344
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
 

Author Comment

by:tryso
ID: 2711464
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

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Introduction I have seen many questions in this Delphi topic area where queries in threads are needed or suggested. I know bumped into a similar need. This article will address some of the concepts when dealing with a multithreaded delphi database…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the file…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now