Solved

breadth first search

Posted on 1997-04-30
1
192 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
Comment Utility
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

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…
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…
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 for-loops in the C programming language.

728 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

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now