# Depth First Search in Commodore Basic

Published on 21 October 2023 (Updated: 21 October 2023)

Welcome to the Depth First Search in Commodore Basic page! Here, you'll find the source code for this program as well as a description of how the program works.

## Current Solution

10 DIM A(99)
20 DIM AM%(99)
25 REM Vertices
30 DIM VX(9)
35 REM Graph:
36 REM - G%(i, j) contains vertex index for child node j,  vertex i or
37 REM   negative to indicate no more child nodes
40 DIM G%(9, 10)
45 REM Visited nodes: 1 if visited, 0 otherwise
50 DIM VS%(9)
55 REM Stack - 2 elements for vertex
60 DIM SK%(19)
70 GOSUB 2000
80 IF V = 0 OR C <> -1 THEN GOTO 400: REM invalid or end of input/value
90 NM = NA
100 FOR I = 0 TO NA - 1
110     AM%(I) = 0
120     IF A(I) <> 0 THEN AM%(I) = 1
130 NEXT I
135 REM Get vertices
140 GOSUB 2000
150 IF V = 0 OR C <> -1 THEN GOTO 400: REM invalid or end of input/value
160 NV = NA
170 FOR I = 0 TO NA - 1
180     VX(I) = A(I)
190 NEXT I
195 REM Get target value
200 GOSUB 1000
210 IF V = 0  OR C >= 0 THEN GOTO 400: REM invalid or not end of input/value
220 T = NR
225 REM Form graph
230 GOSUB 2500
235 REM Perform depth search and show result
240 SP = -1: REM Reset stack pointer
250 GOSUB 3000
260 R\$ = "false"
270 IF VI >= 0 THEN R\$ = "true"
280 PRINT R\$
290 END
400 Q\$ = CHR\$(34): REM quote
410 PRINT "Usage: please provide a tree in an adjacency matrix form ";
420 PRINT "("; Q\$; "0, 1, 1, 0, 0, 1, 0, 0, 0, 0, ";
430 PRINT "1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0"; Q\$; ") ";
440 PRINT "together with a list of vertex values ";
450 PRINT "("; Q\$; "1, 3, 5, 2, 4"; Q\$;  ") and the integer to find ";
460 PRINT "("; Q\$; "4"; Q\$; ")"
470 END
1000 REM Read input value one character at a time since Commodore BASIC
1001 REM has trouble reading line from stdin properly
1002 REM NR = number
1003 REM V = 1 if valid number, 0 otherwise
1004 REM C = -2 if end of input, -1 if end of value,
1005 REM   32 if whitespace, ASCII code of last character otherwise
1006 REM Initialize
1010 NR = 0
1020 V = 0
1030 S = 1
1035 REM Loop while leading spaces
1040 GOSUB 1500
1050 IF C = 43 OR C = 45 THEN GOTO 1100: REM + or -
1060 IF C >= 48 AND C <= 57 THEN GOTO 1150: REM 0 to 9
1070 IF C = 32 THEN GOTO 1040: REM whitespace
1080 RETURN: REM other character
1085 REM Loop while sign
1090 GOSUB 1500
1100 IF C = 43 THEN GOTO 1090: REM +
1110 IF C >= 48 AND C <= 57 THEN GOTO 1150: REM 0 to 9
1120 IF C <> 45 THEN RETURN: REM not -
1130 S = -S
1140 GOTO 1090
1145 REM Set valid flag
1150 V = 1
1155 REM Loop while digits
1160 NR = (ABS(NR) * 10 + C - 48) * S
1170 GOSUB 1500
1180 IF C >= 48 AND C <= 57 THEN GOTO 1160: REM 0 to 9
1185 REM Loop while trailing spaces
1190 IF C < 0 OR C <> 32 THEN RETURN: REM end character or not whitespace
1200 GOSUB 1500
1210 GOTO 1180
1500 REM Get input character
1501 REM A\$ = input character
1502 REM C = One of the following:
1502 REM - -1 if end of value
1503 REM - -2 if end of input
1504 REM - 32 if whitespace
1505 REM - ASCII code otherwise
1510 GET A\$
1520 C = ASC(A\$)
1530 IF C = 13 THEN C = -1
1540 IF C = 255 THEN C = -2
1550 IF C = 9 OR C = 10 THEN C = 32
1560 RETURN
2001 REM A contains array value
2002 REM NA contains length of array
2003 REM V = 1 if valid number, 0 otherwise
2004 REM C = -2 if end of input, -1 if end of value,
2005 REM   32 if whitespace, ASCII code of last character otherwise
2006 REM Initialize
2010 NA = 0
2020 GOSUB 1000: REM Read input value
2030 IF V = 0 THEN RETURN: REM invalid
2040 A(NA) = NR
2050 NA = NA + 1
2060 IF C < 0 THEN RETURN: REM end of input or value
2070 IF C = 44 THEN GOTO 2020: REM comma, get next value
2080 V = 0
2090 RETURN
2500 REM Form graph
2501 REM Inputs:
2502 REM - AM% contains adjacency matrix
2503 REM - NM contains number of items in adjacency matrix
2504 REM - NV contains number of vertices
2505 REM Output: G% contains graph
2510 K = -1
2520 FOR I = 0 TO NV - 1
2530     N = -1
2540     FOR J = 0 TO NV - 1
2550         K = K + 1
2560         IF K >= NM THEN GOTO 2600
2570         IF AM%(K) = 0 THEN GOTO 2600
2580         N = N + 1
2590         G%(I, N) = J
2600     NEXT J
2610     G%(I, N + 1) = -1: REM End of child nodes
2620 NEXT I
2630 RETURN
3000 REM Perform depth first search
3001 REM Commodore Basic does not really support recursion because everything
3002 REM is a global variable. However, recursion can be simulated with
3003 REM a "stack". This "stack" is just an array, SK, and a stack index, SP.
3004 REM Inputs:
3005 REM - VX contains vertices
3006 REM - NV contains number of vertices
3007 REM - T contains value to find
3008 REM - G% contains graph
3009 REM Output: VI contains index of vertex found, -1 if not found
3010 REM Initialize visited nodes
3020 FOR I = 0 TO NV - 1
3030     VS%(I) = 0
3040 NEXT I
3050 REM Start at root node
3060 NI = 0
3070 VI = -1
3100 REM Recursive portion of algorithm
3101 REM Inputs:
3102 REM - NI contains node index
3103 REM - VX contains vertices
3104 REM - NV contains number of vertices
3105 REM - T contains value to find
3106 REM - G% contains graph
3107 REM - VS% contains visited nodes
3108 REM Output: VI contains index of vertex found, -1 if not found
3110 IF VX(NI) = T THEN VI = NI: GOTO 3250: REM Found
3120 VS%(NI) = 1: REM Indicate node visited
3130 J = -1
3140 J = J + 1
3150 CI = G%(NI, J): REM Get child node
3160 IF CI < 0 THEN GOTO 3250: REM No more child nodes
3170 IF VS%(CI) <> 0 THEN GOTO 3140: REM Skip visited node
3180 SP = SP + 1: SK%(SP) = J: REM Push child node index
3190 SP = SP + 1: SK%(SP) = NI: REM Push node index
3200 NI = CI: REM Go to child node
3210 GOSUB 3100: REM Perform depth first search on child node
3220 NI = SK%(SP): SP = SP - 1: REM Pop node index
3230 J = SK%(SP): SP = SP - 1: REM Pop child node index
3240 IF VI < 0 THEN GOTO 3140: REM If not found, go to next child node
3250 RETURN

Depth First Search in Commodore Basic was written by:

• rzuckerm

If you see anything you'd like to change or update, please consider contributing.

## How to Implement the Solution

No 'How to Implement the Solution' section available. Please consider contributing.

## How to Run the Solution

No 'How to Run the Solution' section available. Please consider contributing.