Solved

breadth first search

Posted on 1997-04-30
1
199 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 70 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

DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

Question has a verified solution.

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

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
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 and use switch statements in the C programming language.

777 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