Entry
Datastructure: Graph: Traversal: How to program a walk a graph breadth first?
Feb 5th, 2005 12:46
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 06 February 2005 - 01:55 am -------------------
Datastructure: Graph: Traversal: How to program a walk a graph breadth
first?
---
---
A possible program might be
--- cut here: begin --------------------------------------------------
procedure BFS( G, s )
1. Enqueue( s )
2. LOOP
3. n = Dequeue() // get node from the head of the queue
4. FOREACH n' in Successors( n ) DO
Enqueue( n', OPEN ) // insert node at the end of a queue
ENDDO
5. ENDLOOP
--- cut here: end ----------------------------------------------------
---
example:
---
figure:
S
|
+--+--+--+--+
| | | |
A C D E
|
+
|
B
---
---
table
--------------------------------------------------------------------
| ORDER OF VISITATION | QUEUE CONTENTS AFTER PROCESSING NODE |
--------------------------------------------------------------------
[ S ]
S [ A C D E ]
A [ C D E B ]
C [ D E B ]
D [ E B ]
E [ B ]
B [ ]
--------------------------------------------------------------------
---
---
example:
---
figure:
A
|
+----+----+
| |
B C
| |
+--+--+ +--+--+
| | | |
D E F G
---
---
table
---------------------------------------------------------------------
| ORDER OF VISITATION | QUEUE CONTENTS AFTER PROCESSING NODE
---------------------------------------------------------------------
[ A ]
A [ B C ]
B [ C D E ]
C [ D E F G ]
D [ E F G ]
E [ F G ]
F [ G ]
G [ ]
---------------------------------------------------------------------
---
---
Book: see also:
---
[book: Aho, Alfred V. / Hopcroft, John E. / Ullman, Jeffrey D. - data
structures and algorithms - Addison-Wesley - ISBN 0-201-00023-7 - p.
243 'Breadth-First Search' (simple implementation of breadth first
search)]
---
[book: Horowitz, Ellis / Sahni, Sartaj - fundamentals of computer
algorithms - computer science press - 0-914894-22-6 - p. 263 'Breadth
First Search' (simple implementation of breadth first search)]
---
[book: Horowitz, Ellis / Sahni, Sartaj - fundamentals of data
structures in Pascal (2nd edition) - p. 284 'Breadth First Search'
(simple implementation of breadth first search)]
---
[book: Knuth, Donald - the art of computer programming (fundamental
algorithms) / volume 1 (3th edition) - ISBN 0-201-89683-4 - p.
351 'Breadth First Search' (just a very short description)]
---
[book: Lipschutz, Seymour - datastructures - McGraw-Hill - ISBN 0-07-
038001-5 - p. 296 'Traversing a graph: Depth First Search' (nice step
by step example)]
---
[book: Schildt, Herbert - artificial intelligence using C -
Osborne/McGraw-Hill - ISBN 0-07-881255-0 - p. 40 'Breadth First
Search' (description of a special case of the breadth first search)]
---
[book: Sedgewick, Robert - algorithms - Addison-Wesley - ISBN 0-201-
066673-4 - p. 430 'Breadth First Search' (simple and detailed
implementation of breadth first search, using Pascal)]
---
[book: Tremblay, Jean-Paul / Sorenson, Paul G. - an introduction to
datastructures with applications - McGraw-Hill - ISBN 0-07-065157-4 -
p. 449 'Breadth First Search' (simple and detailed implementation of
breadth first search)]
---
[book: Tucker, Alan B. - the computer science and engineering
handbook - CRC press - ISBN 0-8493-2909-4 - p. 208 'Breadth First
Search' (simple implementation of breadth first search)]
---
---
Internet: see also:
---
Datastructure: Link: Overview: Can you give an overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/32054/fid/1264
----------------------------------------------------------------------
