[Last Call] Learn about multicloud storage options and how to improve your company's cloud strategy. Register Now

x
Solved

Posted on 2000-04-10
Medium Priority
4,279 Views
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
Question by:tryso
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 2

Expert Comment

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

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

Author Comment

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

ID: 2699909
Edited text of question.
0

LVL 2

Accepted Solution

Serega earned 579 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

ID: 2701315
Um, might be just fine, but I'm using an adjacency List..
They are also weighted.
0

Expert Comment

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

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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi projâ€¦
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 this video, Percona Director of Solution Engineering Jon Tobin discusses the function and features of Percona Server for MongoDB. How Percona can help Percona can help you determine if Percona Server for MongoDB is the right solution for â€¦
Want to learn how to record your desktop screen without having to use an outside camera. Click on this video and learn how to use the cool google extension called "Screencastify"! Step 1: Open a new google tab Step 2: Go to the left hand upper cornâ€¦
Suggested Courses
Course of the Month13 days, 7 hours left to enroll