Solved

breadth first search

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

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

Suggested Solutions

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…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.

730 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