?
Solved

breadth first search

Posted on 1997-04-30
1
Medium Priority
?
206 Views
Last Modified: 2010-04-15
is there code for a breadth first search of a graph? (not depth first search).
0
Comment
Question by:biggup
[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
  • Learn & ask questions
1 Comment
 
LVL 4

Accepted Solution

by:
jos010697 earned 140 total points
ID: 1250197
You need an additional queue to store the fan out of the
current nodes. Here's some pseudo code:

Note: push operates on the front of the queue (as
if it were a stack), while pop pops an element
from the rear of the queue.

queue= empty;
push(queue, node);
bfs(stack);

void bfs(stack_t stack) {
node_t node;

if (!(node= pop(stack)) /* anything left to do? */
   return;

if (!marked(node)) { /* if not been here before */
   mark(node);      /* mark it and do something useful here */
   for (<all edges leaving this node>)
      push(stack, node->fanout);
   bfs(stack); /* tail recursion here (it could be an iteration */
}

kind regards,

Jos
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
Suggested Courses

771 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