Entry
Datastructure: Graph: Traversal: How to program a walk a graph breadth first? Array: BBCBASIC
Feb 5th, 2005 13:36
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 06 February 2005 - 01:51 am -------------------
Datastructure: Graph: Traversal: How to program a walk a graph breadth
first? Array: BBCBASIC
---
You do the following actions
1. store the given graph in the DATA statements
2. read the given graph
---
3. do a breadth first search of this graph
1. add the begin node at the end of the queue
2. repeat the following actions
1. get the current begin node from the queue
2. remove the current begin node from the queue
3. add all children of this node at the end of the queue
---
---
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 [ ]
--------------------------------------------------------------------
---
---
--- cut here: begin --------------------------------------------------
REM ------------------------------------------------------------------
rowminI% = 1
rowmaxI% = 6
columnminI% = 1
columnmaxI% = 10
:
REM ------------------------------------------------------------------
:
DIM s$( rowmaxI% )
DIM queueP%( rowmaxI% )
:
DIM linkedlistP%( rowmaxI%, columnmaxI% )
:
REM ------------------------------------------------------------------
FOR rowI% = rowminI% TO rowmaxI%
READ s$
PRINT s$
s$( rowI% ) = s$
columnI% = columnminI% - 1
REPEAT
READ P%
stopB% = ( P% = -1 )
columnI% = columnI% + 1
PRINT P%
linkedlistP%( rowI%, columnI% ) = P%
UNTIL stopB%
NEXT rowI%
:
DATA "S", 2, 4, 5, 6, -1
DATA "A", 3, -1
DATA "B", -1
DATA "C", -1
DATA "D", -1
DATA "E", -1
:
REM ------------------------------------------------------------------
REM initialize the queue begin and end counter
queuebeginI% = rowminI% - 1
queueendI% = queuebeginI%
:
REM ------------------------------------------------------------------
REM add a value: add the initialize begin node to the queue
IF ( queueendI% >= rowmaxI% ) THEN PRINT "queue full" ELSE queueendI%
= queueendI% + 1 : queueP%( queueendI% ) = rowminI%
:
REM ------------------------------------------------------------------
REM view the queue
PROCQueueView
:
REM ------------------------------------------------------------------
REM while the queue is not empty
REPEAT
stopB% = ( queuebeginI% >= queueendI% )
IF NOT stopB% THEN PROCGraphSearchBreadthFirstSub
UNTIL stopB%
END
:
:
:
DEF PROCGraphSearchBreadthFirstSub
LOCAL rowI%
rowI% = FNQueueRemove : REM get and remove the node in begin of queue
PRINT rowI%
PRINT s$( rowI% )
PROCGraphSearchBreadthFirstChildrenAdd( rowI% )
ENDPROC
:
REM ------------------------------------------------------------------
REM add the children of the current node to end of the queue
DEF PROCGraphSearchBreadthFirstChildrenAdd( rowI% )
LOCAL columnI%
LOCAL stopB%
LOCAL P%
:
REM add a value: the children of the current node
columnI% = columnminI% - 1
REPEAT
columnI% = columnI% + 1
P% = linkedlistP%( rowI%, columnI% )
stopB% = ( P% = -1 )
IF ( NOT stopB% AND ( queueendI% >= rowmaxI% ) ) THEN PRINT "queue
full" ELSE IF ( NOT stopB% AND NOT ( queueendI% >= rowmaxI% ) ) THEN
queueendI% = queueendI% + 1 : queueP%( queueendI% ) = P%
UNTIL stopB%
:
PROCQueueView
ENDPROC
:
REM ------------------------------------------------------------------
REM view the queue
DEF PROCQueueView
LOCAL P%
LOCAL s$
PRINT "--------------"
PRINT
FOR rowI% = rowminI% TO rowmaxI%
P% = queueP%( rowI% )
IF ( P% <> -1 ) THEN s$ = s$( P% ) ELSE s$ = ""
IF ( P% <> -1 ) PRINT rowI%; " "; s$; " ";
NEXT rowI%
PRINT
FOR rowI% = rowminI% TO rowmaxI%
P% = queueP%( rowI% )
PRINT rowI%; " "; P%; " ";
NEXT rowI%
PRINT
ENDPROC
:
REM ------------------------------------------------------------------
REM remove from begin of queue
DEF FNQueueRemove
LOCAL queueoldP%
IF ( queuebeginI% >= queueendI% ) THEN PRINT "queue empty" ELSE
queuebeginI% = queuebeginI% + 1 : queueoldP% = queueP%(
queuebeginI% ) : queueP%( queuebeginI% ) = -1
= queueoldP%
:
--- cut here: end ----------------------------------------------------
---
If you run this program, it will the following output
--- cut here: begin --------------------------------------------------
S
2
4
5
6
-1
A
3
-1
B
-1
C
-1
D
-1
E
-1
--------------
1 S 2 3 4 5 6
1 1 2 0 3 0 4 0 5 0 6 0
1
S
--------------
2 A 3 C 4 D 5 E 6
1 -1 2 2 3 4 4 5 5 6 6 0
2
A
--------------
3 C 4 D 5 E 6 B
1 -1 2 -1 3 4 4 5 5 6 6 3
4
C
--------------
4 D 5 E 6 B
1 -1 2 -1 3 -1 4 5 5 6 6 3
5
D
--------------
5 E 6 B
1 -1 2 -1 3 -1 4 -1 5 6 6 3
6
E
--------------
6 B
1 -1 2 -1 3 -1 4 -1 5 -1 6 3
3
B
--------------
1 -1 2 -1 3 -1 4 -1 5 -1 6 -1
--- cut here: end ----------------------------------------------------
---
---
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
----------------------------------------------------------------------
