Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

breadth first search

Posted on 1997-04-30
1
Medium Priority
?
208 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
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

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.

Question has a verified solution.

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

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
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 and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Suggested Courses
Course of the Month12 days, 11 hours left to enroll

580 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