Δευτέρα, 30 Οκτωβρίου 2017

Αναθεώρηση 1 (έκδοση 9) και ένα Breadth-First Tree

Μικρή αναθεώρηση.  Εντοπίστηκαν δυο λάθη και διορθώθηκαν.

Παρακάτω είναι ένα πρόγραμμα που περιέχει κόμβους A, B, C, D, E, F, G και για κάθε κόμβο έχει ένα στοιχείο έναν πίνακα κόμβων που συνδέονται άμεσα.  Για παράδειγμα το Α συνδέεται άμεσα με το B και το S. Το πρόγραμμα με μια συνάρτηση γυρνάει μια Κατάσταση (Inventory) όπου το κλειδί είναι ο κόμβος και το περιεχόμενο είναι το επίπεδο, όπου ένα επίπεδο 3 σημαίνει τρια βήματα από την αρχή. Ένα στοιχείο θα έχει το επίπεδο 0, θα είναι η κορυφή. Μπορούμε οποιοδήποτε κόμβο να τον θέσουμε ως κορυφή. Η κατάσταση οδηγείται σε μια ρουτίνα που εμφανίζει ανά γραμμή το κάθε επίπεδο.


Form 60,30
Report 2, "breadth first tree algorithm"
Inventory nodes
\\ a class in a global function (outside a group) which return a group
Class node {
      Dim con$()
Class:
      Module node {
            Dim .con$(stack.size)
            n=Each(.con$())
            While n {
                  Read .con$(n^)
            }
      }
}
Append nodes, "A":=Node("B","S"), "B":=Node("A"), "C":=Node("S","D","E","F")
Append nodes, "D":=Node("C"), "F":=Node("C","G"), "E":=Node("C","H")
Append nodes, "G":=Node("S","F","H"), "H":=Node("E","G")
Append nodes,"S":=Node("A","C","G")
\\Print nodes("A").con$()
Function BFS (nodes, node$) {
      inventory result
      Stack New {
            \\ use stack as a fifo
            Data node$, 0
            While Not Empty {
                  Read where$, level
                  For nodes(where$) {
                        if Exist(result, where$) Then Exit
                        Append result, where$:=level
                        k=Each(.con$())
                        While k {
                                   Data .con$(k^), level+1
                              }
                  }
            }
      }
      =result
}
Printlevel(BFS(nodes, "A"))
Printlevel(BFS(nodes, "G"))
Printlevel(BFS(nodes, "H"))
Printlevel(BFS(nodes, "F"))
Printlevel(BFS(nodes, "S"))
Sub Printlevel(M)
      local N=each(M)
      local level=1
      While N {
            If level<>eval(N) then Print : level=eval(N): Print "level:";level,
            Print eval$(M,N^),
      }
      Print
End Sub