PureBasic Forums - English

Code: Select all

;- desc
; we have 5 node numbered: 0, 1, 2, 3, 4
; if node u neighbound with node v  then (u, v)=1
; other (u, v)=0

;example:
; 0 - 2
;    / \
; 1 4 - 3 

; matrix a(u,v)
; 0 0 1 0 0
;
; 0 0 0 0 0
;
; 1 0 0 1 0
;
; 0 0 1 0 1
;
; 0 1 0 1 0

;find a path from S=0 to F=4: 4 <- 2 <- 0
;or S = 1 to F =2: "not found"
;and that is shortest path

;- global var
#max = 4
Global Dim a.l(#max, #max)
Global Dim free.l(#max)
Global Dim trace.l(#max)
Global Dim queue.l(#max)
Global s.l, f.l, front.l, rear.l, n.l
n = #max

;- procedures
Procedure init()
  s = 0
  f = 4
  a(0,2) = 1
  a(2,0) = 1 : a(2,3) = 1 : a(2,4) = 1
  a(3,2) = 1 : a(3,4) = 1
  a(4,2) = 1 : a(4,3) = 1
  For i = 0 To n
    free(i) = 1
  Next i
  free(s) = 0
  queue(0) = s
  rear = 0
  front = 0
EndProcedure

Procedure.l pop()
  tm.l = queue(front)
  front = front + 1
  ProcedureReturn tm
EndProcedure

Procedure push(value.l)
  rear = rear + 1
  queue(rear) = value
EndProcedure

Procedure bfs()
  Repeat
    u = pop()
    For v = 0 To n
      If free(v) And a(u, v)
        push(v)
        free(v) = 0
        trace(v) = u
      EndIf
    Next v 
  Until front > rear
EndProcedure

Procedure result()
  OpenConsole()
  PrintN("Path from "+Str(S)+" To "+Str(F)+":")
  If free(f)
    PrintN("not found")
  Else
    While f <> s
      Print(Str(f)+"<-")
      f = trace(f)
    Wend
    Print(Str(s))
  EndIf
  Input()
  CloseConsole()
EndProcedure

;- main
init()
bfs()
result()
End