Entry
Datastructure: Graph: Presentation: List: Linked: How program representation connections? BBCBASIC
Feb 5th, 2005 13:26
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 05 February 2005 - 09:49 pm -------------------
Datastructure: Graph: Presentation: List: Linked: How program
representation connections? BBCBASIC
---
Example:
Given the following graph:
A
|
+------+------+
| |
B C
| |
+--+--+ +--+--+
| | | |
D E F G
---
Here you have the following row numbers for the nodes
table
-----------------------------------
| NR | NODE |
-----------------------------------
1 A
2 B
3 C
4 D
5 E
6 F
7 G
-----------------------------------
---
Thus node A has as children node B and C, respectively row 2 and 3
Thus node B has as children node D and E, respectively row 4 and 5
Thus node C has as children node F and G, respectively row 6 and 7
Thus node D has no children
Thus node E has no children
Thus node F has no children
Thus node G has no children
---
This you might represent as follows in a linked list of children
(using '-1' as an indicator for no children anymore)
A, 2, 3, -1
B, 4, 5, -1
C, 6, 7, -1
D, -1
E, -1
F, -1
G, -1
---
To read a representation of this graph, you might use
the following program:
--- cut here: begin --------------------------------------------------
rowmaxI% = 7
FOR rowI% = 1 TO rowmaxI%
READ s$
PRINT s$
columnI% = 1 - 1
REPEAT
READ P%
stopB% = ( P% = -1 )
IF NOT stopB% THEN columnI% = columnI% + 1 : PRINT P%
UNTIL stopB%
NEXT rowI%
:
DATA "A", 2, 3, -1
DATA "B", 4, 5, -1
DATA "C", 6, 7, -1
DATA "D", -1
DATA "E", -1
DATA "F", -1
DATA "G", -1
--- cut here: end ----------------------------------------------------
---
If you run this program it will show:
--- cut here: begin --------------------------------------------------
A
2
3
B
4
5
C
6
7
D
E
F
G
--- cut here: end ----------------------------------------------------
---
---
Example:
Given the following graph:
S
|
+--+--+--+--+
| | | |
A C D E
|
+
|
B
---
Here you have the following row numbers for the nodes
table
-----------------------------------
| NR | NODE |
-----------------------------------
1 S
2 A
3 B
4 C
5 D
6 E
-----------------------------------
---
Thus node S has as children node A, C, D, E, respectively row 2, 4, 5,
6
Thus node A has as children node B, respectively row 3
Thus node B has no children
Thus node C has no children
Thus node D has no children
Thus node E has no children
---
This you might represent as follows in a linked list of children
(using '-1' as an indicator for no children anymore)
S, 2, 4, 5, 6, -1
A, 3, -1
B, -1
C, -1
D, -1
E, -1
---
To read a representation of this graph, you might use
the following program:
--- cut here: begin --------------------------------------------------
rowmaxI% = 6
FOR rowI% = 1 TO rowmaxI%
READ s$
PRINT s$
columnI% = 1 - 1
REPEAT
READ P%
stopB% = ( P% = -1 )
IF NOT stopB% THEN columnI% = columnI% + 1 : PRINT 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
--- cut here: end ----------------------------------------------------
---
If you run this program it will show:
--- cut here: begin --------------------------------------------------
S
2
4
5
6
A
3
B
C
D
E
--- 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
----------------------------------------------------------------------
